Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
hub Canonical reference
Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva
Canonical reference. 80% of citing Pith papers cite this work as background.
33
Pith papers citing it
Background
80% of classified citations
hub tools
citation-role summary
background 4
method 1
citation-polarity summary
representative citing papers
A threshold κ=Θ(1/√α) (α=m/n) separates easy collision finding from OGP-based exponential lower bounds against online algorithms in single-layer binary NNs.
First deterministic sublogarithmic-round spanner and APSP algorithms in linear, sublinear, and near-linear MPC plus Congested Clique via derandomized hitting sets.
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.
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.
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.
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.
Regularity in hypergraphs is fine-grained equivalent to the general case for clique detection, enabling a complete classification of k-sparse Boolean CSP optimization complexity by constraint degree: linear for d≤1, clique-equivalent for d=2, and exhaustive-search for d≥3 under 3-uniform hyperclique
Unconditional lower bounds and tight upper bounds for distributed quantum state certification under public- and private-coin communication models.
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
Small symmetries create strict hierarchies in resolution with exponential separations from standard resolution, constant-depth Frege, and between SRCI and SRII.
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
cgFOC admits computable VC-dimension bounds on nowhere dense structures and efficient algorithms for query answering and PAC learning on locally bounded expansion classes, but a minor extension is intractable on trees.
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.
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
First learning-augmented algorithms for online minimization problems that use stable dual LP predictions to improve theoretical guarantees on metrical task systems and laminar set cover.
Backdoors can be embedded in ResNet and ViT models as statistically indistinguishable latent directions, reducing cryptographic undetectability to an intractable hypothesis test over parameter distributions.
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.
GenusSink achieves near-linear time approximate generalized Sinkhorn for bounded genus graphs via separator decompositions, computational geometry, and fast distance matrix operations.
Rigorous security proofs for variable-length QKD, phase-error bounding with imperfect detectors, marginal-constrained entropy accumulation, and authentication reductions place practical QKD on firmer mathematical ground.
Semialgebraic graphs admit O(n^{1-2/(d+1)+ε})-bit adjacency labels via polynomial partitioning; semilinear graphs need only O(log n) bits.
Connectivity-preserving important separators of size at most k number 2^{O(k log k)} and can be enumerated in the same bound, yielding 2^{O(k log k)} FPT time for constant-class Node Multiway Cut-Uncut.
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.
-
Deterministic Distance Approximation in MPC via Improved Hitting Sets
First deterministic sublogarithmic-round spanner and APSP algorithms in linear, sublinear, and near-linear MPC plus Congested Clique via derandomized hitting sets.
-
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.
-
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.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
-
Multi-Source Reachability in Near-Optimal Time
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
-
Revisiting Diameter in Directed Graphs
The paper shows fine-grained hardness for approximating reachability diameter in directed graphs, gives additive approximations for unweighted cases, and constant-factor approximations for bounded treewidth and width-bounded DAGs.
-
Learning-Augmented Online Minimization with Dual Predictions
First learning-augmented algorithms for online minimization problems that use stable dual LP predictions to improve theoretical guarantees on metrical task systems and laminar set cover.
-
Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
GenusSink achieves near-linear time approximate generalized Sinkhorn for bounded genus graphs via separator decompositions, computational geometry, and fast distance matrix operations.
-
Approximation Preserving Coresets
Introduces approximation-preserving coresets that guarantee cost preservation for near-optimal solutions and proves that even tiny approximation-factor distortion forbids coresets of that size.
-
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.