Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
In the circle-packed planar-doubling setting of Section 7, prove that the expected distance of simple random walk from its root at time t is at most t^α for some α<1/2. Is the optimal exponent α=d^-1 when volume grows like r^d?
Prove lower bounds on the size of Cutting Planes refutations for random k-CNF formulas; this is a long-standing open problem with recent progress.
Consider the q-Potts model or uniform q proper colorings on a general graph G. Is there a universal asymp nlog n lower bound on the mixing time uniform in the temperature? Is there always an frac nlog n2 lower bound?
For random groups at density D<1/2, do the simplest homologically essential closed surface subgroups have genus O(n/log n) as the relator length n tends to infinity?
Let M_n be the sample median, let θ and σ be the quantities in Theorem~, and suppose the setting of that theorem applies. Assume that D_i=O(1) for i∈1,2,3. Optimal-rate conjecture. sup_x∈mathdsRvertmathdsP(θ√n· M_nleqslantσ x)-Φ(x)vert≈…
Censoring for the Potts model Consider the q-state Potts model (say with q=3 for concreteness) and start from all green. Is it the case that deterministically censoring a sequence of spin flips can only increase the total variation…
For critical bond percolation on a high-dimensional box with free boundary conditions, determine the asymptotic order and limiting behavior of the largest cluster.
For i.i.d. first-passage percolation on Z^2, prove or disprove that boundary fluctuations have a Tracy–Widom limit and that the variance of the passage time from 0 to (n,0) has order n^2/3. Determine optimal computational bounds for…
Which stationary random point process on the plane is most remarkable mathematically, and how should the chaotic analytic zero process—whose points are the zeros of a Gaussian random entire function—be characterized relative to the Poisson…
Let K≥3, let the underlying graph be either a hypercube or a discrete torus, and let the initial configuration be any nonzero configuration of the K-type competing urn scheme. Single-survivor conjecture. The process has almost surely a…
Suppose θ_nX converges in distribution to X' on a separable metric path space. Is there a coupling characterization involving only a joint construction of X and X', rather than a whole family of copies? For example, can they be coupled so…
Can two simple random walks on Z^3 or Z^4, started at vertices at graph distance 10, be coupled so that their paths are disjoint with positive probability?
Let (a_ij)_i,j≤ n be real coefficients, and let (ε_ij)_1≤ i,j≤ n be independent symmetric random variables taking values in -1,1. For a random matrix, write |·| for its operator norm, and let |S|_p=( E|S|^p)^1/p. Rademacher matrix norm…
Consider two initial conditions for (T)ASEP corresponding to height functions h_1(x;t=0) and h_2(x;t=0) which can be random, but are independent of each other. Hydrodynamic theory says that if for i=1,2, ε^-1 h_i(ε^-1 x;t=0)→ barh(x;t=0)…
Can the dynamics of colored particles on a ring be recast in terms of an (affine) Hecke algebra structure?
It was recently shown that if λ, μ are N-tuples of positive integers, then the ratio of Schur polynomials s_λ / s_μ, when evaluated at N real variables with values in (0,1]^N (the “log-negative orthant”), is minimized at (1,…,1) if and…
Does there exist an absolute constant c>0 such that, for all ε>0 and n≥ 1, P(| S_n-E S_n| ≥ε)≤ 2exp(-cnε^2/t_f(δ)) , where t_f(δ)=sup_x∈Ωn≥ 0, |E_x f(X_n) -E_π f|≤δ ? Does it hold for δ=1/4?
By contrast, it is a long-standing open problem to find the largest product-free subset of An . The largest product-free subsets of the alternating groups Peter Keevash (joint work with Noam Lifshitz, Dor Minzer)
How does uncertainty (noise in labels or nonexact solutions) affect these results?
In the Poincaré disk, sample a Poisson process of intensity λ with respect to hyperbolic area, form its Voronoi tessellation, and color cells black or white independently with probability 1/2. For four boundary points defining opposite…