Change search
ReferencesLink to record
Permanent link

Direct link
Hardness of approximate hypergraph coloring
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2002 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 31, no 6, 1663-1686 p.Article in journal (Refereed) Published
Abstract [en]

We introduce the notion of covering complexity of a veri er for probabilistically checkable proofs (PCPs). Such a veri er is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The veri er is also given a random string and decides whether to accept the proof or not, based on the given random string. We de ne the covering complexity of such a veri er, on a given input, to be the minimum number of proofs needed to satisfy the veri er on every random string; i.e., on every random string, at least one of the given proofs must be accepted by the veri er. 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 veri er for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a superconstant covering complexity for statements not in the language. Moreover, the acceptance predicate of this veri er is a simple not-all-equal check on the four bits it reads. This enables us to prove that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption.

Place, publisher, year, edition, pages
2002. Vol. 31, no 6, 1663-1686 p.
Keyword [en]
graph coloring, hypergraph coloring, hardness of approximations, PCP, covering PCP, set splitting, lovasz local lemma, chromatic number, algorithms, graph
URN: urn:nbn:se:kth:diva-22056ISI: 000179328200002OAI: diva2:340754
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
SIAM journal on computing (Print)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 47 hits
ReferencesLink to record
Permanent link

Direct link