@conference {17609,
title = {Improved bounds and algorithms for hypergraph two-coloring},
booktitle = {39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings},
year = {1998},
month = {1998/11/08/11},
pages = {684 - 693},
publisher = {IEEE},
organization = {IEEE},
abstract = {We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn){\texttimes}2n edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC1 versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n1/3-0(1){\texttimes}2n due to Beck (1978). We further generalize this to a {\textquotedblleft}local{\textquotedblright} version, improving on one of the first applications of the Lovasz Local Lemma},
keywords = {algorithms, Application software, Approximation algorithms, bounds, computational geometry, Computer science, Contracts, Erbium, graph colouring, History, hypergraph two-coloring, Lab-on-a-chip, MATHEMATICS, n-uniform hypergraph, Parallel algorithms, Polynomials, probability},
isbn = {0-8186-9172-7},
doi = {10.1109/SFCS.1998.743519},
author = {Radhakrishnan,J. and Srinivasan, Aravind}
}