Cover Image

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bishnu, Arijit, Chanda, Debarshi, Mishra, Gopinath
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models
by: Bishnu, Arijit, et al.
Published: (2025)

Near Uniform Triangle Sampling Over Adjacency List Graph Streams
by: Bishnu, Arijit, et al.
Published: (2024)

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
by: Chanda, Debarshi
Published: (2025)

Optimal non-adaptive algorithm for edge estimation
by: Bishnu, Arijit, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

Sublinear Algorithms for Wasserstein and Total Variation Distances: Applications to Fairness and Privacy Auditing
by: Basu, Debabrota, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

Cover Edge-Based Novel Triangle Counting
by: Bader, David A., et al.
Published: (2024)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
by: Chen, Xi, et al.
Published: (2024)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
by: Bringmann, Karl, et al.
Published: (2022)

Triangle Counting with Local Edge Differential Privacy
by: Eden, Talya, et al.
Published: (2023)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
by: Anand, Aditya, et al.
Published: (2024)

Counting Distinct Square Substrings in Sublinear Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
by: Cen, Ruoxu, et al.
Published: (2025)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
by: Eden, Talya, et al.
Published: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
by: Biedl, Therese, et al.
Published: (2026)

Approximate Butterfly Counting in Sublinear Time
by: Luo, Chi, et al.
Published: (2026)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
by: He, Jialin, et al.
Published: (2025)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
by: Chakraborty, Sourav, et al.
Published: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

Learning Partitions using Rank Queries
by: Chakrabarty, Deeparnab, et al.
Published: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
by: de Vos, Tijn, et al.
Published: (2024)

Sublinear Random Access Generators for Preferential Attachment Graphs
by: Even, Guy, et al.
Published: (2016)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries
by: Boninsegna, Fabrizio
Published: (2025)

Counting Balanced Triangles on Social Networks With Uncertain Edge Signs
by: Zhou, Alexander, et al.
Published: (2026)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
by: Fu, Bin, et al.
Published: (2026)

Streaming Graph Algorithms in the Massively Parallel Computation Model
by: Czumaj, Artur, et al.
Published: (2025)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)

Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
by: Beretta, Lorenzo, et al.
Published: (2025)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
by: Pfisterer, Kevin, et al.
Published: (2026)

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
by: Kapralov, Michael, et al.
Published: (2022)

DTC: Real-Time and Accurate Distributed Triangle Counting in Fully Dynamic Graph Streams
by: Xuan, Wei, et al.
Published: (2025)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
by: Jiang, Yonggang, et al.
Published: (2025)

Cut-Query Algorithms with Few Rounds
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Submodular Maximization in Exactly $n$ Queries
by: Balkanski, Eric, et al.
Published: (2024)