Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
hub
Korhonen, A single-exponential time 2-approximation algorithm for treewidth, in: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), 2022, pp
35 Pith papers cite this work, alongside 20 external citations. Polarity classification is still indexing.
35
Pith papers citing it
20
external citations · external index
hub tools
citation-role summary
background 2
other 1
citation-polarity summary
representative citing papers
Modular construction of succinct arguments for QMA via OSP-based interactive protocol plus collapsing-hash communication compression compiler, without LWE.
Coverability for order-k nested reset counter systems is F_Ωk-complete.
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.
The Nesting Bird Box Problem is ER-complete.
Coherent-state propagation enables quasi-polynomial classical simulation of bosonic circuits with logarithmically many Kerr gates at exponentially small trace-distance error, with polynomial runtime in the weak-nonlinearity regime.
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 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.
First shuffle-DP and joint-DP algorithms for GLM contextual bandits achieve near non-private regret without strong spectral assumptions on contexts.
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.
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
An FPT-time O(2^k log n)-approximation is given for k-MMSA_3, alongside gap-preserving reductions clarifying inapproximability across the MMSA hierarchy.
Presents a forward-only construction of semilinear inductive invariants for VAS built solely from the source configuration, avoiding backward reasoning.
Establishes L membership for identity acceptors, all F in commutative monoids, and L(R)-commutative UoG monoids, plus NL-completeness dichotomies for BA2 and U, using product graphs and Green's relations.
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.
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.
Introduces CIRCLES protocol that computes relative majority with k^3 states via circular lists where no two agents of same color share a list.
CBNE enables estimation of nonlinear quantum properties such as higher-order expectations from a single randomized measurement setting under sufficient system dimension or ancillary qubits.
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.
Deterministic O(n^{2.686})-time algorithm for Monotone Min-Plus Product and n^{1.5+o(1)}-time algorithm for Monotone Min-Plus Convolution, derandomizing prior randomized results.
Using the shuffle index, the authors formulate and solve an optimization problem for post-shuffle minimax-optimal unbiased mean estimation, yielding an asymptotically optimal mechanism whose privacy-utility tradeoff approaches the central Gaussian mechanism in the high-privacy regime.
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.
Structural liveness of conservative Petri nets is EXPSPACE-complete because minimal live markings are at most doubly exponential in net size.
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.
-
A Modular Approach to Succinct Arguments for QMA
Modular construction of succinct arguments for QMA via OSP-based interactive protocol plus collapsing-hash communication compression compiler, without LWE.
-
The Complexity of Nested Reset Counter Systems
Coverability for order-k nested reset counter systems is F_Ωk-complete.
-
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.
-
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
The Nesting Bird Box Problem is ER-complete.
-
Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
Coherent-state propagation enables quasi-polynomial classical simulation of bosonic circuits with logarithmically many Kerr gates at exponentially small trace-distance error, with polynomial runtime in the weak-nonlinearity regime.
-
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 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.
-
Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits
First shuffle-DP and joint-DP algorithms for GLM contextual bandits achieve near non-private regret without strong spectral assumptions on contexts.
-
Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
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.
-
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
-
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
An FPT-time O(2^k log n)-approximation is given for k-MMSA_3, alongside gap-preserving reductions clarifying inapproximability across the MMSA hierarchy.
-
A Forward-Only Construction of Semilinear Inductive Invariants for VAS
Presents a forward-only construction of semilinear inductive invariants for VAS built solely from the source configuration, avoiding backward reasoning.
-
On the Reachability Problem on Monoid-Labelled Undirected Graphs
Establishes L membership for identity acceptors, all F in commutative monoids, and L(R)-commutative UoG monoids, plus NL-completeness dichotomies for BA2 and U, using product graphs and Green's relations.
-
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.
-
Distributed Stochastic Graph Algorithms
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.
-
Ranking Opinions with Few States in Population Protocols
Introduces CIRCLES protocol that computes relative majority with k^3 states via circular lists where no two agents of same color share a list.
-
Quantum Nonlinear Properties from a Single Measurement Setting
CBNE enables estimation of nonlinear quantum properties such as higher-order expectations from a single randomized measurement setting under sufficient system dimension or ancillary qubits.
-
Understanding Robust Catalytic Computing
Three new robust error models for catalytic tape resetting are characterized with equivalences to standard classes and collapse under derandomization.
-
Deterministic Monotone Min-Plus Product and Convolution
Deterministic O(n^{2.686})-time algorithm for Monotone Min-Plus Product and n^{1.5+o(1)}-time algorithm for Monotone Min-Plus Convolution, derandomizing prior randomized results.
-
Shuffling-Aware Optimization for Private Vector Mean Estimation
Using the shuffle index, the authors formulate and solve an optimization problem for post-shuffle minimax-optimal unbiased mean estimation, yielding an asymptotically optimal mechanism whose privacy-utility tradeoff approaches the central Gaussian mechanism in the high-privacy regime.
-
Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
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.
-
Structural Liveness of Conservative Petri Nets
Structural liveness of conservative Petri nets is EXPSPACE-complete because minimal live markings are at most doubly exponential in net size.
-
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.
-
Optimal Sparsifiers for Abelian Cayley Graphs
Every abelian Cayley graph admits an optimal O(ε^{-2} log |G|)-generator weighted Cayley spectral sparsifier, proved via a character-symmetry volume bound on a sparsification polytope.
-
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.
-
Online Connectivity Augmentation
Obtains a tight competitive ratio for the online Connectivity Augmentation Problem, improving prior bounds.
-
Maximizing Reachability via Shifting of Temporal Paths
Maximizing reachability in k-path temporal graphs via budgeted shifts is FPT when parameterized by k and b together or by k alone, but intractable in most other parameterizations with matching XP algorithms.
-
Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers
A non-interactive time-delayed publicly verifiable scheme for quantum computation compiled from private 2-round protocols via time-lock puzzles and commitments, proven secure in the quantum random oracle model with CRS.
-
Parameterized algorithms for $k$-Inversion
FPT algorithms exist for k-Inversion on tournaments (generalized), block graphs, and general digraphs via treewidth parameterization.
-
Fixed-parameter tractable computation of Reshetikhin--Turaev knot polynomials via tensor networks
Reshetikhin-Turaev knot polynomials are fixed-parameter tractable in the treewidth of the input diagram via tensor network contraction, yielding e^{O(sqrt n)} time.
-
Facial diagrams and cycle double cover
Studying twists of edges in embeddings of cubic graphs yields bounds on the number of singular edges.
- Adversarially Robust Approximate Furthest Neighbor
- Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD