Radhakrishnan, J. ; Srinivasan, A. (1998) Improved bounds and algorithms for hypergraph two-coloring Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998 . pp. 684-693.
Full text not available from this repository.
Official URL: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumb...
Related URL: http://dx.doi.org/10.1109/SFCS.1998.743519
Abstract
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 n⅓-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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998. |
| ID Code: | 89519 |
| Deposited On: | 27 Apr 2012 13:36 |
| Last Modified: | 27 Apr 2012 13:36 |
Repository Staff Only: item control page
