The importance of being biased. (English) Zbl 1192.68318
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 33-42, electronic only (2002).
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | R. Ahlswede and L. H. Khachatrian. The complete intersection theorem for systems of finite sets. European J. Combin., 18(2):125-136, 1997.]] 10.1006/eujc.1995.0092 · Zbl 0869.05066 |
| [2] | S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998.]] 10.1145/278298.278306 · Zbl 1065.68570 |
| [3] | S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, Jan. 1998.]] 10.1145/273865.273901 · Zbl 0903.68076 |
| [4] | R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics, 25:27-45, 1985.]] · Zbl 0557.90072 |
| [5] | M. Bellare, O. Goldreich, and M. Sudan. Free bits, PCPs, and nonapproximability-towards tight results. SIAM Journal on Computing, 27(3):804-915, June 1998.]] 10.1137/S0097539796302531 · Zbl 0912.68041 |
| [6] | M. Ben-Or and N. Linial. Collective coin flipping. ADVCR: Advances in Computing Research, 5, 1989.]] |
| [7] | M. Ben-Or, N. Linial, and M. Saks. Collective coin flipping and other models of imperfect randomness. In Combinatorics (Eger, 1987), pages 75-112. North-Holland, Amsterdam, 1988.]] · Zbl 0675.90107 |
| [8] | I. Benjamini, G. Kalai, and O. Schramm. Noise sensitivity of Boolean functions and applications to percolation. Inst. Hautes Études Sci. Publ. Math., (90):5-43 (2001), 1999.]] · Zbl 0986.60002 |
| [9] | M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to numerical problems. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (Baltimore, MD, 1990), volume 47, pages 549-595, 1993.]] 10.1145/100216.100225 · Zbl 0795.68131 |
| [10] | J. Bourgain and G. Kalai. Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal., 7(3):438-461, 1997.]] · Zbl 0982.20004 |
| [11] | L. Engebretsen and J. Holmerin. Clique is hard to approximate within n1-(1). In Automata, languages and programming (Geneva, 2000), pages 2-12. Springer, Berlin, 2000.]] · Zbl 0973.68079 |
| [12] | P. Erdös, C. Ko, and R. Rado. Intersection theorems for systems of finite sets. Quart. J. Math. Oxford Ser (2), 12:313-320, 1961.]] · Zbl 0100.01902 |
| [13] | P. Erdös and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc., 35: 85-90, 1960.]] · Zbl 0103.27901 |
| [14] | U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete. In Proc. 32nd IEEE Symp. on Foundations of Computer Science, pages 2-12, 1991.]] 10.1109/SFCS.1991.185341 |
| [15] | P. Frankl. The Erdöds-Ko-Rado theorem is true for n = ckt. In Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pages 365-375. North-Holland, Amsterdam, 1978.]] · Zbl 0401.05001 |
| [16] | E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27-35, 1998.]] · Zbl 0909.06008 |
| [17] | E. Friedgut and G. Kalai. Every monotone graph property has a sharp threshold. Proc. Amer. Math. Soc., 124(10):2993-3002, 1996.]] · Zbl 0864.05078 |
| [18] | E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 329-337, N.Y., Jan. 9-11 2000. ACM Press.]] · Zbl 0956.68108 |
| [19] | J. Håstad. Some optimal inapproximability results. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 1-10, El Paso, Texas, 4-6 May 1997.]] 10.1145/258533.258536 |
| [20] | J. Håstad. Clique is hard to approximate within n1-e. Acta Math., 182(1):105-142, 1999.]] · Zbl 0989.68060 |
| [21] | J. Kahn, G. Kalai, and N. Linial. The influence of variables on Boolean functions. In IEEE, editor, 29th annual Symposium on Foundations of Computer Science, October 24-26, 1988, New York, pages 68-80. IEEE Computer Society Press, 1988.]] |
| [22] | R. M. Karp. Reducibility among combinatorial problems. In Miller and Thatcher, editors, Complexity of Computer Computations, pages 85-103. Plenum Press, 1972.]] · Zbl 1467.68065 |
| [23] | S. Khot. Improved inapproximability results for Max-Clique, Chromatic Number and Approximate Graph Coloring. In Proc. 42nd IEEE Symp. on Foundations of Computer Science, 2001.]] |
| [24] | P. N. Klein, S. A. Plotkin, S. Rao, and E. Tardos. Approximation algorithms for steiner and directed multicuts. J. Algorithms, 22(2):241-269, 1997.]] 10.1006/jagm.1996.0833 · Zbl 0866.68072 |
| [25] | G. A. Margulis. Probabilistic characteristics of graphs with large connectivity. Problemy Peredači Informacii, 10(2):101-108, 1974.]] · Zbl 0322.05147 |
| [26] | B. Monien and E. Speckenmeyer. Some further approximation algorithms for the vertex cover problem. In G. Ausiello and M. Protasi, editors, Proceedings of the 8th Colloquium on Trees in Algebra and Programming (CAAP’83), volume 159 of LNCS, pages 341-349, L’Aquila, Italy, Mar. 1983. Springer.]] · Zbl 0537.05053 |
| [27] | C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991.]] · Zbl 0765.68036 |
| [28] | R. Raz. A parallel repetition theorem. SIAM Journal on Computing, 27(3):763-803, June 1998.]] 10.1137/S0097539795280895 · Zbl 0911.68082 |
| [29] | R. Raz and S. Safra. A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In Proc. 29th ACM Symp. on Theory of Computing, pages 475-484, 1997.]] 10.1145/258533.258641 · Zbl 0963.68175 |
| [30] | L. Russo. An approximate zero-one law. Z. Wahrsch. Verw. Gebiete, 61(1):129-139, 1982.]] · Zbl 0501.60043 |
| [31] | L. Trevisan. Non-approximability results for optimization problems on bounded degree instances. In Proc. 33rd ACM Symp. on Theory of Computing, 2001.]] 10.1145/380752.380839 · Zbl 1323.90059 |
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.
