Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For each of the three random labeled chip-firing protocols described in the source—uniformly choosing a legal firing move, uniformly choosing an unstable vertex and then a pair of chips there, or uniformly choosing a labeled stabilization…
On the bidirected complete n-vertex graph, is the expected number of length-i excursions in a uniform Eulerian circuit asymptotic to e^-i/n?
Let d_k(n) be the expected distance from the origin after taking n random steps from the origin in Z^k (conditional on no self intersections) - that is, a self-avoiding walk. Is it true that lim_n→ ∞fracd_2(n)n^1/2= ∞? Is it true that…
For every infinite, connected, vertex-transitive, cubic graph G, let c_n(G,v) denote the number of self-avoiding walks of length n starting at a vertex v, and let the connective constant be μ(G):=limsup_n→∞ c_n(G,v)^1/n. Then μ(G)≥φ, where…
If G is strongly amenable, can Bernoulli percolation on G×Z have infinitely many infinite clusters throughout a nondegenerate interval [p_1,p_2]? What if G is also assumed to have polynomial volume growth?
For arbitrary simply connected planar domains, identify the optimal universal constants C₁,C₂,C₃,C₄ and the geometry of extremal domains in the four inequalities relating, respectively, the Hardy integral to the distance-to-boundary…
Universal lower bound for Potts 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…
Does the ReCom transition function run in polynomial time? Or can it get stuck in configurations where it is very unlikely a random tree will be splittable? Can we at least show that such configurations are exponentially unlikely?
For learning-and-optimization (LEO) models, is deterministic optimality the appropriate goal, or is there a notion of statistical optimality that quantifies the probability that a solution is \epsilon-optimal; how should generalizability…
Let 1≤ p<2 and let M be a p-convex and 2-concave Orlicz function. A mean zero function f has independent copies equivalent in L_p to the unit vector basis of l_M when those copies are equivalent to that basis in L_p; uniqueness up to…
Show that there exists a geodesic g=(v_0,v_1,…) and a unit direction v such that v_k/|v_k| tends to v as k→∞.
Let C,c>0 be fixed constants. Let G be an n-vertex C-Ramsey graph, meaning that G has no clique or independent set of size Clog n. Let k satisfy cn≤ k≤ (1-c)n, and let X be the number of edges induced by a uniformly random k-vertex subset…
Let X_1,…, X_n be iid random vectors in R^d satisfying sup_x∈ R^dP(X_i=x)≤ α. A choice of weights w_i∈ -1,1 should exist such that, for all non-zero a_i∈ R and all x∈ R^d, P(X_1+…+X_n = x)≤ max_k∈ ZP(w_1U^α_1+…+w_nU^α_n=k). This is stated…
How to use deep learning to solve PDEs in the viscosity sense (Hamilton-Jacobi-Bellman and Isoacs equations, e.g.) where solutions are not classical and need a mechanism to select viscosity solution? learn the flux or directly approximate…
Delete each edge of the square lattice independently with probability q<1/2, condition the origin to lie in the infinite component, and let K_q be the deterministic asymptotic graph-metric ball shape in that component. Prove that, after…
Let S be a finite string of heads and tails, let s be its total number of heads and tails, and let E(S) denote the expected number of fair-coin flips needed to produce S. Assume S∉H^k,T^k. Powers-of-two conjecture. The expected value E(S)…
Let κ vdash n be a partition with Plancherel measure, and let λ_κ be the quantity defined in with parameter α>0. Let F_2 denote the distribution function defined by F_2(s)=exp(-∫_s^∞ (x-s)q(x)^2 dx), where q is the solution of the Painlevé…
Does the simple random walk on every family of vertex-transitive expander graphs exhibit total-variation cutoff, and can the comparison between the mixing times of the simple and non-backtracking random walks known for random regular…
Let (X_1,X_2,…) be an infinite exchangeable sequence, and let K_n be the number of distinct values among its first n terms. For m∈1,2,…,∞, let K_n,m be the number of distinct values in n independent samples from the uniform distribution on…
What is the exact recovery threshold for the Stochastic Block Model with a logarithm number of communities? Both computational and information theoretical.