Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>

Oded Goldreich

Various types of probabilistic proof systems have played

a central role in the development of computer science in the last decade.

In this exposition, we concentrate on three such proof systems ---

interactive proofs, zero-knowledge proofs,

and probabilistic checkable proofs --- stressing the essential

role of randomness in each ...
more >>>

Mihir Bellare, Oded Goldreich, Madhu Sudan

This paper continues the investigation of the connection between proof

systems and approximation. The emphasis is on proving ``tight''

non-approximability results via consideration of measures like the

``free bit complexity'' and the ``amortized free bit complexity'' of

proof systems.

The first part of the paper presents a collection of new ... more >>>

Adam Klivans, Dieter van Melkebeek

We establish hardness versus randomness trade-offs for a

broad class of randomized procedures. In particular, we create efficient

nondeterministic simulations of bounded round Arthur-Merlin games using

a language in exponential time that cannot be decided by polynomial

size oracle circuits with access to satisfiability. We show that every

language with ...
more >>>

Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan

We extend the notion of linearity testing to the task of checking

linear-consistency of multiple functions. Informally, functions

are ``linear'' if their graphs form straight lines on the plane.

Two such functions are ``consistent'' if the lines have the same

slope. We propose a variant of a test of ...
more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

We continue the investigation of interactive proofs with bounded

communication, as initiated by Goldreich and Hastad (IPL 1998).

Let $L$ be a language that has an interactive proof in which the prover

sends few (say $b$) bits to the verifier.

We prove that the complement $\bar L$ has ...
more >>>

Boaz Barak, Shien Jin Ong, Salil Vadhan

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... more >>>

Yael Tauman Kalai, Ran Raz

An interactive-PCP (say, for the membership $x \in L$) is a

proof that can be verified by reading only one of its bits, with the

help of a very short interactive-proof.

We show that for membership in some languages $L$, there are

interactive-PCPs that are significantly shorter than the known

more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Brendan Juba, Madhu Sudan

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

Graham Cormode, Justin Thaler, Ke Yi

Applications based on outsourcing computation require guarantees to the data owner that the desired computation has been performed correctly by the service provider. Methods based on proof systems can give the data owner the necessary assurance, but previous work does not give a sufficiently scalable and practical solution, requiring a ... more >>>

Gillat Kol, Ran Raz

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

Justin Thaler

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

Ryan Williams

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,

$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ...
more >>>

Baris Aydinlioglu, Eric Bach

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

Cynthia Dwork, Moni Naor, Guy Rothblum

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

Omer Reingold, Ron Rothblum, Guy Rothblum

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

Jason Li, Ryan O'Donnell

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where

the verifier is guaranteed with high probability to output the same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Andrew Drucker

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some $[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>>