TY - CONF
T1 - Improved bounds and algorithms for hypergraph two-coloring
T2 - 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings
Y1 - 1998
A1 - Radhakrishnan,J.
A1 - Srinivasan, Aravind
KW - algorithms
KW - Application software
KW - Approximation algorithms
KW - bounds
KW - computational geometry
KW - Computer science
KW - Contracts
KW - Erbium
KW - graph colouring
KW - History
KW - hypergraph two-coloring
KW - Lab-on-a-chip
KW - MATHEMATICS
KW - n-uniform hypergraph
KW - Parallel algorithms
KW - Polynomials
KW - probability
AB - 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
JA - 39th Annual Symposium on Foundations of Computer Science, 1998. Proceedings
PB - IEEE
SN - 0-8186-9172-7
M3 - 10.1109/SFCS.1998.743519
ER -