This paper studies a generalization of multi-prover interactive proofs in which a verifier interacts with two competing teams of provers: one team attempts to convince the verifier to accept while the other attempts to convince the verifier to reject. Each team consists of two provers who jointly implement a no-signaling ... more >>>

The {\em hybrid argument}
allows one to relate
the {\em distinguishability} of a distribution (from
uniform) to the {\em
predictability} of individual bits given a prefix. The
argument incurs a loss of a factor $k$ equal to the
bit-length of the
distributions: $\epsilon$-distinguishability implies only
$\epsilon/k$-predictability. ... more >>>

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>