{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:04:52Z","timestamp":1750694692091},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_50","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"673-685","source":"Crossref","is-referenced-by-count":9,"title":["Small Clique Detection and Approximate Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Lorenz","family":"Minder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Vilenchik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"50_CR1","doi-asserted-by":"publisher","first-page":"1733","DOI":"10.1137\/S0097539794270248","volume":"26","author":"N. Alon","year":"1997","unstructured":"Alon, N., Kahale, N.: A spectral technique for coloring random 3-colorable graphs. SIAM Journal on Computation\u00a026(6), 1733\u20131748 (1997)","journal-title":"SIAM Journal on Computation"},{"issue":"3-4","key":"50_CR2","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W","volume":"13","author":"N. Alon","year":"1998","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Random Structures and Algorithms\u00a013(3-4), 457\u2013466 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"50_CR3","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, Chichester (1992)"},{"key":"50_CR4","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing Nash equilibria: Approximation and smoothed complexity. In: FOCS 2006: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, USA, pp. 604\u2013612 (2006)","DOI":"10.1109\/FOCS.2006.20"},{"key":"50_CR5","unstructured":"Conitzer, V., Sandholm, T.: Complexity Results about Nash Equilibria. In: 18th International Joint Conference on Artificial Intelligence, pp. 765\u2013771 (2003)"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: STOC 2006: Proceedings of the 38th annual ACM Symposium on Theory of computing, USA, pp. 71\u201378 (2006)","DOI":"10.1145\/1132516.1132527"},{"key":"50_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: STOC 2002: Proceedings of the 34th annual ACM Symposium on Theory of Computing, pp. 534\u2013543 (2002)","DOI":"10.1145\/509984.509985"},{"issue":"1","key":"50_CR8","doi-asserted-by":"publisher","first-page":"25","DOI":"10.4086\/toc.2007.v003a002","volume":"3","author":"U. Feige","year":"2007","unstructured":"Feige, U., Ofek, E.: Easily refutable subformulas of large random 3CNF formulas. Theory of Computing\u00a03(1), 25\u201343 (2007)","journal-title":"Theory of Computing"},{"issue":"1","key":"50_CR9","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior\u00a01(1), 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"issue":"4","key":"50_CR10","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M. Jerrum","year":"1992","unstructured":"Jerrum, M.: Large Cliques Elude the Metropolis Process. Random Structures and Algorithms\u00a03(4), 347\u2013359 (1992)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"50_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1008374125234","volume":"20","author":"A. Juels","year":"2000","unstructured":"Juels, A., Peinado, M.: Hiding Cliques for Cryptographic Security. Designs, Codes and Cryptography\u00a020(3), 269\u2013280 (2000)","journal-title":"Designs, Codes and Cryptography"},{"key":"50_CR12","doi-asserted-by":"crossref","unstructured":"Hazan, E., Krauthgamer, R.: How hard is it to approximate the best Nash equilibrium? In: ACM-SIAM Symposium on Discrete Algorithms, USA, pp. 720\u2013727 (2009)","DOI":"10.1137\/1.9781611973068.79"},{"issue":"2-3","key":"50_CR13","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L. Ku\u010dera","year":"1995","unstructured":"Ku\u010dera, L.: Expected Complexity of Graph Partitioning Problems. Discrete Applied Mathematics\u00a057(2-3), 193\u2013212 (1995)","journal-title":"Discrete Applied Mathematics"},{"key":"50_CR14","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: 4th ACM conference on Electronic commerce, USA, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"50_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-540-77105-0_8","volume-title":"Internet and Network Economics","author":"H. Tsaknakis","year":"2007","unstructured":"Tsaknakis, H., Spirakis, P.G.: An Optimization Approach for Approximate Nash Equilibria. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 42\u201356. Springer, Heidelberg (2007)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:15:47Z","timestamp":1558282547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}