{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:46:56Z","timestamp":1750308416245,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T00:00:00Z","timestamp":1637539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S03238X\/1"],"award-info":[{"award-number":["EP\/S03238X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2022,1,31]]},"abstract":"<jats:p>Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finit field. The expressive power of FPR properly extends that of FPC and is contained in P, but it is not known if that containment is proper. We give a circuit characterization for FPR in terms of families of symmetric circuits with rank gates, along the lines of that for FPC given by Anderson and Dawar in 2017. This requires the development of a broad framework of circuits in which the individual gates compute functions that are not symmetric (i.e., invariant under all permutations of their inputs). This framework also necessitates the development of novel techniques to prove the equivalence of circuits and logic. Both the framework and the techniques are of greater generality than the main result.<\/jats:p>","DOI":"10.1145\/3476227","type":"journal-article","created":{"date-parts":[[2021,11,22]],"date-time":"2021-11-22T17:43:55Z","timestamp":1637603035000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Symmetric Circuits for Rank Logic"],"prefix":"10.1145","volume":"23","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Wilsenach","sequence":"additional","affiliation":[{"name":"University of Cambridge, Cambridge, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,11,22]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9692-2"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00005-6"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2728816.2728820"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-3-319-28678-5_2","volume-title":"Topics in Theoretical Computer Science","author":"Dawar A.","year":"2016","unstructured":"A. Dawar. 2016. On symmetric and choiceless computation. In Topics in Theoretical Computer Science, Mohammad Taghi Hajiaghayi and Mohammad Reza Mousavi (Eds.). Springer International Publishing, Cham, Switzerland, 23\u201329."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2009.24"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_25"},{"key":"e_1_3_2_8_2","first-page":"Article 20, 16","volume-title":"Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL\u201918)","author":"Dawar A.","year":"2018","unstructured":"A. Dawar and G. Wilsenach. 2018. Symmetric circuits for rank logic. In Proceedings of the 27th EACSL Annual Conference on Computer Science Logic (CSL\u201918). Article 20, 16 pages."},{"key":"e_1_3_2_9_2","first-page":"Article 36, 18","volume-title":"Proceedings of the 27th International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","author":"Dawar A.","year":"2020","unstructured":"A. Dawar and G. Wilsenach. 2020. Symmetric arithmetic circuits. In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming (ICALP\u201920). Article 36, 18 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.36"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3110287"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0731-3"},{"key":"e_1_3_2_12_2","first-page":"390","volume-title":"Proceedings of the 2015 24th Annual Conference on Computer Science Logic (CSL\u201915)","author":"Gr\u00e4del E.","year":"2015","unstructured":"E. Gr\u00e4del and W. Pakusa. 2015. Rank logic is dead, long live rank logic! In Proceedings of the 2015 24th Annual Conference on Computer Science Logic (CSL\u201915). 390\u2013404."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781139028868"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0070"},{"key":"e_1_3_2_15_2","volume-title":"Descriptive Complexity of Linear Algebra","author":"Holm B.","year":"2010","unstructured":"B. Holm. 2010. Descriptive Complexity of Linear Algebra. University of Cambridge."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90021-7"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/647846.736744"},{"key":"e_1_3_2_19_2","volume-title":"Symmetric Circuits and Model-Theoretic Logics","author":"Wilsenach G.","year":"2019","unstructured":"G. Wilsenach. 2019. Symmetric Circuits and Model-Theoretic Logics. Master\u2019s Thesis. University of Cambridge. DOI:https:\/\/doi.org\/10.17863\/CAM.44848"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3476227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:16Z","timestamp":1750268956000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3476227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,22]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1,31]]}},"alternative-id":["10.1145\/3476227"],"URL":"https:\/\/doi.org\/10.1145\/3476227","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2021,11,22]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}