Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
Consider a two-receiver memoryless broadcast channel with states and receiver message side information (RMSI), together with the corresponding channel without RMSI. Let a transmission scheme for the channel without RMSI be transformed by…
Let q=2, m=3, and l=2, and let the degraded CMLOBCs have channel matrices S^(i)=(ε_0^(i)J_7×1|ε_1^(i)S_21|ε_2^(i)I_7×7), with S_21 a stochastic incidence matrix of two-dimensional versus one-dimensional subspaces of F_2^3. The channel is…
Let X and Y be independent identically distributed real-valued random variables with a common log-concave density and finite differential entropy. Define F:[0,1]→R by F(t)=h(√1-t X+√t Y). The Ball–Nayar–Tkocz entropy concavity conjecture…
Let D(P) denote the relative entropy of a probability distribution P from the Poisson distribution with the same mean. Write bi(n,p) for the binomial distribution with parameters n and p, and nb(n,p) for the negative binomial distribution…
Consider a private-message AWGN broadcast channel with Q>3 receivers, ordered by noise levels as N_1≤ N_2≤…≤ N_Q. A group leader is the common subgraph obtained from a group of side-information graphs by removing all arcs from a stronger…
Let R_opS be the minimum communication rate required to achieve the secrecy capacity in the secret-key agreement model. A trusted helper is a user whose source is trusted and who is not initially active, a vocal active user communicates at…
Consider the 2-transmitter 2-receiver network setting of the paper's linear-subspace-ratio lemma. Let n∈ N, let f_1^(n),f_2^(n) be arbitrary encoding functions, let vecbf y_1^n and vecbf y_2^n be the corresponding received signals, and let…
An index coding problem consists of messages, receivers, and side-information constraints; the paper organizes its messages into alignment sets, with type-2 alignment sets subject to restricted internal conflicts. Rate 1/3 feasibility…
Let n∈N and let f^(n) be a log-concave probability density on R^n. Let D(f^(n)) denote its relative entropy with respect to the Gaussian density having the same mean and covariance matrix. Entropic form of the hyperplane conjecture. There…
Let M be a channel with second eigenvalue λ_2(M), and let T_b be the b-ary tree. The reconstruction problem is census-solvable when the root can be reconstructed from the empirical counts of the symbols at a level. Census non-solvability…
Let p range over [0,0.5], and define the 3D space curve C=(p,h(ε+p-2ε p),h(δ+p-2δ p))| p∈ [0,0.5]. Two-point convex-hull conjecture. Any point in the convex hull of C can be expressed as the convex combination of only two points belonging…
For every integer n≥ 2, let X=(X_1,…,X_n) be a centered Gaussian vector satisfying Var(X_i)=1 for every i. Let Z_1,…,Z_n be independent standard Gaussian random variables and set overlineZ=(Z_1+…+Z_n)/n. Then, for every t∈R, Pmax_i X_i≤ t≥…
An allocation distributes storage across n nodes, and its recovery delay is denoted by D; the parameters are the node count n, request rate λ, and threshold T. An allocation is symmetric when it treats the nodes identically. Symmetric…
For an n-party monotone access structure Γ⊆ 2^[n], let ℓ_Γ be the minimum, over all linear secret-sharing schemes for one-bit secrets realizing Γ, of the maximum number of bits in any party's share. Define L(n)=max_Γ⊆ 2^[n]ℓ_Γ. Determine…
Let U be the auxiliary random variable in the feedback-based collaborative secrecy encoding problem over binary symmetric channels. The preceding result establishes that U can be restricted without loss of optimality to a three-dimensional…
Let R_(b,k) denote the rate of a (b,k)-hashing scheme, with integers b≥ k>3. For j in the range 2≤ j≤ k-2, let b^underlinej+1 denote the falling factorial b(b-1)…(b-j). Generalized upper-bound conjecture. For b≥ k>3, R_(b,k) ≤ min_2 ≤ j ≤…
Let C_unif(d) be the maximum coding rate achievable by uniformly-random codes for the binary deletion channel with deletion probability d, and define d^*_unif:=supd∈[0,1]:C_unif(d)>0. Uniform-capacity threshold conjecture. d^*_unif=1.…
Let u_i be an unfrozen bit in a polar code, and consider any incorrect decoding path that survives at u_i. Under the Gaussian approximation, the path may continue through subsequent unfrozen bits u_i+1,…,u_N. Incorrect-path splitting…
Let X,Y,Z be jointly distributed, and let overlineX and overlineY be binary outputs of arbitrary binary output channels applied to X and Y. For N≥ 1, let X^N,Y^N,Z^N denote N independent copies and let overlineX^N,overlineY^N be binary…
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. Define E_∞=lim_n→∞1/nElog|D(X,Y)|.…