Parallel algorithm for matroid basis computation with O(n^{1/3} log^{1/3} n) round complexity, nearly matching the KUW lower bound.
Entropic independence I : Modified log- S obolev inequalities for fractionally log-concave distributions and high-temperature I sing models
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
years
2026 5verdicts
UNVERDICTED 5representative citing papers
Glauber dynamics for RFIM on bounded-degree graphs mixes in polynomial time w.h.p. under anti-concentrated random fields, with MLSI and weak Poincaré inequalities also established.
Sparse localization deduces entropic independence from sparse ℓ2-independence with explicit loss, yielding approximate entropy conservation for uniform independent sets of fixed size in bounded-degree graphs.
Proves polynomial mixing of Glauber dynamics at the antiferromagnetic two-spin uniqueness threshold and optimal logarithmic mixing for Swendsen-Wang dynamics on bounded-degree graphs, resolving a conjecture.
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.
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.
-
Glauber dynamics for random field Ising models on bounded degree graphs and MLSI
Glauber dynamics for RFIM on bounded-degree graphs mixes in polynomial time w.h.p. under anti-concentrated random fields, with MLSI and weak Poincaré inequalities also established.
-
Entropic independence via sparse localization
Sparse localization deduces entropic independence from sparse ℓ2-independence with explicit loss, yielding approximate entropy conservation for uniform independent sets of fixed size in bounded-degree graphs.
-
Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
Proves polynomial mixing of Glauber dynamics at the antiferromagnetic two-spin uniqueness threshold and optimal logarithmic mixing for Swendsen-Wang dynamics on bounded-degree graphs, resolving a conjecture.
-
Lower bound on the mixing time of $p$-spin glasses
Proves an exponential lower bound on the mixing time of Glauber dynamics for the p-spin glass at inverse temperatures above C ln(p)/p for large p, via energy landscape analysis with Gaussian decompositions and a bottleneck bound.