{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:45Z","timestamp":1760202705205,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2015,12,10]],"date-time":"2015-12-10T00:00:00Z","timestamp":1449705600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/H026835"],"award-info":[{"award-number":["EP\/H026835"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,12,10]]},"abstract":"<jats:p>We show that the ellipsoid method for solving linear programs can be implemented in a way that respects the symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the program. In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed by Blass, Gurevich and Shelah [Blass et al. 1999]. On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected capacitated graphs.<\/jats:p>","DOI":"10.1145\/2822890","type":"journal-article","created":{"date-parts":[[2015,12,14]],"date-time":"2015-12-14T14:19:41Z","timestamp":1450102781000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Solving Linear Programs without Breaking Abstractions"],"prefix":"10.1145","volume":"62","author":[{"given":"Matthew","family":"Anderson","sequence":"first","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anuj","family":"Dawar","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bjarki","family":"Holm","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12,10]]},"reference":[{"volume-title":"Proceedings of STACS. LIPIcs, 41--52","author":"Anderson M.","key":"e_1_2_1_1_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.23"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.049"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090265"},{"key":"e_1_2_1_5_1","unstructured":"A. Blass and Y. Gurevich. 2005. A quick update on open problems in Blass-Gurevich-Shelah's article \u2018On polynomial time computations over unordered structures\u2019. Online at http:\/\/research.microsoft.com\/_gurevich\/annotated.html.  A. Blass and Y. Gurevich. 2005. A quick update on open problems in Blass-Gurevich-Shelah's article \u2018On polynomial time computations over unordered structures\u2019. Online at http:\/\/research.microsoft.com\/_gurevich\/annotated.html."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00005-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150152"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592196"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90012-5"},{"key":"e_1_2_1_11_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3. ed.). MIT Press.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3. ed.). MIT Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"G. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press.  G. Dantzig. 1963. Linear Programming and Extensions. Princeton University Press.","DOI":"10.7249\/R366"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.24"},{"key":"e_1_2_1_14_1","unstructured":"E. A. Dinitz A. V. Karazanov and M. V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimizations 290--306. In Russian.  E. A. Dinitz A. V. Karazanov and M. V. Lomonosov. 1976. On the structure of the system of minimum edge cuts in a graph. Studies in Discrete Optimizations 290--306. In Russian."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_2_1_17_1","unstructured":"H. D. Ebbinghaus and J. Flum. 1999. Finite Model Theory. Springer.  H. D. Ebbinghaus and J. Flum. 1999. Finite Model Theory. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.013"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192523"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371662"},{"key":"e_1_2_1_21_1","unstructured":"M. Grohe K. Kersting M. Mladenov and E. Selman. 2013. Dimension Reduction via Colour Refinement. CoRR abs\/1307.5697 (2013) 17 pages.  M. Grohe K. Kersting M. Mladenov and E. Selman. 2013. Dimension Reduction via Colour Refinement. CoRR abs\/1307.5697 (2013) 17 pages."},{"volume-title":"Proceedings of CSL. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 289--304","year":"2012","author":"Grohe M.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Springer.  M. Gr\u00f6tschel L. Lov\u00e1sz and A. Schrijver. 1988. Geometric Algorithms and Combinatorial Optimization. Springer.","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_1_25_1","unstructured":"B. Holm. 2010. Descriptive Complexity of Linear Algebra. Ph.D. Dissertation. University of Cambridge.  B. Holm. 2010. Descriptive Complexity of Linear Algebra. Ph.D. Dissertation. University of Cambridge."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. 1999. Descriptive Complexity. Springer-Verlag.  N. Immerman. 1999. Descriptive Complexity. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808695"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(80)90061-0"},{"volume-title":"Proceedings of the 3rd Symposium on Inequalities, Oved. Shisha (Ed.). Academic Press, New York-London, 159--175","author":"Klee V.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","unstructured":"B. Laubner. 2011. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. Ph.D. Dissertation. Humboldt-Universitt zu Berlin.  B. Laubner. 2011. The Structure of Graphs and New Logics for the Characterization of Polynomial Time. Ph.D. Dissertation. Humboldt-Universitt zu Berlin."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"A. N. Letchford G. Reinelt and D. O. Theis. 2004. A faster exact separation algorithm for blossom inequalities. In Integer Programming and Combinatorial Optimization. Springer 196--205.  A. N. Letchford G. Reinelt and D. O. Theis. 2004. A faster exact separation algorithm for blossom inequalities. In Integer Programming and Combinatorial Optimization. Springer 196--205.","DOI":"10.1007\/978-3-540-25960-2_15"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"L. Libkin. 2004. Elements of Finite Model Theory. Springer.   L. Libkin. 2004. Elements of Finite Model Theory. Springer.","DOI":"10.1007\/978-3-662-07003-1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"volume-title":"Fields of Logic and Computation","author":"Rossman B.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","unstructured":"T. Rothvo\u00df. 2013. The matching polytope has exponential extension complexity. CoRR abs\/1311.2369 (2013) 19 pages.  T. Rothvo\u00df. 2013. The matching polytope has exponential extension complexity. CoRR abs\/1311.2369 (2013) 19 pages."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02341816"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/BF01071394","article-title":"Cut-off method with space extension in convex programming problems","volume":"13","author":"Shor N. Z.","year":"1977","journal-title":"Cybern. Syst. Anal."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305952"},{"key":"e_1_2_1_44_1","first-page":"3","article-title":"Informational complexity and efficient methods for the solution of convex extremal problems","volume":"13","author":"Yudin D. B.","year":"1976","journal-title":"Matekon"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2822890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:31Z","timestamp":1750225711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2822890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,10]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2015,12,10]]}},"alternative-id":["10.1145\/2822890"],"URL":"https:\/\/doi.org\/10.1145\/2822890","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2015,12,10]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}