In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance \frac{1-\varepsilon}{2} and rate \Omega\bigl(\varepsilon^{2+o(1)}\bigr) and thus it almost achieves the Gilbert-Varshamov bound, except for the o(1) term in the exponent. The prior best list-decoding algorithm for (a variant of) ... more >>>

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

In this note, we show the mixing of three-term progressions (x, xg, xg^2) in every finite quasirandom group, fully answering a question of Gowers. More precisely, we show that for any D-quasirandom group G and any three sets A_1, A_2, A_3 \subset G, we have
\[ \left|\Pr_{x,y\sim G}\left[ x \in ... more >>>

In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either ... more >>>