{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T21:43:14Z","timestamp":1771623794426,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,1,8]],"date-time":"2012-01-08T00:00:00Z","timestamp":1325980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CICYT","award":["TIN2010-20967-C04-04 (TASSAT)"],"award-info":[{"award-number":["TIN2010-20967-C04-04 (TASSAT)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,1,8]]},"DOI":"10.1145\/2090236.2090265","type":"proceedings-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T17:02:17Z","timestamp":1326214937000},"page":"367-379","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Sherali-Adams relaxations and indistinguishability in counting logics"],"prefix":"10.1145","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[{"name":"Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain"}]},{"given":"Elitza","family":"Maneva","sequence":"additional","affiliation":[{"name":"Universitat de Barcelona, Barcelona, Spain"}]}],"member":"320","published-online":{"date-parts":[[2012,1,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a002"},{"key":"e_1_3_2_1_2_1","series-title":"Lecture Notes in Computer Science","volume-title":"34th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Atserias A.","year":"2007","unstructured":"A. Atserias , A. Bulatov , and A. Dawar . Affine systems of equations and counting infinitary logic . In 34th International Colloquium on Automata, Languages and Programming (ICALP) , Lecture Notes in Computer Science , 2007 . A. Atserias, A. Bulatov, and A. Dawar. Affine systems of equations and counting infinitary logic. In 34th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, 2007."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.12.049"},{"key":"e_1_3_2_1_4_1","volume-title":"Unpublished","author":"Atserias A.","year":"2006","unstructured":"A. Atserias , Ph. G. Kolaitis , and M. Y. Vardi . Linear programming and the existential pebble game . Unpublished , 2006 . A. Atserias, Ph. G. Kolaitis, and M. Y. Vardi. Linear programming and the existential pebble game. Unpublished, 2006."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209047"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592023"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1190150152"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_1_10_1","volume-title":"Finite Model Theory","author":"Ebbinghaus H.","year":"1995","unstructured":"H. Ebbinghaus and J. Flum . Finite Model Theory . Springer-Verlag , 1995 . H. Ebbinghaus and J. Flum. Finite Model Theory. Springer-Verlag, 1995."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_3_2_1_12_1","first-page":"1022","article-title":"Sur une nouvelle classification des syst\u00e8mes de relations","volume":"230","author":"Fra\u00efss\u00e9 R.","year":"1950","unstructured":"R. Fra\u00efss\u00e9 . Sur une nouvelle classification des syst\u00e8mes de relations . Comptes Rendus , 230 : 1022 -- 1024 , 1950 . R. Fra\u00efss\u00e9. Sur une nouvelle classification des syst\u00e8mes de relations. Comptes Rendus, 230:1022--1024, 1950.","journal-title":"Comptes Rendus"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.34"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/788020.788896"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335313"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.22"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer-Verlag 1999.  N. Immerman. Descriptive Complexity . Springer-Verlag 1999.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_2_1_18_1","first-page":"59","volume-title":"Describing Graphs: A First-Order Approach to Graph Canonization","author":"Immerman N.","year":"1990","unstructured":"N. Immerman and E. Lander . Describing Graphs: A First-Order Approach to Graph Canonization , pages 59 -- 81 . Springer-Verlag , 1990 . N. Immerman and E. Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59--81. Springer-Verlag, 1990."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00025-X"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.11"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.3.470.16391"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.4.871.20508"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1024196"},{"key":"e_1_3_2_1_27_1","volume-title":"Matching Theory","author":"Lov\u00e1sz L.","year":"2009","unstructured":"L. Lov\u00e1sz and M. D. Plummer . Matching Theory , volume 367 . AMS Chelsea Publishing , 2009 . L. Lov\u00e1sz and M. D. Plummer. Matching Theory, volume 367. AMS Chelsea Publishing, 2009."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0801013"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536456"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-21676-7","volume-title":"Bounded variable logics and counting -- A study in finite models","author":"Otto M.","year":"1997","unstructured":"M. Otto . Bounded variable logics and counting -- A study in finite models , volume 9 . Springer-Verlag , 1997 . M. Otto. Bounded variable logics and counting -- A study in finite models, volume 9. Springer-Verlag, 1997."},{"key":"e_1_3_2_1_31_1","article-title":"Logical complexity of graphs: a survey. 55pp.arXiv:1003.4865v3 {math. CO}, accepted for publication in \"Model Theoretic Methods in Finite Combinatorics","author":"Pikhurko O.","year":"2011","unstructured":"O. Pikhurko and O. Verbitsky . Logical complexity of graphs: a survey. 55pp.arXiv:1003.4865v3 {math. CO}, accepted for publication in \"Model Theoretic Methods in Finite Combinatorics \", M. Grohe and J. Makowsky (editors), AMS Comtemporary Mathematics Series , 2011 . O. Pikhurko and O. Verbitsky. Logical complexity of graphs: a survey. 55pp.arXiv:1003.4865v3 {math. CO}, accepted for publication in \"Model Theoretic Methods in Finite Combinatorics\", M. Grohe and J. Makowsky (editors), AMS Comtemporary Mathematics Series, 2011.","journal-title":"M. Grohe and J. Makowsky (editors), AMS Comtemporary Mathematics Series"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90241-0"},{"key":"e_1_3_2_1_33_1","volume-title":"Fractional Graph Theory","author":"Scheinerman E. R.","year":"1992","unstructured":"E. R. Scheinerman and D. H. Ullman . Fractional Graph Theory . Wiley-Interscience , 1992 . E. R. Scheinerman and D. H. Ullman. Fractional Graph Theory. Wiley-Interscience, 1992."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250836"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_3_2_1_37_1","volume-title":"Lecture Notes on Design and Analysis of Algorithms","author":"Stallmann Matt","unstructured":"Matt Stallmann . Lecture Notes on Design and Analysis of Algorithms . North Carolina State University . Matt Stallmann. Lecture Notes on Design and Analysis of Algorithms. North Carolina State University."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.1.1"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.28"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536457"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"}],"event":{"name":"ITCS '12: Innovations in Theoretical Computer Science","location":"Cambridge Massachusetts","acronym":"ITCS '12","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 3rd Innovations in Theoretical Computer Science Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2090236.2090265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:46Z","timestamp":1750241206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,8]]},"references-count":41,"alternative-id":["10.1145\/2090236.2090265","10.1145\/2090236"],"URL":"https:\/\/doi.org\/10.1145\/2090236.2090265","relation":{},"subject":[],"published":{"date-parts":[[2012,1,8]]},"assertion":[{"value":"2012-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}