%0 Conference Paper
%B 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings
%D 1998
%T Improved bounds and algorithms for hypergraph two-coloring
%A Radhakrishnan,J.
%A Srinivasan, Aravind
%K algorithms
%K Application software
%K Approximation algorithms
%K bounds
%K computational geometry
%K Computer science
%K Contracts
%K Erbium
%K graph colouring
%K History
%K hypergraph two-coloring
%K Lab-on-a-chip
%K MATHEMATICS
%K n-uniform hypergraph
%K Parallel algorithms
%K Polynomials
%K probability
%X We show that for all large n, every n-uniform hypergraph with at most 0.7√(n/lnn)×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)×2n due to Beck (1978). We further generalize this to a “local” version, improving on one of the first applications of the Lovasz Local Lemma
%B 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings
%I IEEE
%P 684 - 693
%8 1998/11/08/11
%@ 0-8186-9172-7
%G eng
%R 10.1109/SFCS.1998.743519