More Like this

1. Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast

   https://doi.org/10.4230/LIPIcs.SoCG.2021.51  

   Laddha, Aditi; Vempala, Santosh S. (January 2021, ACM Symposium on Computational Geometry)

   Buchin, Kevin; Colin de Verdi\` (Ed.)

   The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case. 

   more » « less
2. Multitrees in Random Graphs

   https://doi.org/10.37236/10804  

   Frieze, Alan; Pegden, Wesley (January 2023, The Electronic Journal of Combinatorics)

   Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$. 

   more » « less
3. Identification of mixtures of discrete product distributions in near-optimal sample and time complexity

   Gordon, Spencer L; Jahn, Erik; Mazaheri, Bijan; Rabani, Yuval; Schulman, Leonard J (June 2024, Proceedings of Machine Learning Research)

   Agrawal, Shipra; Roth, Aaron (Ed.)

   We consider the problem of \emph{identifying,} from statistics, a distribution of discrete random variables $$X_1 \ldots,X_n$$ that is a mixture of $$k$$ product distributions. The best previous sample complexity for $$n \in O(k)$$ was $$(1/\zeta)^{O(k^2 \log k)}$$ (under a mild separation assumption parameterized by $$\zeta$$). The best known lower bound was $$\exp(\Omega(k))$$. It is known that $$n\geq 2k-1$$ is necessary and sufficient for identification. We show, for any $$n\geq 2k-1$$, how to achieve sample complexity and run-time complexity $$(1/\zeta)^{O(k)}$$. We also extend the known lower bound of $$e^{\Omega(k)}$$ to match our upper bound across a broad range of $$\zeta$$. Our results are obtained by combining (a) a classic method for robust tensor decomposition, (b) a novel way of bounding the condition number of key matrices called Hadamard extensions, by studying their action only on flattened rank-1 tensors. 

   more » « less
4. Lower bounds for incidences

   https://doi.org/10.1007/s00222-025-01331-2  

   Cohen, Alex; Pohoata, Cosmin; Zakharov, Dmitrii (March 2025, Inventiones mathematicae)

   Abstract Let$$p_{1},\ldots ,p_{n}$$ $p_1,\dots ,p_n$be a set of points in the unit square and let$$T_{1},\ldots ,T_{n}$$ $T_1,\dots ,T_n$be a set of$$\delta $$ $\delta$-tubes such that$$T_{j}$$ $T_j$passes through$$p_{j}$$ $p_j$. We prove a lower bound for the number of incidences between the points and tubes under a natural regularity condition (similar to Frostman regularity). As a consequence, we show that in any configuration of points$$p_{1},\ldots , p_{n} \in [0,1]^{2}$$ $p_1,\dots ,p_n\in {[0,1]}^2$along with a line$$\ell _{j}$$ ${\ell }_j$through each point$$p_{j}$$ $p_j$, there exist$$j\neq k$$ $j\ne k$for which$$d(p_{j}, \ell _{k}) \lesssim n^{-2/3+o(1)}$$ $d(p_j,{\ell }_k)\lesssim n^{-2/3+o\left(1\right)}$. It follows from the latter result that any set of$$n$$ $n$points in the unit square contains three points forming a triangle of area at most$$n^{-7/6+o(1)}$$ $n^{-7/6+o\left(1\right)}$. This new upper bound for Heilbronn’s triangle problem attains the high-low limit established in our previous work arXiv:2305.18253. 

   more » « less
5. On Ramsey numbers of hedgehogs

   https://doi.org/10.1017/s0963548319000312  

   Fox, Jacob; Li, Ray (January 2020, Combinatorics, Probability and Computing)

   Abstract The hedgehog H t is a 3-uniform hypergraph on vertices $$1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$$ such that, for any pair ( i , j ) with 1 ≤ i < j ≤ t , there exists a unique vertex k > t such that { i , j , k } is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog H t is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r ( H t ) = O ( t 2 ln t ). 

   more » « less