The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>>

We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least $\tilde\Omega((\log n)(\log(1/\delta)))$ tests. This solves the open problem posed by Damaschke and Sheikh Muhammad.

more >>>

In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class $VP$ is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>>