We give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work ... more >>>

We give the simplest known algebraic proof of the PCP theorem, involving only ingredients like code concatenation, polynomial interpolation, and polynomial multiplication. Specifically, we prove that graph 3-coloring has a polynomial-sized proof that can be verified by a verifier tossing logarithmically many coins and querying a constant number of bits ... more >>>