Improved Bounds and Algorithms for Hypergraph Two-Coloring

We show that for all large n, every n-uniform hypergraph with at most 0.7 sqrt n/ln n x 2" edges can be 2-colored. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n sup (1/3-o(1)) x 2" due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma. We also present fast algorithms that output a proper 2-coloring with high probability for n-uniform hypergraphs with at most 0.7 sqrt n/ ln n x 2" edges, for all large n. In addition, we derandomize and parallelize these algorithms to derive NC sup 1 versions of these results.