Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Consider a variable-length feedback code with M=2^K messages, target error probability P_e, expected decoding time E[T], rate overlineR, channel capacity C, first-stage reliability quantity tildeC_1, and bounded one-step log-likelihood…
Let S be the set of pairs of random variables (U,W)∈(0,1)^2 with prescribed values of E[U], E[W], E[H_2(U)], and E[H_2(W)]. Define ζ(m_u,m_w,e_u,e_w)=inf_(U,W)∈Sfrac12E[(U-W)(J(W)-J(U))]. Let Ψ be the class of functions satisfying the…
Let s be a situation, let C_W(s) denote its causal or world complexity, and let C_D(s) denote its description complexity in Simplicity Theory (ST). Define unexpectedness by U(s)=C_W(s)-C_D(s). Bayes–Unexpectedness correspondence…
Let P_M be a stationary distribution with entropy H, let H_N denote the LAWS hit rate after N total queries, and let N_min be the per-node visit threshold. Phase transition in LAWS convergence. There exists N^*=Θ(N_min·2^H) such that H_N≈0…
Let P_X_k^+ and P_X_k^- denote the distributions of the observations at layer k conditioned on the source bit being 1 and 0, respectively. Fix δ∈(0,1/2), and suppose that every vertex with two inputs in the 2D regular grid uses the NAND…
For a binary r-hot codeword c of length n, view 1/rc as a distribution on Z/nZ and call it the reduced distribution of c, denoted by dist(c). For a code Ilongrightarrow C with codewords c_i and probabilities p_i, define its average minimal…
Consider either combinatorial nonadaptive group testing, where k uniformly randomly chosen items among n are defective, or probabilistic nonadaptive group testing, where each of the n items is independently defective with probability…
Let n≥ 2 independent arms have distributions X_i~N(μ_i,1), with μ_i∈[0,1] and a unique optimal arm *. Write Δ_i=μ_*-μ_i for i≠ *, H=∑_i≠ *Δ_i^-2, and, for each integer r≥ 0, let p_r=H^-1∑_i≠ *: 2^-(r+1)<Δ_i≤ 2^-rΔ_i^-2. Define…
Let W be a positive integer and let D be a symmetric, W-way DPI-additive divergence on bounded W-tuples of probability distributions. Write Δ_W=α∈[0,1]^W:∑_k=1^Wα_k=1 and let C_α denote the simplex-indexed divergence atom. A Borel measure…
Let P(s,k) denote the optimal block length of a PIR code with parameters s and k, and let N(s,k) denote the coding-theoretic lower bound. Set k=2^s-2. Asymptotic gap conjecture. lim_s→∞ (P(s,k)-N(s,k))=∞. This conjecture asserts that, for…
Let C_PF(N,P_T) denote the proportional fair capacity of a Gaussian broadcast channel with noise vector N and total power P_T. Let preceq denote the componentwise ordering of noise vectors. Monotonicity conjecture. If NpreceqN', then…
Let H(x):=-xlog x-(1-x)log(1-x) be the binary entropy. For real k≥ 1, let α_k∈(0,1) be the unique solution of α_k=frac1(1+α_k)^k-1. The entropy inequality for real exponents. For 0≤ x≤ 1, α_k H(x^k)≥ x^k-1H(x). Equality holds at x=0,…
Let widetilde D be a real-valued functional on bounded conditional W-tuples (π_|G,p_G) over a fixed Polish alphabet pair (X,G). Assume that widetilde D satisfies joint data-processing inequalities under main-system stochastic operators…
Let P_e(δ) denote the optimal reconstruction error probability in the binary-tree broadcasting model, let δ_c be the critical channel parameter, and write δ=δ_c-τ with τ≪ 1. Error-probability critical exponent conjecture.…
Let P(X,Y| A,B) be a strategy generated using active common randomness W by P(X,Y| A,B)=∑_W P(W| A,B)P(X| A,W)P(Y| B,W). Let L be the set of local strategies and NS the set of no-signaling strategies. Active common randomness means that…
Let A'_n i and S_n i be the index sets defined in the construction, with S_ntu001csubseteqmathcalA_n^textc, and let D_n=A'_ntu001ccupmathcalS_n. For i itu001cmathcalD_n, define J_i=I(W_i;W_D^(i)_n,W_D^textc_n,Y). Possible polarization…
Let H_x be the entropy of a position for an optimal search heuristic in chess, and let L be an optimally compressed endgame tablebase capable of returning the perfect result for any legal and reachable position. Entropy–tablebase bound.…
Let [L]=1,…,L and [L']=1,…,L'. Let W([L],[L']) denote the set of channels from [L] to [L'], let δ_i be the point mass at i, and let P^(K)([L]) denote the set of probability distributions on [L]^K invariant under coordinate permutations.…
For every pair of integers n,k satisfying 3≤ k≤ n-1, the optimal leading coefficient in the high-SNR maximum-likelihood error-probability expansion for SNR-dependent (n+k,n) AWGN spherical codes is conjectured to satisfy K_n+k,n^*=4k(k-1),…
Let N_k(p) denote the probability of winning from a heap of size k when each transmitted binary digit is independently erroneous with probability p. A move transmits the number of chips left in the heap, and the full-pile-removal move…