TR00-062 Authors: Venkatesan Guruswami, Johan HÃ¥stad, Madhu Sudan

Publication: 26th August 2000 15:18

Downloads: 1780

Keywords:

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 accepted by the verifier. The covering

complexity of PCP verifiers offers a promising route to getting

stronger inapproximability results for some minimization problems, and

in particular, (hyper)-graph coloring problems. We present a PCP

verifier for NP statements that queries only four bits and yet has a

covering complexity of one for true statements and a super-constant

covering complexity for statements not in the language. Moreover, the

acceptance predicate of this verifier is a simple Not-all-Equal check

on the four bits it reads. This enables us to prove that for {\em

any} constant c, it is NP-hard to color a 2-colorable 4-uniform

hypergraph using just c colors, and also yields a super-constant

inapproximability result under a stronger hardness assumption.