[1]   Noga Alon, Michael Krivelevich, and Benny Sudakov: Finding a large hidden clique in a random graph. Random Structures & Algorithms, 13(3-4):457–466, 1998. Preliminary version in SODA’98. [doi:10.1002/(SICI)1098-2418(199810/12)13:3/4¡457::AID-RSA14¿3.0.CO;2-W]

[2]   Per Austrin, Mark Braverman, and Eden Chlamtáč: Inapproximability of NP-complete variants of Nash equilibrium. In Proc. 14th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’11), pp. 13–25. Springer, 2011. [doi:10.1007/978-3-642-22935-0_2]

[3]   Hartwig Bosse, Jaroslaw Byrka, and Evangelos Markakis: New algorithms for approximate Nash equilibria in bimatrix games. Theoret. Comput. Sci., 411(1):164–173, 2010. Preliminary version in WINE’07. [doi:10.1016/j.tcs.2009.09.023]

[4]   S. Charles Brubaker and Santosh Vempala: Random tensors and planted cliques. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), pp. 406–419, 2009. [doi:10.1007/978-3-642-03685-9_31]

[5]   Xi Chen, Xiaotie Deng, and Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3):14:1–14:57, 2009. Preliminary versions in FOCS’06 by Chen and Deng and by Chen, Deng, and Teng. [doi:10.1145/1516512.1516516]

[6]   Vincent Conitzer and Tuomas Sandholm: Complexity results about Nash equilibria. In Proc. 18th Internat. Joint Conf. on Artificial Intelligence (IJCAI’03), pp. 765–771, 2003. Article accessible at IJCAI. [ACM:1630659.1630770]

[7]   Vincent Conitzer and Tuomas Sandholm: New complexity results about Nash equilibria. Games and Economic Behavior, 63(2):621–641, 2008. [doi:10.1016/j.geb.2008.02.015]

[8]   David P. Dailey: Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete. Discrete Mathematics, 30(3):289–293, 1980. [doi:10.1016/0012-365X(80)90236-8]

[9]   Constantinos Daskalakis, Aranyak Mehta, and Christos H. Papadimitriou: Progress in approximate Nash equilibria. In Proc. 8th ACM Conf. on Electronic Commerce (EC’07), pp. 355–358. ACM Press, 2007. [doi:10.1145/1250910.1250962]

[10]   Constantinos Daskalakis, Aranyak Mehta, and Christos H. Papadimitriou: A note on approximate Nash equilibria. Theoret. Comput. Sci., 410(17):1581–1588, 2009. Preliminary version in WINE’06. [doi:10.1016/j.tcs.2008.12.031]

[11]   Tomás Feder, Hamid Nazerzadeh, and Amin Saberi: Approximating Nash equilibria using small-support strategies. In Proc. 8th ACM Conf. on Electronic Commerce (EC’07), pp. 352–354, 2007. [doi:10.1145/1250910.1250961]

[12]   Uriel Feige and Robert Krauthgamer: The probable value of the Lovász–Schrijver relaxations for Maximum Independent Set. SIAM J. Comput., 32(2):345–370, 2003. [doi:10.1137/S009753970240118X]

[13]   Alan M. Frieze and Ravi Kannan: A new approach to the planted clique problem. In IARCS Ann. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’08), pp. 187–198. Schloss Dagstuhl, 2008. [doi:10.4230/LIPIcs.FSTTCS.2008.1752]

[14]   Drew Fudenberg and Jean Tirole: Game Theory. MIT Press, 1991.

[15]   Itzhak Gilboa and Eitan Zemel: Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1(1):80–93, 1989. [doi:10.1016/0899-8256(89)90006-7]

[16]   Elad Hazan and Robert Krauthgamer: How hard is it to approximate the best Nash equilibrium? SIAM J. Comput., 40(1):79–91, 2011. Preliminary version in SODA’09. [doi:10.1137/090766991]

[17]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58(301):13–30, 1963. [doi:10.1080/01621459.1963.10500830]

[18]   Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta: Playing large games using simple strategies. In Proc. 4th ACM Conf. on Electronic Commerce (EC’03), pp. 36–41. ACM Press, 2003. [doi:10.1145/779928.779933]

[19]   Lorenz Minder and Dan Vilenchik: Small clique detection and approximate Nash equilibria. In Proc. 13th Internat. Workshop on Randomization and Computation (RANDOM’09), pp. 673–685. Springer, 2009. [doi:10.1007/978-3-642-03685-9_50]

[20]   Christos H. Papadimitriou: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. System Sci., 48(3):498–532, 1994. [doi:10.1016/S0022-0000(05)80063-7]

[21]    Haralampos Tsaknakis and Paul G. Spirakis: An optimization approach for approximate Nash equilibria. Internet Mathematics, 5(4):365–382, 2008. Preliminary version in WINE’07. [doi:10.1080/15427951.2008.10129172]