Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let h_n denote the normalized conditional entropy in the code ensemble, and let τ and ρ be the degree sequences appearing in Theorem 1. For each admissible random variable V, let φ_V be the corresponding trial-entropy functional. Under the…
Let N_q(n,2,t) denote the maximum, over pairs of distinct q-ary strings of length n, of the size of the intersection of their sets of length-n-t deletion traces. For qgeqslant 4 and sufficiently large n, define x=(0,1,2,0,1,w),…
Let bfΣ_1 and bfΣ_2 denote the channel covariance matrices, let ρ be the signal-to-noise ratio, and let R_sf weighted be the weighted ergodic sum-rate. Write sf Dom. eig(•) for the unit-norm dominant eigenvector operation, and let…
Let G be an undirected graph. Write gn(G) for its guessing number, let V(G) be its vertex set, and let κ_f(G) denote the fractional clique-cover number of G. Christofides–Markström conjecture. If G is an undirected graph then…
Let M_CII denote the model of causal information integration and let M_CIS denote the model of causal information structure, with M_CII⊆M_CIS. Approximation is understood with respect to the distribution space under consideration. Strict…
For every finite two-receiver discrete memoryless broadcast channel p_Y,Z| X, the capacity region equals the full Marton inner bound: C(p_Y,Z| X)=R_Marton(p_Y,Z| X).
Let an [n,k] MDS storage code store a database accessed by a Symmetric Private Information Retrieval scheme, with t-colluding servers, b Byzantine servers, and r unresponsive servers. Let M denote the number of messages. Symmetric PIR…
Let U and V be source variables, and let X and Y be target variables. Write C_GK(U;V) for the Gács–Körner common information of U and V. A target distribution p_XY is simulable from a source distribution p_UV when Alice and Bob, observing…
Let X_i and Y_i be independent Bernoulli random variables with parameters a_i and b_i, respectively, for i=1,…,n. Write H(a_1,…,a_n) for the entropy of ∑_i=1^n X_i. Shepp–Olkin conjecture. The function H(a_1,…,a_n) is concave in…
Let (a_n) be a sequence satisfying Benford's Law through equidistribution dynamics, and suppose the continued fraction of its rotation number is of bounded type, meaning that sup_k a_k<∞. Let β_eff(N) denote its effective…
Let X=[X_1 X_2]^intercal be a non-negative random vector whose components X_1 and X_2 are mutually independent and identically distributed. Let Y=[Y_1 Y_2 Y_3]^intercal∈Z_+^3 be jointly distributed with X, with conditional law as in (a).…
Let g be a measurable function describing a system with input X and output Y, and let h be another system function transforming input Y to output Z. Write l(X→Y), l(Y→Z), and l(X→Z) for the corresponding relative information losses.…
Let L=2^m with m≥ 3, and let L_k-m denote the log-likelihood ratio at bit position k-m. For each bf v_k-m+1^k∈0,1^m, let P_v_k-m=1, bf v_k-m+1^k be the path metric of the path beginning with v_k-m=1 and continuing with bf v_k-m+1^k, and…
Let k_α^A denote the Arimoto conditional-entropy function and let * denote binary convolution. There exists a value 1<hatα<1.5783 such that k_α^A(k_α^A^-1(x)* k_α^A^-1(y)) is convex for 0<α<1 and concave for 1<α≤hatα. This conjecture is…
Let Z=Z_n_n=1^∞ be a stationary ergodic process over a finite alphabet Z. Its Shannon entropy rate is H(Z)triangleq lim_n→∞H(Z_1^n)/n, and, when the limit exists, its α-th order Rényi entropy rate is H_α(Z)triangleq lim_n→∞fracH_α(Z_1^n)n.…
Let ω denote common randomness, with enough common randomness available—for example, ω ~ Unif[0,1]. For a fixed network setting, let underline C_p_0 be the strong coordination capacity region and let C_p_0 be the empirical coordination…
Let P_XYZ be a probability distribution. The Renner–Wolf conjecture. S(X:Y||Z)=I(X:Y downarrow downarrow Z). The reduced intrinsic information is a known upper bound on the secret-key rate and can be strictly smaller than the intrinsic…
Let S be a closed, discrete-time stochastic system over a state space X, and let its memory be M=M(S)=sup_tsup_μ I_X_t~μ(X_t;X_t+1), where the inner supremum ranges over all distributions μ on X and I(X_t;X_t+1) denotes Shannon mutual…
Let R^*(D) denote the infimum mutual-information rate over generalized causal reproductions GCR whose long-term distortion is at most D, and let R(D) denote the rate function obtained from the continuous-time linear Gaussian sensor…
Let Q_XY be a joint distribution on finite alphabets, and consider distributed hypothesis testing with null hypothesis H_0: P_XY=Q_XQ_Y and alternative hypothesis H_1: P_XY=Q_XY. An encoder observing X^n sends a message of rate at most R…