Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
2403.10985 introduced the notion of reversible capacity of a graph and showed that it is at most the Shannon capacity. It is conjectured there that the two values are equal. At the finite-length level, it is known to fail: the maximum…
Let m≥ 3 and let X_1,…,X_m be the inputs of an m-party computation, with ρ(∅,…,∅,X_1+…+X_m) denoting the relevant randomness measure when only the last party receives the summation. The real summation function conjecture.…
Consider the Poisson channel x[t] ≥ 0 longrightarrow y[t] ~ Pois(x[t]), with power constraint 1/n∑_t=1^n x[t] ≤ n^α. This is the Poisson channel with increasing power (PCIP). A normalized rate ρ>0 is achievable if, for every ε>0, one can…
An overparameterized neural network is a neural network with more parameters than are needed to fit its training data. A Neural Channel is a model that can approximately preserve its original behavior while efficiently storing and enabling…
Let N=2 and suppose the conditional densities of the observation Y given hypotheses H=0 and H=1 are f_Y| H(y| 0)=frac1√2πσ^2exp(-y^2/2σ^2), f_Y| H(y| 1)=frac1√2πσ^2exp(-(y-h_1)^2/2σ^2), where σ and h_1 are arbitrary positive numbers, and…
A polar code is decoded using a split-reduced successive cancellation list decoder, with u_i denoting the current unfrozen bit and P_e(u_i) its decoding error probability. Under the Gaussian approximation, consider a correct decoding path…
Let M be a binomially or Poisson-distributed random variable with G-transform G(M), and let Φ denote the standard Gaussian distribution function. The increasing property. The function mlongmapstoP(M=m)/Φ(G(m+1))-Φ(G(m)) is increasing,…
Consider the stochastic process defined by the Markov chain referenced in the source. Let the transformation described above act on a finite-length realization of this process, and let entropy be averaged over realizations of the process.…
Let x be a binary string of length m, and let κ^2(x) denote its autocorrelation coefficient. The alternating string is x=1010.... Alternating-string conjecture. The alternating string x=1010... minimizes the autocorrelation coefficient…
Let X,Y,Z be jointly distributed random variables, and let S(X:Y||Z) denote the secret-key rate and I(X:Y downarrow Z) the intrinsic information. The bound-secrecy conjecture. There exists a distribution P_XYZ such that I(X:Y downarrow…
Let P and Q be probability distributions, and let D_JS(P,Q) denote their classical Jensen–Shannon divergence. For alpha∈(1/2,1), consider the powered divergence [D_JS(P,Q)]^α. Conjecture on powers of the Jensen–Shannon divergence. The…
Let N be the number of possible outcomes in a uniform sample, and consider the bulleted procedure at the beginning of the subsection that generates tosses from this sample. Conditioning on N, let the expected number of generated tosses be…
Let h:[0,1]→R be a non-negative function, and let q>0 be a constant such that 2h(z)=q(h(z^2)+h(2z-z^2)) for every z∈[0,1]. QUP polar-code functional inequality. Then h(z_1)+h(z_2)≤ q(h(z_1z_2)+h(z_1+z_2-z_1z_2)) for every z_1,z_2∈[0,1].…
Let (x,y) be dependent Rademacher random variables taking values in -1,1, and let (x,y)=(x,y)^n consist of n independent, identically distributed copies. For a Boolean function fcolon-1,1^n→-1,1, Kumar–Courtade conjecture. I(f(x);y)≤…
Let P_M range over stationary distributions with entropy H, and let N be the number of queries. LAWS acquisition lower bound. No online inference caching algorithm can achieve acquisition cost o(2^H(P_M)·log N) expert creations in the…
For (u,w)∈(0,1)^2, define κ(u,w)=(u-w)(J(w)-J(u))/2-|u-w|J(L^-1(H_2(u)+H_2(w)/|u-w|)), with κ(u,u)=0. The kappa inequalities. The following two assertions hold: for u,w∈(0,1/2], κ(u,w)≤κ(1-u,w); and the function…
For q≥ 1, let ln_q:(0,+∞)→R be the q-logarithm ln_q(t):= fract^q-1-1q-1, q≠ 1, ln(t), q=1, and define Φ_q^sym(t)=tln_q(t)+(1-t)ln_q(1-t) and the associated symmetric q-stability by Stab_q^sym. A Boolean function f_d is a dictator function…
In the setting of the preceding proposition, consider a countable class of maps and the BIC penalty. BIC consistency conjecture. We almost surely have Property 2 from the proposition for the BIC penalty studied by Csiszár and Shields. This…
Consider a single-user MIMO Gaussian channel with t transmitting antennas and r receiving antennas, channel matrix H∈C^r× t, and covariance matrices Q≥ 0 satisfying tr(Q)≤ P. Let P_out(R,P) be the infimum of the outage probability over…
Let W be a channel from [ [1,2] ] to [ [1,n] ], and let S be the state space. Suppose W=∑_s∈Sp_S(s)K^(s), where S denotes the channel state. Causal state-information uselessness conjecture. If, for every 1≤ j≤ n, the two entries K^(s)_1,j…