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.
34
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
Introduces a heavy-edge technique yielding a 1.622k-approximation for n-pairs shortest paths in weighted graphs, better than previous (2k-3) results.
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.
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.
-
Collision Resistance of Single-Layer Neural Nets
A threshold κ=Θ(1/√α) (α=m/n) separates easy collision finding from OGP-based exponential lower bounds against online algorithms in single-layer binary NNs.
-
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.
-
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.
-
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.
-
Improved Approximation Algorithms for n-Pairs Shortest Paths
Introduces a heavy-edge technique yielding a 1.622k-approximation for n-pairs shortest paths in weighted graphs, better than previous (2k-3) results.
-
Distributed Property Testing with (Quantum) Carrier Pigeons: Tight Bounds on State Certification
Unconditional lower bounds and tight upper bounds for distributed quantum state certification under public- and private-coin communication models.
-
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.
-
The Power of Small Symmetries
Small symmetries create strict hierarchies in resolution with exponential separations from standard resolution, constant-depth Frege, and between SRCI and SRII.
-
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.
-
Complexity of Clique-Guarded First-Order Logic with Counting
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.
-
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
Uniform-Ironed-Virtual-Value Item Pricing achieves a tight 3-approximation to the Duality Relaxation Benchmark in unit-demand single-buyer revenue maximization.
-
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.
-
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.
-
Backdoor Channels Hidden in Latent Space: Cryptographic Undetectability in Modern Neural Networks
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.
-
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.
-
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.
-
Rigorous Security Proofs for Practical Quantum Key Distribution
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.
-
Implicit representations via the polynomial method
Semialgebraic graphs admit O(n^{1-2/(d+1)+ε})-bit adjacency labels via polynomial partitioning; semilinear graphs need only O(log n) bits.
-
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.
-
Graph Alignment Topology as an Inductive Bias for Grounding Detection
A GNN trained on bipartite alignment graphs between references and LLM generations reports state-of-the-art hallucination detection across four datasets, beating prior methods and GPT-4o.
-
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.
-
Differentially Private Modeling of Disease Transmission within Human Contact Networks
A differentially private pipeline using node-level DP summaries to fit ERGMs or SBMs, generate synthetic networks, and simulate SIS disease spread on ARTNet sexual contact data produces incidence, prevalence, and intervention effect sizes close to non-private versions.
-
Maximum Likelihood Decoding of Quantum Error Correction Codes
A topical review unifying statistical mechanics, tensor network, and AI approaches to approximate maximum likelihood decoding for quantum error correction codes.
-
A Guide to Higher-Order Homophily
A survey of existing measures and models for quantifying and generating higher-order homophily and heterophily in hypergraphs.