{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:36Z","timestamp":1746331416806,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_57","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"689-700","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Somewhat Approximation Resistant Predicates"],"prefix":"10.1007","author":[{"given":"Subhash","family":"Khot","sequence":"first","affiliation":[]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[]},{"given":"Pratik","family":"Worah","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"57_CR1","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0097539701389944","volume":"34","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Ben-Sasson, E., Razborov, A.A., Wigderson, A.: Pseudorandom generators in propositional proof complexity. SIAM J. Comput.\u00a034(1), 67\u201388 (2005)","journal-title":"SIAM J. Comput."},{"key":"57_CR2","doi-asserted-by":"crossref","unstructured":"Alekhnovich, M., Razborov, A.: Lower Bounds for Polynomial Calculus: Non-Binomial Case. In: FOCS, pp. 190\u2013199 (2001)","DOI":"10.1109\/SFCS.2001.959893"},{"key":"57_CR3","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S.: A Characterization of Approximation Resistance for Even k-Partite CSPs (2012) (manuscript)","DOI":"10.1145\/2422436.2422459"},{"key":"57_CR4","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00037-009-0272-6","volume":"18","author":"P. Austrin","year":"2009","unstructured":"Austrin, P., Mossel, E.: Approximation Resistant Predicates from Pairwise Independence. Computational Complexity\u00a018, 249\u2013271 (2009)","journal-title":"Computational Complexity"},{"key":"57_CR5","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M.: Robust satisfiability of constraint satisfaction problems. In: STOC, pp. 931\u2013940 (2012)","DOI":"10.1145\/2213977.2214061"},{"issue":"4","key":"57_CR6","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00037-010-0293-1","volume":"19","author":"E. Ben-Sasson","year":"2010","unstructured":"Ben-Sasson, E., Impagliazzo, R.: Random CNFs are Hard for the Polynomial Calculus. Computational Complexity\u00a019(4), 501\u2013519 (2010)","journal-title":"Computational Complexity"},{"issue":"2","key":"57_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1145\/375827.375835","volume":"48","author":"E. Ben-Sasson","year":"2001","unstructured":"Ben-Sasson, E., Wigderson, A.: Short Proofs are Narrow \u2013 Resolution Made Simple. J. ACM\u00a048(2), 149\u2013169 (2001)","journal-title":"J. ACM"},{"key":"57_CR8","doi-asserted-by":"crossref","unstructured":"Bourgain, J.: On the Distribution of the Fourier Spectrum of Boolean Functions. Israel J. of Math., 269\u2013276 (2002)","DOI":"10.1007\/BF02785861"},{"key":"57_CR9","first-page":"110","volume":"19","author":"S.O. Chan","year":"2012","unstructured":"Chan, S.O.: Approximation Resistance from Pairwise Independent Subgroups. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 110 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"57_CR10","doi-asserted-by":"crossref","unstructured":"Charikar, M., Wirth, A.: Maximizing Quadratic Programs: Extending Grothendieck\u2019s Inequality. In: FOCS, pp. 54\u201360 (2004)","DOI":"10.1109\/FOCS.2004.39"},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., H\u00e5stad, J., Friedman, J., Rudich, S., Smolensky, R.: The Bit Extraction Problem of t-Resilient Functions. In: FOCS, pp. 396\u2013407 (1985)","DOI":"10.1109\/SFCS.1985.55"},{"issue":"1","key":"57_CR12","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E. Friedgut","year":"1998","unstructured":"Friedgut, E.: Boolean Functions With Low Average Sensitivity Depend On Few Coordinates. Combinatorica\u00a018(1), 27\u201335 (1998)","journal-title":"Combinatorica"},{"issue":"3","key":"57_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/S0196-8858(02)00024-6","volume":"29","author":"E. Friedgut","year":"2002","unstructured":"Friedgut, E., Kalai, G., Naor, A.: Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels. Advances in Applied Mathematics\u00a029(3), 427\u2013437 (2002)","journal-title":"Advances in Applied Mathematics"},{"key":"57_CR14","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Tulsiani, M.: Optimal Sherali-Adams Gaps from Pairwise Independence. In: APPROX-RANDOM, pp. 125\u2013139 (2009)","DOI":"10.1007\/978-3-642-03685-9_10"},{"key":"57_CR15","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Zhou, Y.: Tight bounds on the approximability of almost-satisfiable horn sat and exact hitting set. In: SODA, pp. 1574\u20131589 (2011)","DOI":"10.1137\/1.9781611973082.122"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Hast, G.: Beating a Random Assignment. PhD thesis, Royal Institute of Technology, Sweden (2005)","DOI":"10.1007\/11538462_12"},{"key":"57_CR17","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The Influence of Variables on Boolean Functions. In: FOCS, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"57_CR18","unstructured":"Kindler, G., Safra, S.: Noise-Resistant Boolean-Functions are Juntas (2004), http:\/\/www.cs.huji.ac.il\/~gkindler\/papers\/Papers.htm"},{"key":"57_CR19","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity\u00a04, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"key":"57_CR20","unstructured":"O\u2019Donnell, R.: Lecture notes for analysis of Boolean functions (2012), http:\/\/analysisofbooleanfunctions.org"},{"key":"57_CR21","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: A PCP Characterization of NP with Optimal Amortized Query Complexity. In: STOC, pp. 191\u2013199 (2000)","DOI":"10.1145\/335305.335329"},{"key":"57_CR22","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of Satisfiability Problems. In: STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"57_CR23","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G.: Linear Level Lasserre Lower Bounds for Certain k-CSPs. In: FOCS, pp. 593\u2013602 (2008)","DOI":"10.1109\/FOCS.2008.74"},{"key":"57_CR24","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Some Optimal Inapproximability Results. J. of the ACM, 798\u2013859 (2001)","DOI":"10.1145\/502090.502098"},{"key":"57_CR25","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: On the Efficient Approximability of Constraint Satisfaction Problems. In: Surveys in Combinatorics, vol.\u00a0346, pp. 201\u2013222. Cambridge University Press (2007)","DOI":"10.1017\/CBO9780511666209.008"},{"key":"57_CR26","doi-asserted-by":"crossref","unstructured":"Tulsiani, M.: CSP gaps and Reductions in the Lasserre Hierarchy. In: STOC, pp. 303\u2013312 (2009)","DOI":"10.1145\/1536414.1536457"},{"key":"57_CR27","first-page":"105","volume":"19","author":"M. Tulsiani","year":"2012","unstructured":"Tulsiani, M., Worah, P.: LS+ Lower Bounds from Pairwise Independence. Electronic Colloquium on Computational Complexity (ECCC)\u00a019, 105 (2012)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:09Z","timestamp":1746264669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}