{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:43:44Z","timestamp":1787496224753,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T00:00:00Z","timestamp":1467676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,7,5]]},"DOI":"10.1145\/2933575.2934560","type":"proceedings-article","created":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T09:34:47Z","timestamp":1476437687000},"page":"267-276","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps"],"prefix":"10.1145","author":[{"given":"Christoph","family":"Berkholz","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jakob","family":"Nordstr\u00f6m","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,7,5]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"18","article-title":"Lower bounds for polynomial calculus: Non-binomial case","volume":"242","author":"Alekhnovich M.","year":"2003","unstructured":"M. Alekhnovich and A. A. Razborov . Lower bounds for polynomial calculus: Non-binomial case . Proc. Steklov Institute of Mathematics , 242 : 18 -- 35 , 2003 . M. Alekhnovich and A. A. Razborov. Lower bounds for polynomial calculus: Non-binomial case. Proc. Steklov Institute of Mathematics, 242:18--35, 2003.","journal-title":"Proc. Steklov Institute of Mathematics"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897542"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.2307\/2272133"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488711"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0172-5"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509975"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.42"},{"key":"e_1_3_2_1_8_1","first-page":"401","volume-title":"Proc. 2nd Symposium on Innovations in Computer Science (ICS '11)","author":"Ben-Sasson E.","year":"2011","unstructured":"E. Ben-Sasson and J. Nordstr\u00f6m . Understanding space in proof complexity: Separations and trade-offs via substitutions . In Proc. 2nd Symposium on Innovations in Computer Science (ICS '11) , pp. 401 -- 416 , 2011 . E. Ben-Sasson and J. Nordstr\u00f6m. Understanding space in proof complexity: Separations and trade-offs via substitutions. In Proc. 2nd Symposium on Innovations in Computer Science (ICS '11), pp. 401--416, 2011."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10428-7_14"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350790"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1726"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_37"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646254.684263"},{"key":"e_1_3_2_1_17_1","volume-title":"Finite Model Theory and Its Applications","author":"Gr\u00e4del E.","year":"2007","unstructured":"E. Gr\u00e4del , P. G. Kolaitis , L. Libkin , M. Marx , J. Spencer , M. Y. Vardi , Y. Venema , and S. Weinstein . Finite Model Theory and Its Applications . Springer , 2007 . E. Gr\u00e4del, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S. Weinstein. Finite Model Theory and Its Applications. Springer, 2007."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00157-2"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.2307\/420954"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970004"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2371656.2371662"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275675"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90039-8"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2933595"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_29"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.69"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833251"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-9(3:15)2013"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2858790"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.74"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/212433.212474"}],"event":{"name":"LICS '16: 31st Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"New York NY USA","acronym":"LICS '16","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","EACSL European Association for Computer Science Logic","IEEE-CS\\DATC IEEE Computer Society"]},"container-title":["Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934560","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2933575.2934560","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:54:53Z","timestamp":1750208093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2933575.2934560"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,5]]},"references-count":35,"alternative-id":["10.1145\/2933575.2934560","10.1145\/2933575"],"URL":"https:\/\/doi.org\/10.1145\/2933575.2934560","relation":{},"subject":[],"published":{"date-parts":[[2016,7,5]]},"assertion":[{"value":"2016-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}