In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once ... more >>>

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>