Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
For the interacting spatial random-permutation model in dimension d\geq3, is the loss of probability mass into infinitely long cycles for an optimizer P of \chi^{(\leq)}(\beta,\rho) equivalent to…
For each n, let X be the number of Hamiltonian paths that are increasing in a uniformly random ordering of the edges of K_n. Log-normal limit conjecture. As n→∞, the normalized variable X/n converges in distribution to a log N(-1/2,1)…
Let m and n denote the card multiplicity and number of card types, respectively, and let S_m,n be the score under an optimal strategy with Yes/No feedback. Optimal score upper-bound conjecture. For all m and ε>0, if n is sufficiently large…
For sparse n-vertex graphs of average degree O(1) whose vertices have distinct O(log n)-length labels over a finite alphabet, construct universal codes analogous to Lempel–Ziv that achieve asymptotically optimal compression.
Let B(t) be standard Brownian motion, let M(t)=sup_0≤ s≤ tB(s), and let A=∫_0^1 M(t) dt. Write f_ A for the density function of A. Tail-density conjecture. The density satisfies f_ A(x)~ frac2· 3^1/6Γ(2/3)x^1/3e^-3x^2/2, x→∞. The preceding…
Noisy majority model The noisy majority model with parameter ε∈ (0,1) is a spin system on a graph G that is the stationary distribution of the following Markov chain on Ω=± 1^V(G): assign each vertex a rate-1 Poisson clock. When the clock…
The above construction can be generalized to any endomorphism of E defined over K. For the family of quadratic twists of E and p = 2, the elements of Sel2 (Ed /K) can be described more explicitly: they parametrize bi-quadratic extensions…
What are the critical points of the EM algorithm for RBM_3,2? Can the MLE degree for the strata of RBM_3,2 be determined?
Let cmu a be a probability measure on c0,1^n. It is CNC if every pair of disjoint increasing events is negatively correlated, and it is CNA if every pair of disjoint subsets of coordinates has negatively associated restrictions under…
Let (ε_n) be a martingale difference sequence satisfying the homogeneity condition E[ε_n+1^2| F_n]=σ^2 a.s. and assumption (H_p) introduced in the preceding theorem, for some integer p≥ 1. Define f_k, M_k, S_k-1, S_k, and d_n as in that…
Let F_{\Omega_n,T_n} be the DFT submatrix formed by independently retaining rows with probability 1-q and columns with probability 1-p. If p+q>1, is |F_{\Omega_n,T_n}|<\sqrt{p(1-q)}+\sqrt{q(1-p)}+\varepsilon with high probability, and if…
A positive random variable X is self-decomposable when its Laplace transform is E[e^-λ X]=exp[-∫_0^∞ (1-e^-λ u)k(u)/u du], λ≥ 0, where k:(0,+∞)→R^+ is non-increasing, after taking γ_0=0. Let f_k be the density associated with a…
Let d≥ 2, let (G_1,…,G_d) be a d-dimensional real-valued centered Gaussian vector, and let m≥ 1 be an integer. Gaussian Product Conjecture. One has E[G_1^2m… G_d^2m]≥∏_i=1^dE[G_i^2m]. This is an open problem and a natural real counterpart…
Let p_A and p_B be distinct win probabilities for the two arms of a slot machine, and let D be a nonrandom periodic pattern strategy with r≥ 1 consecutive plays of arm A and s≥ 1 consecutive plays of arm B. Write J for the number of arms…
What are the most efficient learning algorithms for training sparsely connected RBMs?
Exact solvability Investigate the relationship between the tropical RSK correspondence and mirror symmetry: The entrance law for the Markov process which arises from adding columns under the tropical RSK correspondence arises via a…
Does the random nearly-uniform transposition walk on S_n exhibit cutoff? What about in the simpler case where p_ij=p_ip_j for each 1≤ i,j≤ n?
Van Vu Roots of random functions: Recent progress and open questions . . . . . . . . The report passage is retained verbatim as the relevant context for this extracted problem.
Let b_N and k_N satisfy lim_N→∞b_NN/log k_N=β for some β∈(0,∞), with lim_N→∞k_N/N=0. Write T_rm mix^N,k_N(ε) for the mixing time of the weakly asymmetric simple exclusion process. Crossover-regime mixing-time conjecture. For every ε>0,…
Let M_n be a real random matrix satisfying the paper's Assumption with parameter K>0, possibly with some moment assumptions on its entries. For a deterministic matrix A∈R^n× n, let σ_n-k+1(A+M_n) denote the (n-k+1)-st singular value.…