Lower bounds for approximating graph parameters via communication complexity
From MaRDI portal
Publication:5009503
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
- scientific article; zbMATH DE number 1256715 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 6862103 (Why is no real title available?)
- scientific article; zbMATH DE number 7204459 (Why is no real title available?)
- scientific article; zbMATH DE number 3041944 (Why is no real title available?)
- A stable marriage requires communication
- An information statistics approach to data stream and communication complexity
- Approximately counting triangles in sublinear time
- Approximating average parameters of graphs
- Approximation algorithms for combinatorial auctions with complement-free bidders
- Communication Complexity
- Counting stars and other small subgraphs in sublinear-time
- Distributed verification and hardness of distributed approximation
- Estimating Sum by Weighted Sampling
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- On approximating the number of \(k\)-cliques in sublinear time
- On sampling edges almost uniformly
- On the average-case complexity of property testing
- On the distributional complexity of disjointness
- Probabilistic communication complexity
- Proofs from THE BOOK
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Property testing lower bounds via communication complexity
- Sublinear-time algorithms for counting star subgraphs via edge sampling
- Testing Triangle-Freeness in General Graphs
- Testing the diameter of graphs
- The Probabilistic Communication Complexity of Set Intersection
- Tight Bounds for Testing Bipartiteness in General Graphs
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
- Lower Bounds for Approximating Graph Parameters via Communication Complexity
- Almost optimal query algorithm for hitting set using a subset query
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)
