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 ≈n1−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 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 ≈nO(ℓ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 to2−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.