Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
hub
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages =
17 Pith papers cite this work. Polarity classification is still indexing.
17
Pith papers citing it
hub tools
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
The first dynamic algorithms for matrix rank and related objects achieve update times scaling with rank r, specifically Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, extending to dynamic maximum matching.
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
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.
The one-way communication complexity of reporting k-edit occurrences (including the edit sequences) is Θ(n/m · k log(m|Σ|/k)) bits for 0 < k < m < n/2.
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
Introduces a distributed stochastic setting for graph optimization and supplies fast approximation algorithms for matching, vertex cover, and dominating set that surpass non-stochastic lower bounds.
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
Sparsity helps for k-independent set only below certain density thresholds, with new algorithms achieving O(min(n^{ωk/3} + m^{k/3}, n^k)) time and conditional lower bounds showing brute-force necessity above thresholds for many binary constraint families.
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
Generalizes homomorphism indistinguishability equivalences induced by orthogonal easy quantum groups, including a classification of (0,0)-intertwiners for graph-theoretic versions.
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
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.
-
Dynamic Rank, Basis, and Matching
The first dynamic algorithms for matrix rank and related objects achieve update times scaling with rank r, specifically Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, extending to dynamic maximum matching.
-
Online Steiner Forest with Recourse
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
-
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.
-
The Communication Complexity of Pattern Matching with Edits Revisited
The one-way communication complexity of reporting k-edit occurrences (including the edit sequences) is Θ(n/m · k log(m|Σ|/k)) bits for 0 < k < m < n/2.
-
Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
Tight single-pass linear-space lower bounds for approximating arbitrary Max-CSP(F) whenever the basic LP admits a (γ,β)-integrality gap.
-
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
-
Distributed Stochastic Graph Algorithms
Introduces a distributed stochastic setting for graph optimization and supplies fast approximation algorithms for matching, vertex cover, and dominating set that surpass non-stochastic lower bounds.
-
Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
Hybrid sketching saves up to 97% space on dense graphs and 15% on sparse ones by sketching dense cores and storing sparse parts exactly, with new BalloonSketch reducing sketch sizes up to 8x.
-
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
Sparsity helps for k-independent set only below certain density thresholds, with new algorithms achieving O(min(n^{ωk/3} + m^{k/3}, n^k)) time and conditional lower bounds showing brute-force necessity above thresholds for many binary constraint families.
-
Understanding Robust Catalytic Computing
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.
-
Near-optimal streaming approximation for Max-DICUT in sublinear space using two passes
A two-pass sublinear-space streaming algorithm achieves (1/2-ε)-approximation for Max-DICUT on unbounded-degree graphs.
-
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
First efficient sum-of-squares algorithms recover exact and approximate overlapping planted cliques in dense random intersection graphs for k ≫ √(n log n), with robustness to noise, monotone adversaries, and optimal edge corruptions.
-
Homomorphism Indistinguishability Relations induced by Quantum Groups
Generalizes homomorphism indistinguishability equivalences induced by orthogonal easy quantum groups, including a classification of (0,0)-intertwiners for graph-theoretic versions.
-
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.
-
Hardness and Approximation for Coloring Digraphs
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
- The Quantum Homomorphism Orders are Universal