Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
An arbitrarily varying wiretap channel (AVWC) is a pair ( W, V) of finite arbitrarily varying channels, with legitimate channel family W and eavesdropper channel family V. Let C^mean_S,ran( W, V) denote its mean random secrecy capacity.…
Consider a Bayesian oversampled adaptive sensing setting with N samples, where hatd_n(Y_1) is the conditional distortion associated with the recovery of sample n after the first subframe. The sequence of these random variables is…
Let X and Y be random variables with distributions P_X and P_Y, and let P_X^n and P_Y^n denote their n-fold product distributions. Let H(X) and H(Y) be their entropies, and let G(P_X,P_Y) denote the maximal guessing coupling value.…
Let C be a small i-codebook, and let an OMRS codebook mean an i-codebook whose multiple-relay selection vectors are pairwise orthogonal in the source's coordinatewise sense. OMRS sufficiency conjecture. If C is an OMRS codebook, then…
Consider fully adversarial binary error channels without shared randomness, with noise rate epsilon→0. Let R denote the interactive channel capacity, namely the maximal asymptotically achievable communication rate. Adversarial binary…
Let G=F_p or G=R, let 0<ε<1/2, and let X and Y be independent discrete random variables taking values in G, under the hypotheses of Theorem 1. The theorem currently gives H(X+Y)≥ 1/2H(X)+1/2H(Y)+1/8-ε. Entropy sum lower-bound conjecture.…
Let (U,V) be auxiliary random variables and let X,Y_1,Y_2 be the input and outputs of the binary skew-symmetric channel with p=1/2, such that (U,V) → X → (Y_1,Y_2) is a Markov chain. Sum-rate conjecture. The following inequality holds:…
Let X^n~Unif(H^n), let Y^n be obtained by passing X^n through a binary symmetric channel with crossover probability p∈[0,1], and let V∈H be binary with X^n→ Y^n→ V forming a Markov chain. Define binary convolution by a* b=a(1-b)+(1-a)b,…
The vector Gaussian rate-distortion problem with variable side information under trace distortion, denoted textscRDTr, is considered together with its Minimax and Maximin lower bounds. Strict-separation conjecture. There exists an instance…
Let *DMC_[n],[n]^(s) denote the space of Shannon-equivalence classes of discrete memoryless channels with input and output alphabets [n]=1,…,n, embedded canonically in the corresponding space for larger alphabets. For integers n and m with…
Let K≥ 2 and let P denote the common SNR of a symmetric K-user Gaussian multiple access channel. For real numbers β_2,…,β_K satisfying |β_k|≥ 1, let tildeL be the matrix defined in the source. The condition of equal-amplitude diagonal…
Let X be uniformly distributed on 0,1^n, let Y be obtained from X through a binary symmetric channel with crossover probability 0<p<1/2, and let f:0,1^n→0,1 be balanced, meaning E[f(Y)]=1/2. Define T_pf(x)=P(f(Y)=1| X=x), let f_0 be a…
Let X and Y be independent and identically distributed log-concave random vectors taking values in R^d, and let h denote differential entropy. Folklore conjecture. The entropy increment h(X+Y)-h(X) is maximized when X and Y have…
For every integer n≥ 1, every Boolean function fcolon-1,1^n→-1,1, and every noise parameter ρ∈[0,1], let X be uniformly distributed on -1,1^n, let Z_1,…,Z_n be independent random variables with P(Z_i=1)=(1+ρ)/2 and P(Z_i=-1)=(1-ρ)/2,…
Let ρ satisfy 0≤ρ≤1, let b1∈[1,9], and let MaxStab_α(1/2) denote the maximal asymmetric b1-stability at mean 1/2. A dictator function is a Boolean function depending on one coordinate. Maximal asymmetric alpha-stability conjecture. For…
Let (M_1,X_1,Y_1) and (M_2,X_2,Y_2) be independent triples, and let UI be the TMXY-UI measure of unique information. The independent sums property is the identity UI(M_1,M_2:X_1,X_2backslash Y_1,Y_2)=UI(M_1:X_1backslash…
For k≥2, let ψ_k be the unique real root of (1-x)^k-x in [0,1], set φ_k=1-ψ_k and α_k=φ_k^k-1=frac1φ_k-1, and define the extended binary entropy function h and r_k(x)=h(x^k), s_k(x)=x^k-1h(x), f_k(x)=α_k r_k(x)-s_k(x). Binary entropy…
Let (Γ,Π,hatΣ) be a solution of the convex optimization in, with matrices F, G, H, and J as in Theorem. The matrix pair formed using the pseudoinverse hatΣ^† is (F+GΓhatΣ^†,H+JΓhatΣ^†). A matrix pair is detectable when the associated…
Let X_M be a hypergraphical source, and let R_SK denote the minimum communication rate required to achieve secret-key capacity. Theorem~ gives an upper bound on this rate for general hypergraphical sources, while Theorem~ gives the…
Let G∈F_q^ℓ×ℓ be any kernel, and let PD_1=1 denote the probability that the first distance-process value equals 1. Good D implies good varrho. For any kernel G∈F_q^ℓ×ℓ, PD_1=1<ℓ^-varrho. This bound is intended to control trajectories that…