We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let $r > 0$ be any integer. Given an inner code $\cC_0$ of length $d$, and a $d$-regular bipartite expander graph $G$ with $n$ vertices on each side, we give an algorithm to list-decode the expander code $\cC ... more >>>

One of the major open problems in proof complexity is to prove lower bounds on $AC_0[p]$-Frege proof
systems. As a step toward this goal Impagliazzo, Mouli and Pitassi in a recent paper suggested to prove
lower bounds on the size for Polynomial Calculus over the $\{\pm 1\}$ basis. In this ... more >>>

We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>>