Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, ... more >>>

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

In this paper we show that polynomial identity testing for
noncommutative circuits of size $s$, computing a polynomial in
$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm
with running time polynomial in $s$ and $n$. This answers a question
that has been open for over ten years.

The ... more >>>