All reports by Author Sourya Roy:

__
TR22-069
| 28th April 2022
__

Silas Richelson, Sourya Roy#### List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

__
TR22-004
| 3rd January 2022
__

Silas Richelson, Sourya Roy#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

__
TR21-142
| 1st October 2021
__

Amey Bhangale, Prahladh Harsha, Sourya Roy#### Mixing of 3-term progressions in Quasirandom Groups

__
TR19-117
| 4th September 2019
__

Silas Richelson, Sourya Roy#### Locally Testable Non-Malleable Codes

Revisions: 1

Silas Richelson, Sourya Roy

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 >>>

Silas Richelson, Sourya Roy

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 >>>

Amey Bhangale, Prahladh Harsha, Sourya Roy

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 >>>

Silas Richelson, Sourya Roy

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 >>>