Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
Sketching Cuts in Graphs and Hypergraphs , booktitle =
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
Authors reframe gadget reductions for CSP non-redundancy using hypergraph projections and shrinking factors to obtain improved super-linear lower bounds for select predicates, with SAT solvers used to discover reductions automatically.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
citing papers explorer
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
-
Streaming Complexity Separations for Dense and Sparse Graphs
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
-
Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Authors reframe gadget reductions for CSP non-redundancy using hypergraph projections and shrinking factors to obtain improved super-linear lower bounds for select predicates, with SAT solvers used to discover reductions automatically.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.