Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PCP:
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

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

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

#### 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).
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

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

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

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

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

#### A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

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

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

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

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

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

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

TR17-080 | 1st May 2017
Joshua Brakensiek, Venkatesan Guruswami

#### The Quest for Strong Inapproximability Results with Perfect Completeness

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

TR17-147 | 3rd October 2017
Venkatesan Guruswami, Rishi Saket

#### Hardness of Rainbow Coloring Hypergraphs

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be ... more >>>

TR18-006 | 10th January 2018
Subhash Khot, Dor Minzer, Muli Safra

#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

TR18-050 | 15th March 2018
Irit Dinur, Oded Goldreich, Tom Gur

#### Every set in P is strongly testable under a suitable encoding

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

TR18-073 | 21st April 2018
Amey Bhangale

#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.
(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

TR18-078 | 23rd April 2018
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

#### Small Set Expansion in The Johnson Graph

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if
their intersection is of size t. The Johnson graph arises often ... more >>>

TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

#### Rainbow coloring hardness via low sensitivity polymorphisms

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

TR19-116 | 9th September 2019
Venkatesan Guruswami, Sai Sandeep

#### $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors

The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ ... more >>>

ISSN 1433-8092 | Imprint