Lower bounds for approximating graph parameters via communication complexity
From MaRDI portal
Publication:5009503
DOI10.4230/LIPICS.APPROX-RANDOM.2018.11MaRDI QIDQ5009503FDOQ5009503
Authors: Talya Eden, Will Rosenbaum 
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1709.04262
Recommendations
- Property testing lower bounds via communication complexity
- Estimating parameters associated with monotone properties
- Estimating parameters associated with monotone properties
- The query complexity of graph isomorphism: bypassing distribution testing lower bounds
- On approximating the number of k-cliques in sublinear time
Cites Work
- Title not available (Why is that?)
- Property testing and its connection to learning and approximation
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Distributed verification and hardness of distributed approximation
- Title not available (Why is that?)
- Property testing in bounded degree graphs
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- An information statistics approach to data stream and communication complexity
- Probabilistic communication complexity
- Proofs from THE BOOK
- Title not available (Why is that?)
- Approximating average parameters of graphs
- On the distributional complexity of disjointness
- Title not available (Why is that?)
- Counting stars and other small subgraphs in sublinear-time
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Testing the diameter of graphs
- Tight Bounds for Testing Bipartiteness in General Graphs
- Property testing lower bounds via communication complexity
- Approximation algorithms for combinatorial auctions with complement-free bidders
- Estimating Sum by Weighted Sampling
- Approximately counting triangles in sublinear time
- On approximating the number of \(k\)-cliques in sublinear time
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Testing Triangle-Freeness in General Graphs
- A stable marriage requires communication
- On the average-case complexity of property testing
- On sampling edges almost uniformly
- Title not available (Why is that?)
Cited In (6)
- The arboricity captures the complexity of sampling edges
- Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
- Sublinear time estimation of degree distribution moments: the arboricity connection
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- Almost optimal query algorithm for hitting set using a subset query
- Lower Bounds for Approximating Graph Parameters via Communication Complexity
This page was built for publication: Lower bounds for approximating graph parameters via communication complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009503)
