Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
35 Dmitriy Zhuk
8 Pith papers cite this work, alongside 8 external citations. Polarity classification is still indexing.
8
Pith papers citing it
8
external citations · external index
representative citing papers
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
The second-best bilateral-trade mechanism always captures at least half of first-best gains from trade, and the ratio 1/2 is tight.
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.
Buyer-offering mechanisms with reserve prices achieve a 0.746-approximation to welfare in bilateral trade, surpassing fixed-price limits.
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.
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.
Local syndrome-based preprocessing accelerates BP decoders for quantum LDPC codes, delivering up to 10x speedup on the [[144,12,12]] code while maintaining or improving logical error rates.
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.
-
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
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
-
Second-Best Bilateral Trade is $1/2$ Efficient
The second-best bilateral-trade mechanism always captures at least half of first-best gains from trade, and the ratio 1/2 is tight.
-
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.
-
Welfare Maximization in Bilateral Trade: Improved Approximation Guarantees Beyond the Fixed Price Barrier
Buyer-offering mechanisms with reserve prices achieve a 0.746-approximation to welfare in bilateral trade, surpassing fixed-price limits.
-
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.
-
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.
-
Accelerating BP-based decoders for QLDPC Codes with Local Syndrome-Based Preprocessing
Local syndrome-based preprocessing accelerates BP decoders for quantum LDPC codes, delivering up to 10x speedup on the [[144,12,12]] code while maintaining or improving logical error rates.