We show simple constant-round interactive proof systems for problems capturing the approximability, to within a factor of $\sqrt{n}$, of optimization problems in integer lattices; specifically, the closest vector problem (CVP), and the shortest vector problem (SVP). These interactive proofs are for the ``coNP direction''; that is, we give an interactive ... more >>>

We study the question of whether the class DisNP of disjoint pairs (A, B) of NP-sets contains a complete pair. The question relates to the question of whether optimal proof systems exist, and we relate it to the previously studied question of whether there exists a disjoint pair of NP-sets ... more >>>

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}. We extend our main result in several ways. For ... more >>>