Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with PCP:
TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

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

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

This paper shows finding the closest vector in a lattice
to be NP-hard to approximate to within any factor up to
$2^{(\log{n})^{1-\epsilon}}$ where
$\epsilon = (\log\log{n})^{-\alpha}$
and $\alpha$ is any positive constant $<{1\over 2}$.

more >>>

TR98-066 | 3rd November 1998
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming
closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for
membership in any NP language can be verified with a constant
number of accesses, and with an error probability exponentially
small in the ... more >>>

TR00-073 | 28th August 2000
Venkatesan Guruswami, Sanjeev Khanna

On the Hardness of 4-coloring a 3-colorable Graph

We give a new proof showing that it is NP-hard to color a 3-colorable
graph using just four colors. This result is already known (Khanna,
Linial, Safra 1992), but our proof is novel as it does not rely on
the PCP theorem, while the earlier one does. This ... more >>>

TR01-094 | 3rd December 2001
Jonas Holmerin

Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 - \epsilon

We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick ... more >>>

TR01-102 | 18th December 2001
Oded Goldreich

Using the FGLSS-reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs.

Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that

(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size ... more >>>

TR02-027 | 30th April 2002
Irit Dinur, Venkatesan Guruswami, Subhash Khot

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

TR02-050 | 5th August 2002
Oded Goldreich, Madhu Sudan

Locally Testable Codes and PCPs of Almost-Linear Length

Locally testable codes are error-correcting codes that admit
very efficient codeword tests. Specifically, using a constant
number of (random) queries, non-codewords are rejected with
probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial
core of PCPs. However, the relation is ... more >>>

TR04-046 | 4th June 2004
Eli Ben-Sasson, Madhu Sudan

Robust Locally Testable Codes and Products of Codes

We continue the investigation of locally testable codes, i.e.,
error-correcting codes for whom membership of a given word in the
code can be tested probabilistically by examining it in very few
locations. We give two general results on local testability:
First, motivated by the recently proposed notion of robust
probabilistically ... more >>>

TR04-060 | 22nd July 2004
Eli Ben-Sasson, Madhu Sudan

Simple PCPs with Poly-log Rate and Query Complexity

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

TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])

The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion ... more >>>

TR05-046 | 17th April 2005
Irit Dinur

The PCP theorem by gap amplification

Revisions: 1 , Comments: 3

Let C={c_1,...,c_n} be a set of constraints over a set of
variables. The {\em satisfiability-gap} of C is the smallest
fraction of unsatisfied constraints, ranging over all possible
assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the
satisfiability-gap of a constraint-system, with only a linear ... more >>>

TR05-086 | 14th August 2005
Dana Moshkovitz, Ran Raz

Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

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

TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>

TR06-121 | 14th September 2006
Charanjit Jutla

A Simple Biased Distribution for Dinur's Construction

TR07-026 | 21st November 2006
Dana Moshkovitz, Ran Raz

Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size

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

TR07-031 | 26th March 2007
Yael Tauman Kalai, Ran Raz

Interactive PCP

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

TR07-113 | 15th November 2007
Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, Lisa Zhang

Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs

In the undirected Edge-Disjoint Paths problem with Congestion
(EDPwC), we are given an undirected graph with $V$ nodes, a set of
terminal pairs and an integer $c$. The objective is to route as many
terminal pairs as possible, subject to the constraint that at most
$c$ demands can be routed ... more >>>

TR08-008 | 8th February 2008
Venkatesan Guruswami, Prasad Raghavendra

Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

TR08-064 | 11th July 2008
Or Meir

On the Efficiency of Non-Uniform PCPP Verifiers

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>

TR09-042 | 5th May 2009
Irit Dinur, Prahladh Harsha

Composition of low-error 2-query PCPs using decodable PCPs

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

TR09-059 | 2nd July 2009
Gábor Kun, Mario Szegedy


The well known dichotomy conjecture of Feder and
Vardi states that for every &#64257;nite family &#915; of constraints CSP(&#915;) is
either polynomially solvable or NP-hard. Bulatov and Jeavons re-
formulated this conjecture in terms of the properties of the algebra
P ol(&#915;), where the latter is ... more >>>

TR09-099 | 16th October 2009
Venkatesan Guruswami, Ali Kemal Sinop

Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

TR09-128 | 29th November 2009
Gillat Kol, Ran Raz

Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>

TR09-138 | 14th December 2009
Gillat Kol, Ran Raz

Bounds on 2-Query Locally Testable Codes with Affine Tests

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

TR10-112 | 15th July 2010
Subhash Khot, Dana Moshkovitz

NP-Hardness of Approximately Solving Linear Equations Over Reals

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>

TR10-185 | 2nd December 2010
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

Agnostic Learning of Monomials by Halfspaces is Hard

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

TR11-104 | 3rd August 2011
Or Meir

Combinatorial PCPs with efficient verifiers

Revisions: 3

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

TR11-112 | 10th August 2011
Dana Moshkovitz

The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

TR13-071 | 8th May 2013
Venkatesan Guruswami, Sushant Sachdeva, Rishi Saket

Inapproximability of Minimum Vertex Cover on $k$-uniform $k$-partite Hypergraphs

We study the problem of computing the minimum vertex cover on $k$-uniform $k$-partite hypergraphs when the $k$-partition is given. On bipartite graphs ($k=2$), the minimum vertex cover can be computed in polynomial time. For $k \ge 3$, this problem is known to be NP-hard. For general $k$, the problem was ... more >>>

TR13-085 | 13th June 2013
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

Constant rate PCPs for circuit-SAT with sublinear query complexity

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

TR13-134 | 25th September 2013
Or Meir

Combinatorial PCPs with Short Proofs

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

TR13-159 | 20th November 2013
Per Austrin, Venkatesan Guruswami, Johan Håstad

$(2+\epsilon)$-SAT is NP-hard

Revisions: 2

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width $w$ and the guarantee that there exists an assignment satisfying at least $g = \lceil \frac{w}{2}\rceil -1$ literals in each clause, it is NP-hard to find ... more >>>

TR14-012 | 27th January 2014
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

AM with Multiple Merlins

Revisions: 1

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

TR14-017 | 9th February 2014
Eli Ben-Sasson, Emanuele Viola

Short PCPs with projection queries

We construct a PCP for NTIME(2$^n$) with constant
soundness, $2^n \poly(n)$ proof length, and $\poly(n)$
queries where the verifier's computation is simple: the
queries are a projection of the input randomness, and the
computation on the prover's answers is a 3CNF. The
previous upper bound for these two computations was
more >>>

TR14-025 | 25th February 2014
Oded Goldreich, Tom Gur, Ilan Komargodski

Strong Locally Testable Codes with Relaxed Local Decoders

Locally testable codes (LTCs) are error-correcting codes
that admit very efficient codeword tests. An LTC is said to
be strong if it has a proximity-oblivious tester;
that is, a tester that makes only a constant number of queries
and reject non-codewords with probability that depends solely
on their distance from ... more >>>

TR14-051 | 12th April 2014
Subhash Khot, Rishi Saket

Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>

TR14-142 | 1st November 2014
Subhash Khot, Dana Moshkovitz

Candidate Lasserre Integrality Gap For Unique Games

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.
Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ... more >>>

TR15-085 | 23rd May 2015
Irit Dinur, Prahladh Harsha, Guy Kindler

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

TR16-001 | 9th January 2016
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs

Revisions: 1

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

TR16-007 | 23rd January 2016
Guy Kindler

Property Testing, PCP, andJuntas

Revisions: 1

The first part of this thesis strengthens the low-error PCP
characterization of NP, coming closer to the upper limit of the
conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over
$n$ variables can be tested for the property of depending ... more >>>

TR16-042 | 19th March 2016
Oded Goldreich, Tom Gur

Universal Locally Testable Codes

Revisions: 2

We initiate a study of ``universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTC $C:\{0,1\}^k \to \{0,1\}^n$ for a family of functions $\mathcal{F} = \{ f_i : \{0,1\}^k \to \{0,1\} \}_{i ... more >>>

TR16-073 | 7th May 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

Revisions: 1 , Comments: 1

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ... more >>>

TR16-077 | 12th May 2016
Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

TR16-124 | 12th August 2016
Subhash Khot

On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Revisions: 1 , Comments: 1

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about
Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in
a certain non-standard sense. A reduction that is sound in this non-standard sense
implies that ... more >>>

TR16-128 | 13th August 2016
Irit Dinur

Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>

TR16-149 | 23rd September 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

A security analysis of Probabilistically Checkable Proofs

Comments: 1

Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

TR16-192 | 25th November 2016
Oded Goldreich, Tom Gur

Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP

Revisions: 1 , Comments: 1

Universal locally testable codes (Universal-LTCs), recently introduced in our companion paper [GG16], are codes that admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. In this work, we initiate the study of the NP analogue of these codes, wherein the testing procedures ... more >>>

ISSN 1433-8092 | Imprint