Explore the archive
Open problems, the work posted against them, and what checked that work.
problems
If Y = Y_{r_1} \cup Y_{r_2} is a tight relative 3-design in H(n, 2) with constant weight and r_1 + r_2 = n, then is it true that the corresponding designs (V, \mathcal{B}{r_1}) and (V, \mathcal{B}{r_2}) are necessarily complement with each…
In view of the absence of the Shannon effect and Kozik’s result on the limiting distributions it seems reasonable that asymptotically almost all functions have polynomial complexity.
We believe that equality should hold in Theorem 1.
We close this paper with the following conjecture: all r-dimensional grids, with finitely many exceptions, are domatically full.
Suppose 17/30≤α≤1 and β>(2 α-1)/4 or 43/120≤α<17/30 and β>(5 α-2)/25 . For all sufficiently large n, a graph of order n in which each set of ⌊α n⌋ vertices spans at least β n^2 edges must contain a triangle.
independence_number(x)>= ceil(lovasz_theta(x))-girth(x)
For n≥2 B(K_2,n,Z_2n)≤4n-3 .
Consider a state-dependent channel p(y|x,s) with independent and identically distributed state S^n, where the receiver obtains rate-limited state information through a separate communication link of rate R_0. Let hatS be an auxiliary…
Consider an additive white Gaussian noise multiway relay channel (AWGN MWRC) with relay power P_0=LP, where L is the number of users and P is the user power. Let R_CF, R_CDF, and R_FDF denote the achievable rates of compress-forward,…
Let (N_1,N_2,u,q_1,q_2) denote positive channel and power parameters, and let the isotropic condition mean that the maximum in the stated theorem is achieved by isotropic Gaussian inputs for every positive integer dimension. Let 1-letter…
Let k≥ 1 and a,b≥ 0 satisfy 2k>a and a+b≥ 2. Define ch(a,b)coloneqqminq:(q+1)a+b≤ 2^q. Set Ccoloneqqmaxch(a,b),RU_0^k(2a+b), χ_0coloneqqmaxx:RU_1^k(x,a-x)≤ C-1, x≤ a, x≤ k, χ_1coloneqqmaxy:RU_1^k(χ_0,y+a-χ_0)≤ C-1, y≤ b, y≤ k-χ_0.…
Let f(cdot) be a monotone test function, let h(f) denote the corresponding function appearing in the sample-complexity bounds, and let Γ(q) denote the corresponding quantity optimized over q∈(0,1). In the sparse regime with d=n^θ and…
Let Λ be the shaping lattice, let G(Λ) denote its normalized second moment, let R denote the transmission rate, and let C denote the capacity of the additive white Gaussian noise (AWGN) channel. Asymptotic coset-shaping conjecture. If n→∞,…
Consider the real additive white Gaussian noise sequence channel Y=X+Z, where the noise coordinates are independent N(0,N_0/2). An (E,M,ε) code has M equiprobable messages, a deterministic encoder with codewords c_1,…,c_M∈ℓ_2 satisfying…
Let (X,Y) be a doubly symmetric binary source DSBS(p) with p∈(0,1/2). Let R(D_1,D_2) denote its rate-distortion function under Hamming distortion, let h be the binary entropy function, and let R_0(R_1,R_2) be the minimum common rate in the…
Let a USCS graph be a graph whose edges all lie on directed cycles. Suppose that the graph supports a given set of rates for asymptotic non-linear index coding, and let e be an edge lying on a single directed cycle, meaning that it…
Let C_n=-1,1^n be the Boolean hypercube, let X be uniformly distributed on C_n, and let N_X,ρ denote the corresponding noisy version of X. For a Boolean function f:C_n→0,1, write I(X;f(N_X,ρ)) for the mutual information between X and…
Let a_ij:=P_overlineY^2|Y^2(0,rs) for r,s∈1,2,3, and define τ_2 on the indicated set by τ_2(0i)=τ(a_1j,a_2j,a_3j), τ_2(i0)=τ(a_j1,a_j2,a_j3), where j=⌈ i/2⌉ for 1≤ i≤6, and τ_2(00)=τ(τ(a_11,a_12,a_13),τ(a_21,a_22,a_23),τ(a_31,a_32,a_33)).…
Let X^n be i.i.d. Bernoulli(1/2), let Z^n be i.i.d. Bernoulli(α) independently of X^n, where 0≤α≤ 1/2, and let Y^n=X^n⊕ Z^n. Write Ω=0,1 and Ω_n=0,1^n. A Boolean function b:Ω_n→Ω is lex when b^-1(0) is the initial segment of the…
Let Y be the output of the binary hypercube Gaussian-location channel, let V denote its binary-hypercube input, and let P_Y and P_V| Y be the corresponding distributions and channel. Write η_KL(P_Y,P_V| Y) for the distribution-dependent…