10 problems

Let a random parity-check code have length $n$, $m=n(1-R)$ parity checks, and arbitrary degree distributions. The adaptive LP decoding algorithm is the iterative algorithm that add…

Convergence conjecture. For $\kappa\to+\infty$, this randomized cyclic coordinate-ascent algorithm cannot get stuck at a suboptimal point and therefore converges to a maximum of th…

Let a linear-programming decoding scheme have pseudo-codewords with components $\sigma_i^{(k_*)}$, and define the estimated effective distance by … where the minimum is taken over…

Adaptive LP decoding conjecture. As $n$ increases, the algorithm converges with probability arbitrarily close to $1$ in at most $b1$ iterations and with at most $b2$ final parity-c…

Let $\mathcal C$ be a septenary all-ones single-parity-check code of length $d\geq 3$, and let $\mathcal P=\operatorname{conv}(\mathsf F_{\mathrm v}(\mathcal C))$. Let $\Theta_i$ f…

Let $\mathcal C$ be a quinary all-ones single-parity-check code of length $d\geq 3$, let $\mathcal P=\operatorname{conv}(\mathsf F_{\mathrm v}(\mathcal C))$, and let $\Theta(d)$ be…

Let an ACG-ALP decoder be applied to a quadratic residue code, and suppose that it declares a decoding failure. ACG-ALP proximity conjecture. The solution produced by the ACG-ALP d…

LP-threshold conjecture. The LP threshold of a spatially coupled ensemble on the BSC is the same as that of the base ensemble.

Adaptive linear programming (ALP) decoding starts from a linear program containing box constraints and iteratively adds violated parity inequalities and box constraints, producing…

Consider a failed LP decoding instance with an identified critical loop, and select a special bit on that loop for a bit-local correction of the LP algorithm. Bit-local correction…