Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. (English) Zbl 1301.68152
Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 681-690 (2006).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C15 | Coloring of graphs and hypergraphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 11B75 | Other combinatorial number theory |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
NP-hard; approximation; chromatic number; clique; disperser; explicit construction; extractor; pseudorandomCitations:
Zbl 0989.68060; Zbl 0921.68089; Zbl 1145.11306; Zbl 1192.68468; Zbl 1192.68373; Zbl 1173.11310References:
| [1] | M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160:781-793, 2004. · Zbl 1071.11070 |
| [2] | M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in Logspace. In 19th STOC, pages 132-140, 1987. 10.1145/28395.28410 |
| [3] | N. Alon, U. Feige, A. Wigderson, and D. Zuckerman. Derandomized graph products. Computational Complexity, 5:60-75, 1995. 10.1007/BF01277956 · Zbl 0816.60070 |
| [4] | S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45:501-555, 1998. 10.1145/278298.278306 · Zbl 1065.68570 |
| [5] | B. Barak, R. Impagliazzo, and A. Wigderson. Extracting randomness using few independent sources. In 45th FOCS, pages 384-393, 2004. 10.1109/FOCS.2004.29 |
| [6] | B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson. Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors. In 37th STOC, pages 1-10, 2005. 10.1145/1060590.1060592 · Zbl 1192.68468 |
| [7] | M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs, and nonapproximability – towards tight results. SIAM Journal on Computing, 27(3):804-915, 1998. 10.1137/S0097539796302531 · Zbl 0912.68041 |
| [8] | M. Bellare and M. Sudan. Improved non-approximability results. In 26th STOC, pages 184-193, 1994. 10.1145/195058.195129 · Zbl 1344.68094 |
| [9] | R. Boppana and M. Halldorsson. Approximating maximum independent sets by excluding subgraphs. Bit, 32:180-196, 1992. 10.1007/BF01994876 · Zbl 0761.68044 |
| [10] | J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1:1-32, 2005. · Zbl 1173.11310 |
| [11] | J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric and Functional Analysis, 14:27-57, 2004. · Zbl 1145.11306 |
| [12] | B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988. 10.1137/0217015 · Zbl 0644.94008 |
| [13] | A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In 30th FOCS, pages 14-19, 1989. |
| [14] | H. Cramer. On the order of magnitude of the difference between consecutive prime numbers. Acta Arithmetica, pages 23-46, 1937. · Zbl 0015.19702 |
| [15] | Z. Dvir and R. Raz. An improved analysis of mergers. Technical Report TR05-025, Electronic Colloquium on Computational Complexity, 2005. |
| [16] | L. Engebretsen and J. Holmerin. Towards optimal lower bounds for clique and chromatic number. Theoretical Computer Science, 299:537-584, 2003. 10.1016/S0304-3975(02)00535-2 · Zbl 1042.68046 |
| [17] | U. Feige. Randomized graph products, chromatic numbers, and the Lovasz θ function. Combinatorica, 17:79-90, 1997. · Zbl 0880.05032 |
| [18] | U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43:268-292, 1996. 10.1145/226643.226652 · Zbl 0882.68129 |
| [19] | U. Feige and J. Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57:187-199, 1998. 10.1006/jcss.1998.1587 · Zbl 0921.68089 |
| [20] | D. Gillman. A Chernoff bound for random walks on expander graphs. SIAM Journal on Computing, 27:1203-1220, 1998. 10.1137/S0097539794268765 · Zbl 0911.60016 |
| [21] | O. Goldreich. A sample of samplers – a computational perspective on sampling (survey). Technical Report TR97-020, Electronic Colloquium on Computational Complexity, 1997. |
| [22] | M. Halldorsson. A still better performance guarantee for approximate graph coloring. Information Processing Letters, 45:19-23, 1993. 10.1016/0020-0190(93)90246-6 · Zbl 0768.68043 |
| [23] | J. Håstad. Clique is hard to approximate within n1-ε. Acta Mathematica, 182:105-142, 1999. · Zbl 0989.68060 |
| [24] | J. Hastad and S. Khot. Query efficient PCPs with perfect completeness. In 42nd FOCS, pages 610-619, 2001. |
| [25] | R. Impagliazzo and D. Zuckerman. How to recycle random bits. In 30th FOCS, pages 248-253, 1989. |
| [26] | N. Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091-1106, 1995. 10.1145/210118.210136 · Zbl 0885.68117 |
| [27] | N. Kahale. Large deviation bounds for Markov chains. Combinatorics, Probability, and Computing, 6:465-474, 1997. 10.1017/S0963548397003209 · Zbl 0892.60080 |
| [28] | R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, New York, 1972. · Zbl 1467.68065 |
| [29] | S. Khot. Improved inapproximability results for MaxClique, Chromatic Number and Approximate Graph Coloring. In 42nd FOCS, pages 600-609, 2001. |
| [30] | S. Konyagin. A sum-product estimate in fields of prime order. Technical report, Arxiv, 2003. http://arxiv.org/abs/math.NT/0304217. |
| [31] | L. Lovasz. On the ratio of the optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975. · Zbl 0323.05127 |
| [32] | C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. Journal of the ACM, 41:960-981, 1999. 10.1145/185675.306789 · Zbl 0814.68064 |
| [33] | E. Mossel and C. Umans. On the complexity of approximating the VC dimension. Journal of Computer and System Sciences, 65:660-671, 2002. 10.1016/S0022-0000(02)00022-3 · Zbl 1059.68049 |
| [34] | N. Nisan and A. Ta-Shma. Extracting randomness: A survey and new constructions. Journal of Computer and System Sciences, 58:148-173, 1999. 10.1006/jcss.1997.1546 · Zbl 0943.68190 |
| [35] | N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996. 10.1006/jcss.1996.0004 · Zbl 0846.68041 |
| [36] | R. Raz. Extractors with weak random seeds. In 37th STOC, pages 11-20, 2005. 10.1145/1060590.1060593 · Zbl 1192.68373 |
| [37] | O. Reingold, R. Shaltiel, and A. Wigderson. Extracting randomness via repeated condensing. In 41st FOCS, pages 22-31, 2000. |
| [38] | A. Samorodnitsky and L. Trevisan. A PCP characterization of NP with optimal amortized query complexity. In 32nd STOC, pages 191-199, 2000. 10.1145/335305.335329 · Zbl 1296.68060 |
| [39] | R. Shaltiel. Recent developments in explicit constructions of extractors. Bulletin of the European Association for Theoretical Computer Science, 77:67-95, June 2002. · Zbl 1051.68070 |
| [40] | A. Ta-Shma, C. Umans, and D. Zuckerman. Loss-less condensers, unbalanced expanders, and extractors. In 33rd STOC, pages 143-152, 2001. 10.1145/380752.380790 · Zbl 1323.68263 |
| [41] | A. Ta-Shma and D. Zuckerman. Extractor codes. IEEE Transactions on Information Theory, 50:3015-3025, 2004. 10.1109/TIT.2004.838377 · Zbl 1298.94148 |
| [42] | A. Ta-Shma, D. Zuckerman, and S. Safra. Extractors from Reed-Muller codes. Journal of Computer and System Sciences, 2006. 10.1016/j.jcss.2005.05.010 · Zbl 1094.68036 |
| [43] | C. Umans. Hardness of approximating Σ2p minimization problems. In 40th FOCS, pages 465-474, 1999. |
| [44] | A. Wigderson and D. Xiao. A randomness-efficient sampler for matrix-valued functions and applications. In 46th FOCS, 2005. 10.1109/SFCS.2005.8 |
| [45] | A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125-138, 1999. · Zbl 0929.05075 |
| [46] | D. Zuckerman. General weak random sources. In 31st FOCS, pages 534-543, 1990. |
| [47] | D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367-391, 1996. · Zbl 0857.68121 |
| [48] | D. Zuckerman. Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11:345-367, 1997. 10.1002/(SICI)1098-2418(199712)11:4 · Zbl 0891.60100 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
