Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let G be a finite abelian group. For distributions on G, let f_G(x,y) denote the minimum possible entropy of the sum of two independent G-valued random variables whose entropies are x and y, respectively. The cases G=Z_2 and G=R illustrate…
Let XYZ be the distribution displayed in the source, depending on a parameter a. The candidate-distribution binarization conjecture. There exists a value a such that, for every binarization channel P_overlineX|X and P_overlineY|Y, there…
Let h,p,v∈R_+, let X_1^G~N(0,p) and let Z~N(0,v) be independent of X_1^G. Let X and X_1 be i.i.d. random variables with mean 0 and variance p. Strong Shamai–Laroia conjecture. For all such X and X_1, I(X;X+hX_1^G+Z)≤ I(X;X+hX_1+Z). The…
For α≥ 0, let h_α(p) be the binary Rényi entropy of order α. For functions g_1 and g_2, write g_1succ g_2 when there exists a convex function h such that g_1=h∘ g_2. Rényi relative-convexity conjecture. If α≥β≥ 0, then h_α(·)succ h_β(·).…
Let an input bit vector be transformed by the special invertible encoding matrix R described above, whose entries satisfy r_lm=1 when m=l or m=l+1, and are zero otherwise. The transformation maps the input to an output representation, and…
For every communication problem N in which analogue communication outperforms digital communication, define the ratio of analogue to digital capacity by fracanalogue capacitydigital capacity. Analogue-over-digital ratio conjecture. The…
Let X^n be uniformly distributed on -1,1^n, let Y^n be the output of a memoryless binary symmetric channel with crossover probability δ≤ 1/2, and let widetildeY^n=X^n⊕ W^n be a modified additive-noise output whose principal inertia…
Let V_n,k,P denote the empirical relative entropy statistic for a multinomial distribution with sample size n, alphabet size k, and distribution P. Let t be a real parameter satisfying 0≤ t<n. Centered gamma moment-generating-function…
For β>0, let the generalized Gaussian have density G_β,p(x)=α(1-β|x|^2)_+^1/(p-1), where β and alpha are chosen so that it integrates to one. Let X_j, j=1,…,n, be independent random variables with densities f_j, and let Z_j be independent…
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 k=2^n denotes a heap size that…
Let M be a binomially distributed or Poisson-distributed random variable, let P_0 be its distribution, and let G(M) be its G-transform, defined by assigning the signed square root of twice the divergence from P_0 according as the value is…
Let X be uniformly distributed on 0,1^n, let Y=BDC_d(X) be the output of the binary deletion channel with deletion probability d, and let D(X,Y) be the set of length-n strings compatible with X and Y. Let E_n=1/nElog|D(X,Y)|. Concentration…
Let n be a positive integer and let m be the input size. Define c_n(m)=|(x_1,…,x_n)∈llbracket 1;mrrbracket^n| f(x_1,…,x_n)=x_1|, where f is the auction-output function. Asymptotic form conjecture for c_n. There exists a positive rational…
Let R_n be the squared Reed–Muller code matrix, let U^n=R_nX^n, and let A_i denote the degree layer associated with row i. For indices i,j gin[n], write H(U_i| U^i-1,Y^n) for the corresponding conditional entropy. Twin-Reed–Muller…
Let X_1 and X_2 be independent random vectors taking values in R^n, and let p>n/n+2. Let Z^(p)_1 and Z^(p)_2 be independent random vectors drawn from g_β_p. Sharp two-summand Rényi entropy power conjecture. N_p(X_1+X_2)≥…
We consider the binary skew-symmetric broadcast channel with input X and outputs Y_1,Y_2. Let U,V be random variables such that (U,V)-X-(Y_1,Y_2) forms a Markov chain. Nair–Wang information inequality. For all such (U,V,X),…
For ρ and n, let 4G_ρ,n4 be the directed graph whose vertices are all Boolean functions of n variables, with a directed edge from each function f to its optimal predictor sgn T_ρf whenever they differ; if T_ρf is identically zero, set sgn…
Let [n]=1,…,n, let U(A) denote the uniform distribution on a finite set A, and let (f,g) be probabilistic strategies satisfying the correctness condition for correlated sampling. For positive integers n,a,b,ℓ with ℓ≥ 2 and n≥ a+b-ℓ,…
Let (S,Y,Z) be jointly distributed random variables. Write UI(S;Ybackslash Z) for unique information of Y about S relative to Z, and let S_↔ (S;Y |Z . ) denote the two-way secret key rate. Unique information lower-bound conjecture. The…
Let the Gaussian doubly-dirty multiple access channel have high signal-to-noise ratio and strong interference. Denote its sum capacity by C^sum and the sum rate of the best known single-letter characterization by R_BSL^sum, as defined by…