Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Random walk on monotone subsets of 0,1^n Let A⊂ 0,1^n be a monotone subset of the hypercube: for all x∈ A, if y satisfies y_i≥ x_i for all 1≤ i≤ n, then y∈ A. The random walk picks a coordinate at random, flip it, and accepts the move only…
Let D be a bounded, simply connected domain containing the origin whose boundary is a Jordan curve, and let U,V be disjoint, closed subarcs of ∂ D. For the lattice approximation A_n(D), boundary sets U_n,V_n, nearest-neighbor path set K_n,…
In the two-chunk deterministic-first-chunk peer-to-peer population process, the large-system-limit dynamical system is unstable while simulations suggest that the stochastic process is stable. Prove or disprove this stability conjecture,…
Let T_n be a uniform triangulation with n faces, and perform a critical site or bond percolation on T_n. For random variables, write X_n≈ n^α when, for every ε>0, the probability that n^α-ε<X_n<n^α+ε tends to 1 as n tends to infinity.…
Start from one edge and at each stage replace every edge independently by two edges in series with probability p or two edges in parallel with probability 1-p. For p>1/2, write EΔ_n=exp(nδ(p)+o(n)) for the endpoint distance Δ_n. Determine…
Let μ_n,d^S denote the Gibbs measure for integer-valued Lipschitz functions on the depth-n d-ary tree with boundary condition given by a finite set S⊂Z. Convergence conjecture. lim_n → ∞μ_n,2^S exists for all finite S. Also, lim_n →…
Can we prove ReCom mixes rapidly on some families of graphs? Triangular/square lattice? Complete graphs? Dense random graphs?
Let b∈ S^d-1 be a direction, let p∈(0,1) be the parameter, and let σ_b,p^2 denote the variance of the random billiard walk in direction b. Monotonicity conjecture. For every fixed b∈ S^d-1, σ_b,p^2 is monotone in p. Little is known about…
Let c4_N denote the distribution of the relevant finite planar triangulations, conditioned to have all vertex degrees bounded by M. Weak convergence conjecture. For every Mge 6, the distributions c4_N conditioned to have degrees uniformly…
Is it true that tropical RBMs always have expected dimension, meaning equal to the number of parameters within the model or the dimension of the ambient probability simplex?
For probability vectors x,y with nonzero coordinates, does Theorem 1 remain valid when the relation \prec_M replaces \prec_C?
Can strong smoothness assumptions on the probability distributions be used to overcome the curse of dimensionality in statistical estimation of optimal transport?
Prove or disprove the following conjecture by Feige : Given n independent random variables X_1,…,X_n s.t., for all i , X_i ≥ 0 and E X_i = 1 we have Prob( ∑_i=1^n X_i ≥ n+1 ) ≤ 1 - e^-1 .
For fixed p in (0,1) and triangle count X in G(n,p), how far can the known asymptotic equidistribution of X modulo q and its local limit theorem be extended beyond q=o(n^2/\log n)?
Polymer universality Consider intermediate scaling for polymer with β=n^-1/4c(n) where c(n) is any function which tends to infinity with n. Show universality of the F_GUE fluctuations with a fluctuation exponent which may depend on c(n).
Let λ∈D_n be a fixed partition, and let ε>0. For a uniformly random rook placement π~Unif(RP(N⊙λ)), write widetildeξ_π(t) for its rescaled profile and m_λ(t) for the limiting mean profile. Uniform convergence conjecture. P…
Let m be the recursion parameter and let X_0 be integer-valued. Assume the critical-regime condition (m-1)bf E(X_0m^X_0)=bf E(m^X_0)<∞. Conditional geometric-limit conjecture. Conditionally on X_n≠0, the random variable X_n converges…
Let B_1,…,B_n be independent Bernoulli random variables with parameters p_1,…,p_n∈[0,1], let S=∑_i=1^n B_i, and write P_k(p)=P_p(S=k). Determine the orders q>0 for which, for every n, the Rényi entropy H_q^R(S)=1/1-qlog (∑_k P_k(p)^q) and…
Let f:{0,1}^n\to{0,1} be a Boolean function, and call the probability that f remains undetermined after randomly assigning variables outside S the influence of S. If the expectation of f is bounded away from 0 and 1, is there a set S with…
For two independent coordinatewise partial orders generated by uniform points in the unit square, prove EC_n~ c n^1/3 and establish the existence or value of c∈(0,∞).