Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$ formed by the intersection of $k$ halfspaces, we prove that $$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k \cdot \Delta,$$ where $\Delta$ is ... more >>>

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

We initiate the study of the tradeoff between the {\em length} of a probabilistically checkable proof of proximity (PCPP) and the maximal {\em soundness} that can be guaranteed by a $3$-query verifier with oracle access to the proof. Our main observation is that a verifier limited to querying a short ... more >>>

We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate a value with distribution exactly D. Alice and Bob are allowed to share random bits generated ... more >>>

We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size $n$): We present PCPs of length $\exp(\tildeO(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ Boolean queries. ... more >>>

For a boolean formula \phi on n variables, the associated property P_\phi is the collection of n-bit strings that satisfy \phi. We prove that there are 3CNF properties that require a linear number of queries, even for adaptive tests. This contrasts with 2CNF properties that are testable with O(\sqrt{n}) queries ... more >>>

We present a simple proof of the bounded-depth Frege lower bounds of Pitassi et. al. and Krajicek et. al. for the pigeonhole principle. Our method uses the interpretation of proofs as two player games given by Pudlak and Buss. Our lower bound is conceptually simpler than previous ones, and relies ... more >>>

Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof ... more >>>