{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:44Z","timestamp":1781031464186,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":59,"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":"NSERC","award":["DGECR-2019-00027"],"award-info":[{"award-number":["DGECR-2019-00027"]}]},{"name":"NSERC","award":["RGPIN-2019-04804"],"award-info":[{"award-number":["RGPIN-2019-04804"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800897","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1913-1924","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Monte Carlo to Las Vegas for Recursively Composed Functions"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-5450-9571","authenticated-orcid":false,"given":"Bandar","family":"Al-Dhalaan","sequence":"first","affiliation":[{"name":"University of Waterloo, David R. Cheriton School of Computer Science, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4176-8693","authenticated-orcid":false,"given":"Shalev","family":"Ben-David","sequence":"additional","affiliation":[{"name":"University of Waterloo, David R. Cheriton School of Computer Science, Waterloo, Canada"},{"name":"Institute for Quantum Computing, Waterloo, Canada"}],"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\/j.jcss.2007.06.020"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"e_1_3_2_1_3_1","unstructured":"1Cette recherche a \u00e9t\u00e9 financ\u00e9e par le Conseil de recherches en sciences naturelles et en g\u00e9nie du Canada (CRSNG) DGECR-2019-00027 et RGPIN-2019-04804."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Andris Ambainis. 2016. Superlinear advantage for exact quantum algorithms.","DOI":"10.1137\/130939043"},{"key":"e_1_3_2_1_5_1","volume-title":"Previous version in STOC","author":"Computing SIAM","year":"2013","unstructured":"SIAM Journal on Computing. Previous version in STOC 2013. arXiv: 1211. 0721."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","unstructured":"doi:10.1137\/130939043. 10.1137\/130939043","DOI":"10.1137\/130939043"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106234"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP"},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS). arXiv","author":"Ben-David Shalev","year":"2020","unstructured":"Shalev Ben-David and Eric Blais. 2020. A tight composition theorem for the randomized query complexity of partial functions. Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS). arXiv: 2002.10809."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"doi:10.1109\/focs46700. 2020. 00031. 10.1109\/focs46700.2020.00031","DOI":"10.1109\/focs46700"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00065"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"doi:10.1109\/focs54457. 2022. 00065. 10.1109\/focs54457.2022.00065","DOI":"10.1109\/focs54457"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM.2"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Harry Buhrman and Ronald de Wolf. 2002. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science. doi:10.1016\/S0304-397 5 ( 01 ) 00144-X. 10.1016\/S0304-3975(01)00144-X","DOI":"10.1016\/S0304-397"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188784"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","unstructured":"arXiv: 1710.09079. doi:10.1145\/3188745.3188784. 10.1145\/3188745.3188784","DOI":"10.1145\/3188745.3188784"},{"key":"e_1_3_2_1_20_1","volume-title":"Proceedings of the International Conference on Randomization and Computation (RANDOM). arXiv: 2307","author":"Chakraborty Sourav","year":"2023","unstructured":"Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, and Nitin Saurabh. 2023. On the composition of randomized query complexity and approximate degree. Proceedings of the International Conference on Randomization and Computation (RANDOM). arXiv: 2307. 03900."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","unstructured":"doi:10.4230\/LIPICS.APPROX\/RANDOM. 2023. 63. 10.4230\/LIPICS.APPROX\/RANDOM.2023.63","DOI":"10.4230\/LIPICS.APPROX\/RANDOM"},{"key":"e_1_3_2_1_22_1","unstructured":"Sourav Chakraborty Chandrima Kayal Rajat Mittal Manaswi Paraashar and Nitin Saurabh. 2024. Approximate degree composition for recursive functions."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX\/RANDOM"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS"},{"key":"e_1_3_2_1_25_1","unstructured":"CCC. 2018. 15."},{"key":"e_1_3_2_1_26_1","unstructured":"Dmitry Gavinsky Troy Lee Miklos Santha and Swagato Sanyal. 2019. A composition theorem for randomized query complexity via max-conflict complexity."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Justin Gilmer Michael Saks and Sudarshan Srinivasan. 2016. Composition limits and separating examples for some boolean function complexity measures.","DOI":"10.1007\/s00493-014-3189-x"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s0"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.69"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS"},{"key":"e_1_3_2_1_32_1","unstructured":"Mika G\u00f6\u00f6s and T. S. Jayram. 2016. A composition theorem for conical juntas."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3170"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780640"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Stacey Jefery and Shelby Kimmel. 2017. Quantum algorithms for graph connectivity and formula evaluation. Quantum. arXiv: 1704.00765. doi: 10.22331\/q2017-08-17-26.","DOI":"10.22331\/q2017-08-17-26"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Mauricio Karchmer Ran Raz and Avi Wigderson. 1995. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity. doi:10.1007\/BF01206317. 10.1007\/BF01206317","DOI":"10.1007\/BF01206317"},{"key":"e_1_3_2_1_40_1","volume-title":"Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science. Previous version in ICALP","author":"Kimmel Shelby","year":"2012","unstructured":"Shelby Kimmel. 2013. Quantum adversary (upper) bound. Chicago Journal of Theoretical Computer Science. Previous version in ICALP 2012. arXiv: 1101. 0797."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","unstructured":"doi:10.4086\/cjtcs. 2013. 004. 10.4086\/cjtcs.2013.004","DOI":"10.4086\/cjtcs"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 18th International Conference on Randomization and Computation (RANDOM).","author":"Kothari Robin","year":"2015","unstructured":"Robin Kothari, David Racicot-Desloges, and Miklos Santha. 2015. Separating decision tree complexity from subcube partition complexity. Proceedings of the 18th International Conference on Randomization and Computation (RANDOM)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_59"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20598"},{"key":"e_1_3_2_1_47_1","unstructured":"Ashley Montanaro. 2014. A composition theorem for decision tree complexity."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2014.006"},{"key":"e_1_3_2_1_49_1","unstructured":"Sagnik Mukhopadhyay Jaikumar Radhakrishnan and Swagato Sanyal. 2018."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","unstructured":"Separation between deterministic and randomized query complexity. SIAM Journal on Computing. eccc: 2015 \/107. doi: 10.1137\/17m1124115. 10.1137\/17m1124115","DOI":"10.1137\/17m1124115"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Noam Nisan and Avi Wigderson. 1995. On rank vs. communication complexity.","DOI":"10.1007\/BF01192527"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192527"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.44"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.44"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","unstructured":"Miklos Santha. 1995. On the monte carlo boolean decision tree complexity of read-once formulae. Random Structures & Algorithms. doi: 10.1002\/rsa.32400601 08. 10.1002\/rsa.3240060108","DOI":"10.1002\/rsa.32400601"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS"},{"key":"e_1_3_2_1_57_1","unstructured":"Avishay Tal. 2013. Properties and applications of boolean function composition."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"e_1_3_2_1_59_1","unstructured":"Ingo Wegener and Laszlo Z\u00e1dori. 1988. A note on the relations between critical and sensitive complexity. ( 1988 )."}],"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.3800897","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:00Z","timestamp":1781028120000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800897"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":59,"alternative-id":["10.1145\/3798129.3800897","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800897","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"}}]}}