{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T05:21:33Z","timestamp":1772083293175,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_10","type":"book-chapter","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T22:39:51Z","timestamp":1250807991000},"page":"125-139","source":"Crossref","is-referenced-by-count":12,"title":["Optimal Sherali-Adams Gaps from Pairwise Independence"],"prefix":"10.1007","author":[{"given":"Konstantinos","family":"Georgiou","sequence":"first","affiliation":[]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[]},{"given":"Madhur","family":"Tulsiani","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing","author":"M. Alekhnovich","year":"2005","unstructured":"Alekhnovich, M., Arora, S., Tourlakis, I.: Towards strong nonapproximability results in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, ACM Press, New York (2005)"},{"issue":"2","key":"10_CR2","doi-asserted-by":"publisher","first-page":"19","DOI":"10.4086\/toc.2006.v002a002","volume":"2","author":"S. Arora","year":"2006","unstructured":"Arora, S., Bollob\u00e1s, B., Lov\u00e1sz, L., Tourlakis, I.: Proving integrality gaps without knowing the linear program. Theory of Computing\u00a02(2), 19\u201351 (2006)","journal-title":"Theory of Computing"},{"key":"10_CR3","first-page":"249","volume-title":"IEEE Conference on Computational Complexity","author":"P. Austrin","year":"2008","unstructured":"Austrin, P., Mossel, E.: Approximation resistant predicates from pairwise independence. In: IEEE Conference on Computational Complexity, pp. 249\u2013258. IEEE Computer Society Press, Los Alamitos (2008)"},{"key":"10_CR4","volume-title":"STOC 2009","author":"M.H. Bateni","year":"2009","unstructured":"Bateni, M.H., Charikar, M., Guruswami, V.: MaxMin allocation via degree lower-bounded arborescences. In: STOC 2009. ACM Press, New York (2009)"},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.4086\/toc.2006.v002a004","volume":"2","author":"J. Buresh-Oppenheim","year":"2006","unstructured":"Buresh-Oppenheim, J., Galesi, N., Hoory, S., Magen, A., Pitassi, T.: Rank bounds and integrality gaps for cutting planes procedures. Theory of Computing\u00a02(4), 65\u201390 (2006)","journal-title":"Theory of Computing"},{"key":"10_CR6","volume-title":"STOC 2009","author":"M. Charikar","year":"2009","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Integrality gaps for Sherali-Adams relaxations. In: STOC 2009. ACM Press, New York (2009)"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chlamtac, E.: Approximation algorithms using hierarchies of semidefinite programming relaxations. In: FOCS: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 691\u2013701 (2007)","DOI":"10.1109\/FOCS.2007.72"},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-540-85363-3_5","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"E. Chlamtac","year":"2008","unstructured":"Chlamtac, E., Singh, G.: Improved approximation guarantees through higher levels of SDP hierarchies. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 49\u201362. Springer, Heidelberg (2008)"},{"key":"10_CR9","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-31856-9_16","volume-title":"STACS 2005","author":"L. Engebretsen","year":"2005","unstructured":"Engebretsen, L., Holmerin, J.: More efficient queries in pCPs for NP and improved approximation hardness of maximum CSP. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 194\u2013205. Springer, Heidelberg (2005)"},{"issue":"2","key":"10_CR10","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/S009753970240118X","volume":"32","author":"U. Feige","year":"2003","unstructured":"Feige, U., Krauthgamer, R.: The probable value of the Lov\u00e1sz-Schrijver relaxations for maximum independent set. SICOMP: SIAM Journal on Computing\u00a032(2), 345\u2013370 (2003)","journal-title":"SICOMP: SIAM Journal on Computing"},{"key":"10_CR11","unstructured":"de la Vega, W.F., Kenyon-Mathieu, C.: Linear programming relaxations of maxcut. In: SODA 2007: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 53\u201361. Society for Industrial and Applied Mathematics (2007)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2\u2009\u2212\u2009o(1) for Vertex Cover SDPs in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pp. 702\u2013712 (2007)","DOI":"10.1109\/FOCS.2007.35"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-540-85363-3_7","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"V. Guruswami","year":"2008","unstructured":"Guruswami, V., Raghavendra, P.: Constraint satisfaction over a non-boolean domain: Approximation algorithms and unique-games hardness. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol.\u00a05171, pp. 77\u201390. Springer, Heidelberg (2008)"},{"key":"10_CR14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-45535-3_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"J.B. Lasserre","year":"2001","unstructured":"Lasserre, J.B.: An explicit exact SDP relaxation for nonlinear 0-1 programs. In: Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol.\u00a02081, pp. 293\u2013303. Springer, Heidelberg (2001)"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/moor.28.3.470.16391","volume":"28","author":"M. Laurent","year":"2003","unstructured":"Laurent, M.: A comparison of the Sherali-Adams, Lov\u00e1sz-Schrijver, and Lasserre relaxations for 0-1 programming. Math. Oper. Res.\u00a028(3), 470\u2013496 (2003)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"10_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"10_CR17","unstructured":"Magen, A., Moharrami, M.: Sherali-Adams based polynomial approximation schemes for NP-hard problems on planar and minor-free graphs (manuscript) (2008)"},{"key":"10_CR18","volume-title":"STOC 2009","author":"C. Mathieu","year":"2009","unstructured":"Mathieu, C., Sinclair, A.: Sherali-Adams relaxations of the matching polytope. In: STOC 2009. ACM Press, New York (2009)"},{"key":"10_CR19","first-page":"191","volume-title":"Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000","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, STOC 2000, Portland, Oregon,, May 21-23, 2000, pp. 191\u2013199. ACM Press, New York (2000)"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and PCPs. In: STOC 2006, pp. 11\u201320 (2006)","DOI":"10.1145\/1132516.1132519"},{"key":"10_CR21","first-page":"593","volume-title":"FOCS","author":"G. Schoenebeck","year":"2008","unstructured":"Schoenebeck, G.: Linear level lasserre lower bounds for certain k-CSPs. In: FOCS, pp. 593\u2013602. IEEE Computer Society Press, Los Alamitos (2008)"},{"key":"10_CR22","first-page":"205","volume-title":"IEEE Conference on Computational Complexity","author":"G. Schoenebeck","year":"2007","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: A linear round lower bound for Lov\u00e1sz-Schrijver SDP relaxations of vertex cover. In: IEEE Conference on Computational Complexity, pp. 205\u2013216. IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"10_CR23","volume-title":"Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"G. Schoenebeck","year":"2007","unstructured":"Schoenebeck, G., Trevisan, L., Tulsiani, M.: Tight integrality gaps for Lov\u00e1sz-Schrijver LP relaxations of vertex cover and max cut. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007. ACM Press, New York (2007)"},{"issue":"3","key":"10_CR24","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"H.D. Sherali","year":"1990","unstructured":"Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math.\u00a03(3), 411\u2013430 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR25","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/11538462_20","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"I. Tourlakis","year":"2005","unstructured":"Tourlakis, I.: Towards optimal integrality gaps for hypergraph vertex cover in the Lov\u00e1sz-Schrijver hierarchy. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 233\u2013244. Springer, Heidelberg (2005)"},{"key":"10_CR26","first-page":"170","volume-title":"Proceedings of the 21st IEEE Conference on Computational Complexity","author":"I. Tourlakis","year":"2006","unstructured":"Tourlakis, I.: New lower bounds for vertex cover in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of the 21st IEEE Conference on Computational Complexity, pp. 170\u2013182. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"10_CR27","volume-title":"STOC 2009","author":"M. Tulsiani","year":"2009","unstructured":"Tulsiani, M.: CSP gaps and reductions in the Lasserre hierarchy. In: STOC 2009. ACM Press, New York (2009)"}],"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-642-03685-9_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T08:41:21Z","timestamp":1552120881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}