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

We present a new explicit construction of onesided bipartite lossless expanders of constant degree, with arbitrary constant ratio between the sizes of the two vertex sets. Our construction is simpler to state and analyze than the prior construction of Capalbo, Reingold, Vadhan, and Wigderson (2002).

We construct our ... more >>>

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