Luca Trevisan

We study query-efficient Probabilistically Checkable

Proofs (PCPs) and linearity tests. We focus on the number

of amortized query bits. A testing algorithm uses $q$ amortized

query bits if, for some constant $k$, it reads $qk$ bits and has

error probability at most $2^{-k}$. The best known ...
more >>>

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

In this paper we study program checking (in the

sense of Blum and Kannan) using constant-depth circuits as

checkers. Our focus is on the number of queries made by the

checker to the program being checked and we term this as the

query complexity of the checker for the given ...
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 >>>

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

We introduce the notion of covering complexity of a probabilistic

verifier. The covering complexity of a verifier on a given input is

the minimum number of proofs needed to ``satisfy'' the verifier on

every random string, i.e., on every random string, at least one of the

given proofs must be ...
more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>

Lars Engebretsen, Jonas Holmerin, Alexander Russell

An equation over a finite group G is an expression of form

w_1 w_2...w_k = 1_G, where each w_i is a variable, an inverted

variable, or a constant from G; such an equation is satisfiable

if there is a setting of the variables to values in G ...
more >>>

Lars Engebretsen, Jonas Holmerin

We study non-Boolean PCPs that have perfect completeness and read

three positions from the proof. For the case when the proof consists

of values from a domain of size d for some integer constant d

>= 2, we construct a non-adaptive PCP with perfect completeness

more >>>

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

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 >>>

Eli Ben-Sasson, Madhu Sudan

We give constructions of PCPs of length n*polylog(n) (with respect

to circuits of size n) that can be verified by making polylog(n)

queries to bits of the proof. These PCPs are not only shorter than

previous ones, but also simpler. Our (only) building blocks are

Reed-Solomon codes and the bivariate ...
more >>>

Luca Trevisan

We survey results on the hardness of approximating combinatorial

optimization problems.

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

an m-variate polynomial of total degree at most d

over F. The tester is usually given access to an oracle

A providing the supposed restrictions of f to

affine subspaces of ...
more >>>

Alex Samorodnitsky, Luca Trevisan

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)

of a function f: G -> \C, where G is a finite abelian group and \C are the

complex numbers. Roughly speaking, if a function has small Gowers uniformity

of dimension d, then it ``looks random'' on ...
more >>>

Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>

Or Meir

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

Dana Moshkovitz, Ran Raz

We show that the NP-Complete language 3Sat has a PCP

verifier that makes two queries to a proof of almost-linear size

and achieves sub-constant probability of error $o(1)$. The

verifier performs only projection tests, meaning that the answer

to the first query determines at most one accepting answer to the

more >>>

Jonathan Ullman, Salil Vadhan

Assuming the existence of one-way functions, we show that there is no

polynomial-time, differentially private algorithm $A$ that takes a database

$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way

marginals are approximately equal to those of $D$. (A two-way marginal is the fraction

of database rows ...
more >>>

Dieter van Melkebeek, Holger Dell

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>

Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

Irit Dinur, Venkatesan Guruswami

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... 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 >>>

Shuichi Hirahara, Naoto Ohsaka

Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at ... more >>>