Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
hub
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages =
23 Pith papers cite this work. Polarity classification is still indexing.
23
Pith papers citing it
hub tools
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Randomized LOCAL algorithm computes 2-ruling sets in O(log log n) rounds w.h.p. on graphs with arboricity O(log log n), nearly matching lower bounds and exponentially improving prior combinations of results.
A threshold κ=Θ(1/√α) (α=m/n) separates easy collision finding from OGP-based exponential lower bounds against online algorithms in single-layer binary NNs.
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.
Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 3-approximation to the Duality Relaxation Benchmark in unit-demand single-buyer revenue maximization.
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.
Introduces forward-assisted purification via a new spatiotemporal framework that outperforms conventional static purification by up to 50x in copy efficiency and circumvents no-purification theorems for Bell states.
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.