{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:22:13Z","timestamp":1750220533152,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T00:00:00Z","timestamp":1627516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union's Horizon 2020 research and innovation programme","award":["ERC-2014-CoG 648276"],"award-info":[{"award-number":["ERC-2014-CoG 648276"]}]},{"name":"MICCIN","award":["TIN2016-76573-C2-1P (TASSAT3)"],"award-info":[{"award-number":["TIN2016-76573-C2-1P (TASSAT3)"]}]},{"name":"Alan Turing Institute under the EPSRC","award":["EP\/N510129\/1"],"award-info":[{"award-number":["EP\/N510129\/1"]}]},{"name":"Marie Sk\u0142odowska-Curie","award":["795936"],"award-info":[{"award-number":["795936"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p>We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem.<\/jats:p>","DOI":"10.1145\/3456297","type":"journal-article","created":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T20:52:27Z","timestamp":1627591947000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Power of Symmetric Linear Programs"],"prefix":"10.1145","volume":"68","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joanna","family":"Ochremiak","sequence":"additional","affiliation":[{"name":"University of Bordeaux, CNRS, LaBRI, Talence, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,29]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.5555\/314613.315014"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.5555\/302908.303020"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1007\/s00224-016-9692-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/2822890"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1016\/j.tcs.2008.12.049"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 27th EACSL Conference on Computer Science Logic (CSL\u201918)","author":"Atserias Albert","year":"2018","unstructured":"Albert Atserias and Anuj Dawar . 2018 . Definable inapproximability: New challenges for duplicator . In Proceedings of the 27th EACSL Conference on Computer Science Logic (CSL\u201918) . 7:1\u20137:21. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2018.7 10.4230\/LIPIcs.CSL.2018.7 Albert Atserias and Anuj Dawar. 2018. Definable inapproximability: New challenges for duplicator. In Proceedings of the 27th EACSL Conference on Computer Science Logic (CSL\u201918). 7:1\u20137:21. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2018.7"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.5555\/3470152.3470201"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1137\/0209047"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/FOCS.2016.53"},{"unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. (2016). Retrieved from https:\/\/www.sumofsquares.org\/public\/index.html.  Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. (2016). Retrieved from https:\/\/www.sumofsquares.org\/public\/index.html.","key":"e_1_2_1_10_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/321105.321111"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1016\/S0168-0072(99)00005-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1145\/2811255"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.5555\/648043.745043"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1006\/inco.1998.2703"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/2728816.2728820"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.5555\/3329995.3330043"},{"key":"e_1_2_1_18_1","volume-title":"Dixon and Brian Mortimer","author":"John","year":"1996","unstructured":"John D. Dixon and Brian Mortimer . 1996 . Permutation Groups. Graduate Texts in Mathematics, Vol. 163 . Springer-Verlag New York . DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0731-3 10.1007\/978-1-4612-0731-3 John D. Dixon and Brian Mortimer. 1996. Permutation Groups. Graduate Texts in Mathematics, Vol. 163. Springer-Verlag New York. DOI:https:\/\/doi.org\/10.1007\/978-1-4612-0731-3"},{"volume-title":"Finite Model Theory","author":"Ebbinghaus Heinz-Dieter","unstructured":"Heinz-Dieter Ebbinghaus and J\u00f6rg Flum . 1995. Finite Model Theory . Springer . Heinz-Dieter Ebbinghaus and J\u00f6rg Flum. 1995. Finite Model Theory. Springer.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1137\/S009753970240118X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/788020.788896"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/1953122.1953150"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/800029.808532"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.2307\/421173"},{"volume-title":"Model Theory","author":"Hodges Wilfrid","unstructured":"Wilfrid Hodges . 1993. Model Theory . Cambridge University Press . DOI:https:\/\/doi.org\/10.1017\/CBO9780511551574 10.1017\/CBO9780511551574 Wilfrid Hodges. 1993. Model Theory. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/CBO9780511551574","key":"e_1_2_1_26_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/3178538"},{"doi-asserted-by":"publisher","key":"e_1_2_1_29_1","DOI":"10.1137\/0216051"},{"doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer.  Neil Immerman. 1999. Descriptive Complexity. Springer.","key":"e_1_2_1_30_1","DOI":"10.1007\/978-1-4612-0539-5"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916)","author":"Kolman Petr","year":"2016","unstructured":"Petr Kolman , Martin Kouteck\u00fd , and Hans Raj Tiwary . 2016 . Extension complexity, MSO logic, and treewidth . In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916) . 18:1\u201318:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.18 10.4230\/LIPIcs.SWAT.2016.18 Petr Kolman, Martin Kouteck\u00fd, and Hans Raj Tiwary. 2016. Extension complexity, MSO logic, and treewidth. In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm\u00a0Theory (SWAT\u201916). 18:1\u201318:14. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2016.18"},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_2_1_34_1","first-page":"337","article-title":"On graphs whose full automorphism group is an alternative group or a finite classical group. Proc. London","volume":"2","author":"Liebeck Martin W.","year":"1983","unstructured":"Martin W. Liebeck . 1983 . On graphs whose full automorphism group is an alternative group or a finite classical group. Proc. London Math. Soc. s3-47 , 2 (1983), 337 \u2013 362 . DOI:https:\/\/doi.org\/10.1112\/plms\/s3-47.2.337 10.1112\/plms Martin W. Liebeck. 1983. On graphs whose full automorphism group is an alternative group or a finite classical group. Proc. London Math. Soc. s3-47, 2 (1983), 337\u2013362. DOI:https:\/\/doi.org\/10.1112\/plms\/s3-47.2.337","journal-title":"Math. Soc. s3-47"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1137\/0801013"},{"key":"e_1_2_1_36_1","series-title":"Lecture Notes in Logic","volume-title":"Bounded Variable Logics and Counting: A Study in Finite Models","author":"Otto Martin","unstructured":"Martin Otto . 2017. Bounded Variable Logics and Counting: A Study in Finite Models . Lecture Notes in Logic , Vol. 9 . Cambridge University Press . DOI:https:\/\/doi.org\/10.1017\/9781316716878 10.1017\/9781316716878 Martin Otto. 2017. Bounded Variable Logics and Counting: A Study in Finite Models. Lecture Notes in Logic, Vol. 9. Cambridge University Press. DOI:https:\/\/doi.org\/10.1017\/9781316716878"},{"volume-title":"Computational Complexity","author":"Papadimitriou Christos H.","unstructured":"Christos H. Papadimitriou . 2007. Computational Complexity . Academic Internet Publishers . Christos H. Papadimitriou. 2007. Computational Complexity. Academic Internet Publishers.","key":"e_1_2_1_37_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1287\/moor.2014.0659"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/3127497"},{"volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 1999. Theory of Linear and Integer Programming . Wiley . Alexander Schrijver. 1999. Theory of Linear and Integer Programming. Wiley.","key":"e_1_2_1_40_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_41_1","DOI":"10.1137\/0403036"},{"doi-asserted-by":"publisher","key":"e_1_2_1_42_1","DOI":"10.5555\/524279"},{"doi-asserted-by":"publisher","key":"e_1_2_1_43_1","DOI":"10.5555\/2464831"},{"doi-asserted-by":"publisher","key":"e_1_2_1_44_1","DOI":"10.1145\/800070.802186"},{"doi-asserted-by":"publisher","key":"e_1_2_1_45_1","DOI":"10.1145\/212433.212474"},{"doi-asserted-by":"publisher","key":"e_1_2_1_46_1","DOI":"10.5555\/520668"},{"doi-asserted-by":"publisher","key":"e_1_2_1_47_1","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\/3456297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3456297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:58Z","timestamp":1750195498000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3456297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,29]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1145\/3456297"],"URL":"https:\/\/doi.org\/10.1145\/3456297","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2021,7,29]]},"assertion":[{"value":"2019-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}