Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Let X_1,…,X_k be independent random vectors taking values in R^n, and let p>n/n+2. Let Z_i be independent random vectors, each a scaled version of the generalized Gaussian Z^(p), such that h_p(X_i)=h_p(Z_i). Rényi entropy power conjecture.…
A general layered erasure channel has layers indexed by l∈1,…,q, and let Theorem 1 denote the theorem giving an outer bound on its capacity region. The moderate-interference conditions are denoted by (moderate:c1) and (moderate:c2).…
Let X and Z be zero-mean random variables, and for ρ∈[0,∞) let mmse(X,ρ) denote the minimum mean-square error in estimating X from a Gaussian-noise observation at signal-to-noise ratio ρ. MMSE transform injectivity conjecture. For all…
Let P>0, let f(q_1,q_2) denote the outage-probability expression obtained for a two-transmit-antenna, r-receive-antenna channel with nonnegative powers q_1,q_2, and define D=(q_1,q_2)∈[0,P]^2| q_1+q_2=P. Outage Probability Conjecture for…
Let S be a finite set of n items, with 0<d<n defective items, and let M(d,n) denote the minimum, over adaptive group-testing algorithms, of the worst-case number of tests needed to identify all defectives. Set r:=n/d. Hu–Hwang–Wang…
Let c_A(s,n) denote the relevant coefficient for symbol s∈S and index n. For a fixed n, compare the values c_A(s,n) as s ranges over S. Directional-modulation vulnerability conjecture. The closer the values of c_A(s,n) for all s∈S at the…
Let d be the block-wise feedback delay. A time-invariant scheme is specified by a vector x=[x_1,…,x_d] of non-negative integers satisfying ∑_i x_i=d, and transmits x_i linear combinations of the i lowest-index unseen packets in each block.…
Let (U,V)→ X→(Y,Z) be a Markov chain for a broadcast channel with binary input alphabet |X|=2. Define T_α(X):=max_p(u,v| x)α I(U;Y)+I(V;Z)-I(U;V), α≥1, and let C[f(X)] denote the upper concave envelope of f at p(x). Put barλ=1-λ.…
Let bara:=1-a and a*b:=a(1-b)+(1-a)b. Let α,ε,f,g∈(0,1), and define s by s:=frac(barε-ε)[log(α*ε)-log(barα*ε)]logα-logbarα. Define c by the two equivalent expressions in the source, with the quantities k, f*barg*ε, h, P_XY, and (hat X,hat…
Let v be a string, let L^m(v) denote the length of its shortest grammar, and let MDL(v) denote the MDL code for v. Let γ(n):=n f_1(n). Symmetrical-bound conjecture. There is an inequality |lenMDL(v)-γ(L^m(v))|≤ f_2(L^m(v)), where the…
Let m_u,m_w,e_u,e_w∈[0,1] satisfy H_2(m_u)≥ e_u and H_2(m_w)≥ e_w. Let φ and J be the functions defined in the paper. The explicit lower-bound conjecture. One has φ(frac1-|H_2^-1(e_u)-H_2^-1(e_w)|2,e_u+e_w/2)…
Consider the model on a regular tree of degree parameter d, with broadcast parameter θ, and a BMS survey channel W. Write P_e(W) for the survey error probability, and let WSM denote weak spatial mixing, namely convergence to zero of the…
Let p_1,p_2,… be a sequence of arbitrary discrete distributions presented adaptively over time. An online random sampling algorithm generates exact samples from these distributions using a stream of i.i.d. random bits as its entropy…
Let I(delta) denote the mutual information in the binary-tree broadcasting model, let δ_c be the critical channel parameter, and write δ=δ_c-τ with τ≪ 1. Mutual-information critical exponent conjecture. I(δ_c-τ)=frac4√2ln 2τ+o(τ) bit. This…
Let T be a regular tree or a Galton-Watson tree with Poisson offspring distribution, with root vertex ρ. Let (T,ρ,θ,W) denote the corresponding broadcast model with parameter 0<θ<1 and survey channel W, and let P_e(W) be the error…
For a prime-power alphabet size q≥2, an integer kernel dimension m≥2, and a parameter β∈(0,1), define g_0(x)=(x(1-x))^β. Concavity conjecture. The function overlineg_n(x) is concave on [0,1] for every n. If true, this would make the…
Let F, S, and a be positive integers with F≤ S. Denote by K_(F,2,S) the relevant placement delivery array parameter for these parameters. Additive bound conjecture. K_(F,2,F+a) = K_(F,2,F) + K_(F,2,a). This conjecture extends the preceding…
Let G_q be an alphabet of size q≥ 2, let t≥ 1 be fixed, and let C⊆ G_q^n. For X,Y∈ G_q^t× n, define the column Hamming distance by d_H(X,Y)=|j∈1,…,n:X_*,j≠ Y_*,j|, and define the t-th covering radius of C by R_t(C)=max_X∈ G_q^t× nmin_Y∈…
Let n users receive binary codewords of length ℓ, let C be the colluder set of size c, and let C' be the set of accused users under the decoder of Theorem 1. Let ε_1,ε_2>0 and replace the parameter γ in that theorem by γ' =…
Let α>1 and let n∈N. Write rm H_α(X_RSS), rm H_α(X^*_RSS), and rm H_α(X_SRS) for the Rényi information measures of perfect ranked set sampling, imperfect ranked set sampling, and simple random sampling data, respectively. Rényi information…