{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:10Z","timestamp":1781028310475,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":29,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"U.S. Department of Energy, Office of Science","award":["DE-SC0024124"],"award-info":[{"award-number":["DE-SC0024124"]}]},{"name":"NSF CAREER Award","award":["CCF-233971"],"award-info":[{"award-number":["CCF-233971"]}]},{"name":"NSF CAREER Award","award":["CCF-2145474"],"award-info":[{"award-number":["CCF-2145474"]}]},{"name":"Paul Daisy Soros Fellowship for New Americans","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800922","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2199-2209","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Lower Bounds for QAC0"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-6146-3064","authenticated-orcid":false,"given":"Malvika Raj","family":"Joshi","sequence":"first","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0375-6554","authenticated-orcid":false,"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4758-2944","authenticated-orcid":false,"given":"Francisca","family":"Vasconcelos","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4071-3488","authenticated-orcid":false,"given":"John","family":"Wright","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718189"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Jinge Bao and Francisco Escudero-Guti\u00e9rrez. 2025. Learning junta distributions quantum junta states and QAC^0 circuits. arxiv:2410.15822. https:\/\/doi.org\/10.48550\/arXiv.2410.15822 10.48550\/arXiv.2410.15822","DOI":"10.48550\/arXiv.2410.15822"},{"key":"e_1_3_2_1_4_1","unstructured":"Paul Beame. 1994. A switching lemma primer. Technical Report UW-CSE-95-07-01 Department of Computer Science and Engineering University of Washington.."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.002"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011679.2011682"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","unstructured":"Stephen A. Fenner Daniel Grier Daniel Pad\u00e9 and Thomas Thierauf. 2025. Tight bounds on depth-2 QAC-circuits computing parity. arXiv:2504.06433. https:\/\/doi.org\/10.48550\/ARXIV.2504.06433 10.48550\/ARXIV.2504.06433","DOI":"10.48550\/ARXIV.2504.06433"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2026.61"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_11_1","first-page":"35","article-title":"Counting, fanout and the complexity of quantum ACC. Quantum Info","volume":"2","author":"Green Frederic","year":"2002","unstructured":"Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. 2002. Counting, fanout and the complexity of quantum ACC. Quantum Info. Comput., 2, 1 (2002), Dec., 35\u201365. issn:1533-7146","journal-title":"Comput."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2025.3"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Daniel Grier Jackson Morris and Kewen Wu. 2026. QAC^0 Contains TC^0 (with Many Copies of the Input). arxiv:2601.03243. https:\/\/doi.org\/10.48550\/arXiv.2601.03243 10.48550\/arXiv.2601.03243","DOI":"10.48550\/arXiv.2601.03243"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.80.4329"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a005"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3095799"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63537"},{"key":"e_1_3_2_1_19_1","volume-title":"Quantum Circuits: Fanout, Parity, and Counting.","author":"Moore Cristopher","year":"1999","unstructured":"Cristopher Moore. 1999. Quantum Circuits: Fanout, Parity, and Counting."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649662"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Daniel Pad\u00e9 Stephen Fenner Daniel Grier and Thomas Thierauf. 2020. Depth-2 QAC circuits cannot simulate quantum parity. arxiv:2005.12169. https:\/\/doi.org\/10.48550\/arXiv.2005.12169 10.48550\/arXiv.2005.12169","DOI":"10.48550\/arXiv.2005.12169"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.32"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0140-0"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2017.15"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research","volume":"5604","author":"Vasconcelos Francisca","year":"2025","unstructured":"Francisca Vasconcelos and Hsin-Yuan Huang. 2025. Learning shallow quantum circuits with many-qubit gates. In Proceedings of Thirty Eighth Conference on Learning Theory, Nika Haghtalab and Ankur Moitra (Eds.) (Proceedings of Machine Learning Research, Vol. 291). PMLR, Online. 5553\u20135604. https:\/\/proceedings.mlr.press\/v291\/vasconcelos25a.html"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316404"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:11Z","timestamp":1781027711000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":29,"alternative-id":["10.1145\/3798129.3800922","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800922","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}