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.