{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T21:13:45Z","timestamp":1772313225065,"version":"3.50.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,26]],"date-time":"2017-10-26T00:00:00Z","timestamp":1508976000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Microsoft Research Faculty Fellowship"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1118083, CCF-1017403, CCF-1217256 and CCF-0905626"],"award-info":[{"award-number":["CCF-1118083, CCF-1017403, CCF-1217256 and CCF-0905626"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF Career","award":["CCF-1343104"],"award-info":[{"award-number":["CCF-1343104"]}]},{"name":"Alfred P. Sloan Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,11,8]]},"abstract":"<jats:p>\n                    We prove super-polynomial lower bounds on the size of linear programming relaxations for approximation versions of constraint satisfaction problems. We show that for these problems, polynomial-sized linear programs are no more powerful than programs arising from a constant number of rounds of the Sherali--Adams hierarchy. In particular, any polynomial-sized linear program for M\n                    <jats:sc>ax<\/jats:sc>\n                    C\n                    <jats:sc>ut<\/jats:sc>\n                    has an integrality gap of \u00bd and any such linear program for M\n                    <jats:sc>ax<\/jats:sc>\n                    3-S\n                    <jats:sc>at<\/jats:sc>\n                    has an integrality gap of \u215e.\n                  <\/jats:p>","DOI":"10.1145\/2811255","type":"journal-article","created":{"date-parts":[[2016,10,26]],"date-time":"2016-10-26T09:20:01Z","timestamp":1477473601000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Approximate Constraint Satisfaction Requires Large LP Relaxations"],"prefix":"10.1145","volume":"63","author":[{"given":"Siu On","family":"Chan","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong"}]},{"given":"James R.","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University"}]}],"member":"320","published-online":{"date-parts":[[2016,10,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652188"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a012"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884510"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.10"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746550"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-02-11331-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Y. Faenza S. Fiorini R. Grappe and H. R. Tiwary. 2011. Extended formulations non-negative factorizations and randomized communication protocols. (2011). arXiv:1105.4127.","DOI":"10.1007\/978-3-642-32147-4_13"},{"key":"e_1_2_1_11_1","unstructured":"H. Fawzi J. Saunderson and P. A. Parrilo. 2013. Equivariant semidefinite lifts and sum-of-squares hierarchies. (2013). arXiv:1312.6662."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283390"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213988"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/120877982"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_11"},{"key":"e_1_2_1_19_1","first-page":"46","article-title":"Approximate nonnegative rank is equivalent to the smooth rectangle bound","volume":"21","author":"Kol Gillat","year":"2014","unstructured":"Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff. 2014. Approximate nonnegative rank is equivalent to the smooth rectangle bound. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 21. 46.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"M. Laurent. 2003. A comparison of the sherali-adams lov\u00e1sz-schrijver and lasserre relaxations for 0-1 programming. Math. Oper. Res. (2003) 470--496. 10.1287\/moor.28.3.470.16391","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746599"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.10"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_25_1","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin.","author":"McDiarmid Colin","unstructured":"Colin McDiarmid. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin., Vol. 16. Springer, Berlin, 195--248."},{"key":"e_1_2_1_26_1","unstructured":"Pablo Parrilo. 2000. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. Ph.D. Dissertation. California Institute of Technology."},{"key":"e_1_2_1_27_1","unstructured":"K. Pashkovich. 2012. Extended Formulations for Combinatorial Polytopes. Ph.D. Dissertation. Magdeburg Universit\u00e4t."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591834"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_2_1_30_1","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency","author":"Schrijver Alexander","unstructured":"Alexander Schrijver. 2003. Combinatorial Optimization. Polyhedra and Efficiency. Vol. A. Algorithms and Combinatorics, Vol. 24. Springer-Verlag, Berlin."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/090773714"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1522486"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/500776"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","unstructured":"D. P. Williamson and D. B. Shmoys. 2011. The Design of Approximation Algorithms. Cambridge University Press Cambridge.","DOI":"10.5555\/1971947"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2811255","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2811255","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2811255","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:36:48Z","timestamp":1763458608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2811255"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,26]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11,8]]}},"alternative-id":["10.1145\/2811255"],"URL":"https:\/\/doi.org\/10.1145\/2811255","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,26]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}