All reports by Author Amnon Ta-Shma:

__
TR23-090
| 15th June 2023
__

Itay Cohen, Roy Roth, Amnon Ta-Shma#### HDX Condensers

__
TR22-149
| 7th November 2022
__

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma#### Approximating Iterated Multiplication of Stochastic Matrices in Small Space

__
TR22-078
| 8th May 2022
__

Dan Karliner, Amnon Ta-Shma#### Improved local testing for multiplicity codes

__
TR22-073
| 18th May 2022
__

Itay Kalev, Amnon Ta-Shma#### Unbalanced Expanders from Multiplicity Codes

__
TR22-028
| 23rd February 2022
__

Dan Karliner, Roie Salama, Amnon Ta-Shma#### The plane test is a local tester for Multiplicity Codes

Itay Cohen, Roy Roth, Amnon Ta-Shma

More than twenty years ago, Capalbo, Reingold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon ... more >>>

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

Dan Karliner, Amnon Ta-Shma

Multiplicity codes are a generalization of Reed-Muller codes which include derivatives as well as the values of low degree polynomials, evaluated in every point in $\mathbb{F}_p^m$.

Similarly to Reed-Muller codes, multiplicity codes have a local nature that allows for local correction and local testing.

Recently, the authors and ...
more >>>

Itay Kalev, Amnon Ta-Shma

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a basic building block in many constructions, and, in particular, is behind the state of the art extractor constructions.

We give an alternative construction that is based on ... more >>>

Dan Karliner, Roie Salama, Amnon Ta-Shma

Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order $s$. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a ... more >>>