Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Silas Richelson:

TR23-088 | 1st June 2023
Parker Newton, Silas Richelson, Chase Wilson

A High Dimensional Goldreich-Levin Theorem

In this work we prove a high dimensional analogue of the beloved Goldreich-Levin theorem (STOC 1989). We consider the following algorithmic problem: given oracle access to a function $f:\mathbb{Z}_q^m\rightarrow\mathbb{Z}_q^n$ such that ${\rm Prob}_{{\bf x}\sim\mathbb{Z}_q^m}\bigl[f({\bf x})={\bf Ax}\bigr]\geq\varepsilon$ for some ${\bf A}\in\mathbb{Z}_q^{n\times m}$ and $\varepsilon>0$, recover ${\bf A}$ (or a list of ... more >>>

TR22-069 | 28th April 2022
Silas Richelson, Sourya Roy

List-Decoding Random Walk XOR Codes Near the Johnson Bound

Revisions: 1

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

ISSN 1433-8092 | Imprint