{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:21Z","timestamp":1725490221797},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_11","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T10:52:26Z","timestamp":1188211946000},"page":"149-163","source":"Crossref","is-referenced-by-count":7,"title":["On the Approximation Resistance of a Random Predicate"],"prefix":"10.1007","author":[{"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM\u00a042, 1115\u20131145 (1995)","journal-title":"Journal of the ACM"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1007\/s000390050065","volume":"8","author":"T. Gowers","year":"1998","unstructured":"Gowers, T.: A new proof of Szemer\u00e9di\u2019s theorem for progressions of length four. Geometric and Functional Analysis\u00a08, 529\u2013551 (1998)","journal-title":"Geometric and Functional Analysis"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","volume":"11","author":"T. Gowers","year":"2001","unstructured":"Gowers, T.: A new proof of Szemer\u00e9di\u2019s theorem. Geometric and Functional Analysis\u00a011, 465\u2013588 (2001)","journal-title":"Geometric and Functional Analysis"},{"key":"11_CR4","first-page":"8","volume-title":"Proceedings of 39th Annual IEEE Symposium on Foundations of Computer Science","author":"V. Guruswami","year":"1998","unstructured":"Guruswami, V., Lewin, D., Sudan, M., Trevisan, L.: A tight characterization of NP with 3 query PCPs. In: Proceedings of 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, 1998, pp. 8\u201317. IEEE Computer Society Press, Los Alamitos (1998)"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Hast, G.: Beating a random assignment. KTH, Stockholm, Ph.D Thesis (2005)","DOI":"10.1007\/11538462_12"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of ACM\u00a048, 798\u2013859 (2001)","journal-title":"Journal of ACM"},{"key":"11_CR7","first-page":"740","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computation","author":"J. H\u00e5stad","year":"2005","unstructured":"H\u00e5stad, J.: Every 2-CSP allows nontrivial approximation. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computation, pp. 740\u2013746. ACM Press, New York (2005)"},{"key":"11_CR8","first-page":"767","volume-title":"Proceedings of 34th ACM Symposium on Theory of Computating","author":"S. Khot","year":"2002","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of 34th ACM Symposium on Theory of Computating, pp. 767\u2013775. ACM Press, New York (2002)"},{"key":"11_CR9","first-page":"379","volume-title":"CCC","author":"S. Khot","year":"2003","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: CCC. Proc. of 18th IEEE Annual Conference on Computational Complexity, pp. 379\u2013386. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"11_CR10","first-page":"191","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing","author":"A. Samorodnitsky","year":"2000","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP characterization of NP with optimal amortized query complexity. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 191\u2013199. ACM Press, New York (2000)"},{"key":"11_CR11","first-page":"11","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"A. Samorodnitsky","year":"2006","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables and PCPs. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 11\u201320. ACM Press, New York (2006)"},{"key":"11_CR12","first-page":"216","volume-title":"Conference record of the Tenth annual ACM Symposium on Theory of Computing","author":"T. Schaefer","year":"1978","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: Conference record of the Tenth annual ACM Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"11_CR13","unstructured":"Zwick, U.: Personal Communication"},{"key":"11_CR14","first-page":"201","volume-title":"Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"U. Zwick","year":"1998","unstructured":"Zwick, U.: Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In: Proceedings 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 201\u2013210. ACM Press, New York (1998)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T12:29:34Z","timestamp":1556800174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}