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
Minor containment and disjoint paths in almost-linear time
Canonical reference. 80% of citing Pith papers cite this work as background.
38
Pith papers citing it
Background
80% of classified citations
hub tools
citation-role summary
background 4
other 1
citation-polarity summary
representative citing papers
For every δ < 3/2 the ⊆-minimal minor-closed classes with density >δ form a finite explicitly identified set, yielding a 2^poly(n)-time algorithm that computes δ(excl(Z)) or reports ≥3/2 for any finite forbidden-minor set Z.
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
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.
First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
New irrelevant-vertex theorem for (k,d)-Folio gives linkage function ℓ(k) bounded by 2^{poly(k)}.
Scalable ROM-PRUs imply a positive resolution to the Aaronson-Kuperberg unitary synthesis problem, with any such algorithm requiring a classical oracle of input length (2-o(1))log d that rules out existing candidates.
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
A randomized algorithm maintains O(Δ / ln Δ) coloring of dynamically changing triangle-free graphs with amortized Δ^{o(1)} log n update time per edge update against an adaptive adversary.
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
Any 1-PRS can be amplified to t-PRS for polynomial t by randomness accounting and quantum extractors that eliminate arbitrary ancilla.
Quantum algorithms achieve poly(k) query complexity for tolerant k-junta testing with ε1 = 1/2-1/k and ε2 = 1/2-1/(2k²), while classical algorithms require k^Ω(log k) queries.
A new data structure samples any entry of the noise vector in constant time while exactly reproducing the binary tree Gaussian mechanism distribution, applied to DP CountSketches for improved range counting and join size estimation.
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.
γ-graph dimension characterizes learnability for aggregation of interpolators in regression; median-of-three is optimal and strictly stronger than proper learning.
Functions on the half-slice passing the k-query BLR test with probability (1+δ)/2 agree with an affine function on (1 + δ^{1/(k-2)})/2 - o(1) fraction of points, for k≥3.
Modified logarithmic Sobolev inequalities hold for Davies semigroups in 2D Abelian quantum double models at positive temperatures via a Dobrushin-Shlosman condition and verified strong martingale property for conditional expectations.
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
A technique for enforcing differential privacy in temporal runtime monitoring by analyzing dependencies and injecting noise into specifications while using tree mechanisms to limit accuracy loss.
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.
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.
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.
-
Obstructions for Minor-Closed Classes of limiting Densities Below 3/2
For every δ < 3/2 the ⊆-minimal minor-closed classes with density >δ form a finite explicitly identified set, yielding a 2^poly(n)-time algorithm that computes δ(excl(Z)) or reports ≥3/2 for any finite forbidden-minor set Z.
-
Robust Structure Learning of $k$-local Lindbladians
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
-
Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity
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.
-
Adversarially Robust Approximate Furthest Neighbor
First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
-
Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
-
Optimal Bounds for the k-Disjoint Paths Problem
New irrelevant-vertex theorem for (k,d)-Folio gives linkage function ℓ(k) bounded by 2^{poly(k)}.
-
On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
Scalable ROM-PRUs imply a positive resolution to the Aaronson-Kuperberg unitary synthesis problem, with any such algorithm requiring a classical oracle of input length (2-o(1))log d that rules out existing candidates.
-
Online Steiner Forest with Recourse
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
-
Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
A randomized algorithm maintains O(Δ / ln Δ) coloring of dynamically changing triangle-free graphs with amortized Δ^{o(1)} log n update time per edge update against an adaptive adversary.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
The Presort Hierarchy for Geometric Problems
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
-
Generic Number-of-Copies Amplification for Pseudorandom States
Any 1-PRS can be amplified to t-PRS for polynomial t by randomness accounting and quantum extractors that eliminate arbitrary ancilla.
-
Quantum Advantage in Tolerant Junta Testing
Quantum algorithms achieve poly(k) query complexity for tolerant k-junta testing with ε1 = 1/2-1/k and ε2 = 1/2-1/(2k²), while classical algorithms require k^Ω(log k) queries.
-
A Fast Gaussian Mechanism under Continual Observation, with Applications
A new data structure samples any entry of the noise vector in constant time while exactly reproducing the binary tree Gaussian mechanism distribution, applied to DP CountSketches for improved range counting and join size estimation.
-
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.
-
The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
γ-graph dimension characterizes learnability for aggregation of interpolators in regression; median-of-three is optimal and strictly stronger than proper learning.
-
Low Soundness Linearity Testing on the Half-Slice
Functions on the half-slice passing the k-query BLR test with probability (1+δ)/2 agree with an affine function on (1 + δ^{1/(k-2)})/2 - o(1) fraction of points, for k≥3.
-
Modified logarithmic Sobolev inequalities for Abelian quantum double models
Modified logarithmic Sobolev inequalities hold for Davies semigroups in 2D Abelian quantum double models at positive temperatures via a Dobrushin-Shlosman condition and verified strong martingale property for conditional expectations.
-
Testable and Actionable Calibration for Full Swap Regret
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
-
Differentially Private Runtime Monitoring
A technique for enforcing differential privacy in temporal runtime monitoring by analyzing dependencies and injecting noise into specifications while using tree mechanisms to limit accuracy loss.
-
Offline Local Search for Online Stochastic Bandits
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
-
Dominating Set with Quotas: Balancing Coverage and Constraints
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.
-
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.
-
Colorful Minors
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
-
The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
O(n log n) algorithm for edge-coloring planar graphs with Delta >= 8 using Delta colors, extending prior O(n log n) result for Delta >= 9 and generalizing to bounded-genus graphs.
-
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.
-
Finding irrelevant vertices in linear time on bounded-genus graphs
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
-
Submodular Maximization over Many Matroids via Ordered Local Search
A new ordered local search algorithm achieves k/2 + o(k) approximation for monotone submodular maximization over k matroids and (ln 4 k)/3 + o(k) for weighted k-set packing.
-
Fast mixing of all-to-all quantum systems at high temperatures
k-local quantum Hamiltonians admit system-size-independent spectral gap for Gibbs samplers at high temperature, enabling FPT quantum approximation algorithms for partition functions.
-
Computing canonical labellings of finite solvable groups
Defines a canonical labelling function for finite solvable groups via presentations and cohomology so that can(G) equals can(H) exactly when G and H are isomorphic.
-
Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics
DQMW-Sample realizes a classically hard online learning primitive via dissipative quantum dynamics with sublinear regret and proven hardness for classical simulation including PH collapse.
-
Sublinear Time Algorithms for Abelian Group Property Testing
Presents a tester for abelian group property testing in the PS-model with time Õ(√|G| + 1/ε), improving on prior linear-time testers.
-
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.
-
$O(n +f(k))$: Truly Linear FPT
Defines TLFPT as O(n) + f(k) algorithms, proves it is strictly contained in Linear FPT via diagonalization, and exhibits several problems (SAT, Vertex Cover, k-Path, etc.) that belong to TLFPT under parameters such as treedepth and BFS-width.
-
Engineering Algorithms for Dynamic Greedy Set Cover
First experimental study of dynamic greedy set cover algorithms reveals practical tradeoffs in quality and efficiency across real instances.
-
Are controlled unitaries helpful?
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.
- Quantum Simulation of Non-Hermitian Special Functions and Dynamics via Contour-based Matrix Decomposition