{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:23Z","timestamp":1781031443988,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":42,"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":[{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"publisher","award":["RTI4014"],"award-info":[{"award-number":["RTI4014"]}],"id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","award":["Faculty Award"],"award-info":[{"award-number":["Faculty Award"]}],"id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Tata Institute of Fundamental Research (TIFR)","award":["R. Narasimhan Postdoctoral Fellowship"],"award-info":[{"award-number":["R. Narasimhan Postdoctoral Fellowship"]}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["929894"],"award-info":[{"award-number":["929894"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation (NSF)","award":["CCF-2425349"],"award-info":[{"award-number":["CCF-2425349"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800895","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1892-1900","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Restriction Trees for Sparsity and Applications"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3110-3584","authenticated-orcid":false,"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7338-1762","authenticated-orcid":false,"given":"Yogesh","family":"Dahiya","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Mumbai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4552-1443","authenticated-orcid":false,"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California San Diego, San Diego, 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.1145\/3406325.3451047"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_29"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00063"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.12"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451002"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53015-3_21"},{"key":"e_1_3_2_1_9_1","first-page":"1","article-title":"Approximate degree, secret sharing and concentration phenomena. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","volume":"71","author":"Bogdanov Andrej","year":"2019","unstructured":"Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. 2019. Approximate degree, secret sharing and concentration phenomena. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM. LIPIcs, 145, Schloss-Dagstuhl, 71:1\u201371:21.","journal-title":"APPROX\/RANDOM. LIPIcs, 145, Schloss-Dagstuhl"},{"key":"e_1_3_2_1_10_1","volume-title":"31st Annual Symposium on Foundations of Computer Science (FOCS). II, IEEE, 632\u2013641","author":"Bruck Jehoshua","year":"1990","unstructured":"Jehoshua Bruck and Roman Smolensky. 1990. Polynomial threshold functions, AC^0 functions, and spectral norms (extended abstract). In 31st Annual Symposium on Foundations of Computer Science (FOCS). II, IEEE, 632\u2013641."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2001.933879"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2020.V016A010"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000107"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554833"},{"key":"e_1_3_2_1_16_1","volume-title":"TR08-002","author":"Chattopadhyay Arkadev","year":"2008","unstructured":"Arkadev Chattopadhyay and Anil Ada. 2008. Multiparty Communication Complexity of Disjointness. Electron. Colloquium Comput. Complex., TR08-002 (2008), ECCC:TR08-002. https:\/\/eccc.weizmann.ac.il\/eccc-reports\/2008\/TR08-002\/index.html"},{"key":"e_1_3_2_1_17_1","unstructured":"Arkadev Chattopadhyay Yogesh Dahiya and Shachar Lovett. 2025. Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis. arXiv arxiv:2507.13963."},{"key":"e_1_3_2_1_18_1","volume-title":"TR25-172","author":"Chattopadhyay Arkadev","year":"2025","unstructured":"Arkadev Chattopadhyay, Yogesh Dahiya, and Shachar Lovett. 2025. Restriction Trees for Sparsity and Applications. Electron. Colloquium Comput. Complex., TR25-172 (2025), ECCC:TR25-172. https:\/\/eccc.weizmann.ac.il\/report\/2025\/172"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585199"},{"key":"e_1_3_2_1_20_1","volume-title":"Mande","author":"Chattopadhyay Arkadev","year":"2017","unstructured":"Arkadev Chattopadhyay and Nikhil S. Mande. 2017. Dual polynomials and communication complexity of XOR functions. Electron. Colloquium Comput. Complex., TR17-062 (2017), ECCC:TR17-062. https:\/\/eccc.weizmann.ac.il\/report\/2017\/062"},{"key":"e_1_3_2_1_21_1","volume-title":"37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017","volume":"14","author":"Chattopadhyay Arkadev","year":"2017","unstructured":"Arkadev Chattopadhyay and Nikhil S. Mande. 2017. A Lifting Theorem with Applications to Symmetric Functions. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India, Satya V. Lokam and R. Ramanujam (Eds.) (LIPIcs, Vol. 93). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 23:1\u201323:14."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396695"},{"key":"e_1_3_2_1_23_1","volume-title":"16th Innovations in Theoretical Computer Science Conference (ITCS","author":"Cheung Tsun-Ming","year":"2025","unstructured":"Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley. 2025. A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). 37\u20131."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0654-y"},{"key":"e_1_3_2_1_25_1","volume-title":"Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. CoRR, abs\/1907.00847","author":"Huang Hao","year":"2019","unstructured":"Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. CoRR, abs\/1907.00847 (2019), arxiv:1907.00847"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.007"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471469.3471479"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3450999"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492670"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-009-0276-2"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Troy Lee Adi Shraibman et al. 2009. Lower bounds in communication complexity. Foundations and Trends\u00ae in Theoretical Computer Science 3 4 (2009) 263\u2013399.","DOI":"10.1561\/0400000040"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.36"},{"key":"e_1_3_2_1_35_1","volume-title":"On the degree of Boolean functions as real polynomials. Computational complexity, 4","author":"Nisan Noam","year":"1994","unstructured":"Noam Nisan and Mario Szegedy. 1994. On the degree of Boolean functions as real polynomials. Computational complexity, 4 (1994), 301\u2013313."},{"key":"e_1_3_2_1_36_1","volume-title":"Quantum communication complexity of symmetric predicates. Izvestiya:Mathematics, 67, 1","author":"Razborov Alexander","year":"2003","unstructured":"Alexander Razborov. 2003. Quantum communication complexity of symmetric predicates. Izvestiya:Mathematics, 67, 1 (2003), 145\u2013159."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC10.5-6-5"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629334"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC9.5-6-7"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00062"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Justin Thaler Jonathan Ullman and Salil Vadhan. 2012. Faster algorithms for privately releasing marginals. In International Colloquium on Automata Languages and Programming. 810\u2013821.","DOI":"10.1007\/978-3-642-31594-7_68"}],"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.3800895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:01:15Z","timestamp":1781028075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":42,"alternative-id":["10.1145\/3798129.3800895","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800895","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"}}]}}