7 problems

Let $G$ be a finite abelian group of size $N=|G|$, let $D\subseteq G$ be a random subset in which each element is present independently with probability $\rho$, and for $k\geq 3$ a…

Let a relaxed locally decodable code encode messages in $\{0,1\}^n$ as codewords in $\{0,1\}^m$, with a decoder making $q$ queries. For $q=2$, Gur and Lachish conjectured that the…

Let $\mathcal{C}_{r,p}(d)$ be the Type-$2$ constant for $2\leq p<\infty$, and let $E_{r,p}$ depend only on $r$ and $p$. Conjectured type-2 bound. One has … Moreover, the stronger i…

Adaptive weak Hamming RLDC lower-bound conjecture. The exponential lower bound $m=\exp(\Omega(n))$ should also hold for adaptive $2$-query weak Hamming RLDCs.

Let a $(k,\delta,\epsilon)$-locally decodable code encode an $n$-bit message as an $N$-bit codeword, where recovery of any message bit succeeds with probability at least…

Let $G=\mathbb{F}_p^n$ be a finite field vector space, and let $\rho_k$ denote the smallest density of a random difference set for which every subset of fixed positive density cont…

Exponential-length conjecture. The length $N$ of any constant-query LDC should have an exponential dependence on its message length $n$.