## Abstract

In this paper, we consider the problem of coloring a 3-colorable 3-uniform hypergraph. In the minimization version of this problem, given a 3-colorable 3-uniform hypergraph, one seeks an algorithm to color the hypergraph with as few colors as possible. We show that it is NP-hard to color a 3-colorable 3-uniform hypergraph with constantly many colors. In fact, we show a stronger result that it is NP-hard to distinguish whether a 3-uniform hypergraph with n vertices is 3-colorable or it contains no independent set of size δn for an arbitrarily small constant δ > 0. In the maximization version of the problem, given a 3-uniform hypergraph, the goal is to color the vertices with 3 colors so as to maximize the number of non-monochromatic edges. We show that it is NP-hard to distinguish whether a 3-uniform hypergraph is 3-colorable or any coloring of the vertices with 3 colors has at most 8/9 + ε fraction of the edges non-monochromatic where ε > 0 is an arbitrarily small constant. This result is tight since assigning a random color independently to every vertex makes 8/9 fraction of the edges non-monochromatic. These results are obtained via a new construction of a probabilistically checkable proof system (PCP) for NP. We develop a new construction of the PCP Outer Verifier. An important feature of this construction is smoothening of the projection maps. Dinur, Regev and Smyth [6] independently showed that it is NP-hard to color a 2-colorable 3-uniform hypergraph with constantly many colors. In the "good case", the hypergraph they construct is 2-colorable and hence their result is stronger. In the "bad case" however, the hypergraph we construct has a stronger property, namely, it does not even contain an independent set of size δn.

Original language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science - Proceedings |

Editors | D.C. Martin |

Pages | 23-32 |

Number of pages | 10 |

State | Published - 2002 |

Event | The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002 |

### Other

Other | The 34rd Annual IEEE Symposium on Foundations of Computer Science |
---|---|

Country/Territory | Canada |

City | Vancouver, BC |

Period | 11/16/02 → 11/19/02 |

## ASJC Scopus subject areas

- Hardware and Architecture