scientific article; zbMATH DE number 7378623

DOI10.4230/LIPIcs.APPROX-RANDOM.2018.11MaRDI QIDQ5009503

Will Rosenbaum, Talya Eden

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1709.04262

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

lower boundscommunication complexitysublinear graph parameter estimation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (5)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Unnamed Item ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling

Cites Work

• Probabilistic communication complexity
• An information statistics approach to data stream and communication complexity
• Property testing lower bounds via communication complexity
• On the distributional complexity of disjointness
• Sublinear-time algorithms for counting star subgraphs via edge sampling
• A stable marriage requires communication
• On the Average-Case Complexity of Property Testing
• Property testing and its connection to learning and approximation
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• Counting Stars and Other Small Subgraphs in Sublinear-Time
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Approximating average parameters of graphs
• Testing Triangle-Freeness in General Graphs
• The Probabilistic Communication Complexity of Set Intersection
• Testing the diameter of graphs
• Approximately Counting Triangles in Sublinear Time
• Tight Bounds for Testing Bipartiteness in General Graphs
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• On Approximating the Number of $k$-Cliques in Sublinear Time
• On Sampling Edges Almost Uniformly
• Estimating Sum by Weighted Sampling
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Proofs from THE BOOK
• Property testing in bounded degree graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: