**First Speaker:**Vijay Bhattiprolu

**Approximate Hypergraph Coloring under Low-discrepancy and Related Promises**

A hypergraph is said to be χ-colorable if its vertices can be colored with χ colors so that no hyperedge is monochromatic. 2-colorability is a fundamental property (called Property B) of hypergraphs and is extensively studied in combinatorics. Algorithmically, however, given a 2-colorable k-uniform hypergraph, it is NP-hard to find a 2-coloring miscoloring fewer than a fraction 2^{−k+1} of hyperedges (which is achieved by a random 2-coloring), and the best algorithms to color the hypergraph properly require ≈n^{1−1/k} colors, approaching the trivial bound of n as k increases.

In this work, we study the complexity of approximate hypergraph coloring, for both the maximization (finding a 2-coloring with fewest miscolored edges) and minimization (finding a 2-coloring with fewest miscolored edges) and minimization (finding a proper coloring using fewest number of colors) versions, when the input hypergraph is promised to have the following stronger properties than 2-colorability:

(A) Low-discrepancy: If the hypergraph has discrepancy ℓ≪√k, we give an algorithm to color the it with ≈n^O(ℓ^2/k) colors. However, for the maximization version, we prove NP-hardness of finding a 2-coloring miscoloring a smaller than 2^{−O(k)} (resp. k^{−O(k)}) fraction of the hyperedges when ℓ=O(logk) (resp. ℓ=2). Assuming the UGC, we improve the latter hardness factor to 2^{−O(k)} for almost discrepancy-1 hypergraphs.

(B) Rainbow colorability: If the hypergraph has a (k−ℓ)-coloring such that each hyperedge is polychromatic with all these colors, we give a 2-coloring algorithm that miscolors at most k^{−Ω(k)} of the hyperedges when ℓ≪√k, and complement this with a matching UG hardness result showing that when ℓ=√k, it is hard to even beat the 2^{−k+1} bound achieved by a random coloring.

*
Joint work with Venkatesan Guruswami and Euiwoong Lee.
*