Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
6th Conference on Innovations in Theoretical Computer Science (ITCS) , pages =
8 Pith papers cite this work, alongside 10 external citations. Polarity classification is still indexing.
8
Pith papers citing it
10
external citations · external index
representative citing papers
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.
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.
Any n-qubit QC Hamiltonian sparsifies to Õ(n/ε²) terms preserving all state energies within 1±ε using invariant subspace decomposition and the Alon-Kozma operator inequality.
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.
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
A survey of existing measures and models for quantifying and generating higher-order homophily and heterophily in hypergraphs.
citing papers explorer
-
A Near-Optimal Parallel Algorithm for Finding Matroid Bases
Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query 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.
-
Quantum Cut Sparsifiers
Any n-qubit QC Hamiltonian sparsifies to Õ(n/ε²) terms preserving all state energies within 1±ε using invariant subspace decomposition and the Alon-Kozma operator inequality.
-
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.
-
Optimal Sparsifiers for Abelian Cayley Graphs
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
-
A Guide to Higher-Order Homophily
A survey of existing measures and models for quantifying and generating higher-order homophily and heterophily in hypergraphs.