@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} }