{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:15:12Z","timestamp":1764339312687,"version":"3.46.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"\n Let\n \n \\(\\mathsf {R}_\\epsilon\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n denote the randomized query complexity for error probability \u03b5, and\n \n \\(\\mathsf {R}:=\\mathsf {R}_{1\/3}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . In this work, we investigate whether a perfect composition theorem\n \n \\(\\mathsf {R}(f \\circ g^n)=\\Omega (\\mathsf {R}(f)\\cdot \\mathsf {R}(g))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n holds for a relation\n \n \\(f \\subseteq \\lbrace 0,1\\rbrace ^n \\times \\mathcal {S}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and a total inner function\n \n \\(g:\\lbrace 0,1\\rbrace ^m \\rightarrow \\lbrace 0,1\\rbrace\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Ben-David and Kothari (ICALP 2016, TOC 2018) showed that\n \n \\(\\mathsf {R}(f \\circ g^n)=\\Omega (\\mathsf {R}(f)\\cdot \\mathsf {RS}(g))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , where\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the sabotage complexity, a measure that they defined. Their result holds even when\n f<\/jats:italic>\n is any relation and\n g<\/jats:italic>\n is any partial function. Ben-David and Kothari asked in their article whether Sabotage complexity\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is asymptotically equivalent to\n \n \\(\\mathsf {R}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for total Boolean functions. In this article, we show that\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is asymptotically at least the maximum distributional query complexity for any product distribution (i.e., probability distribution where the individual bits are independently distributed). In light of the minimax theorem, which states that\n \n \\(\\mathsf {R}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the maximum distributional query complexity for any distribution, our result makes progress toward answering the composition question. We prove our result by introducing a novel complexity measure called\n \n \\(\\mathsf {R}_{}^{\\mathsf {prod}}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and proving it to be equivalent to\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n up to a logarithmic factor.\n <\/jats:p>\n \n \n How tight is our bound? We show that our bound is polynomially loose for the complete binary NAND tree function, for which\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is polynomially larger than the distributional query complexity for any product distribution. Our result also confirms that\n \n \\(\\mathsf {RS}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and\n \n \\(\\mathsf {R}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n are asymptotically equivalent for this function. We thus also show a polynomial separation between\n \n \\(\\mathsf {R}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and the maximum distributional query complexity for any product distribution which, to our knowledge, was not known prior to our work.\n <\/jats:p>","DOI":"10.1145\/3747851","type":"journal-article","created":{"date-parts":[[2025,7,15]],"date-time":"2025-07-15T11:36:22Z","timestamp":1752579382000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized query composition and sabotage complexity"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1546-7749","authenticated-orcid":false,"given":"Swagato","family":"Sanyal","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, IIT Kharagpur","place":["Kharagpur, India"]},{"name":"School of Computer Science, The University of Sheffield","place":["Kharagpur, India"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"1","volume-title":"Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science","author":"Anshu Anurag","year":"2018","unstructured":"Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. 2018. A composition theorem for randomized query complexity. In Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. 1."},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming","author":"Bassilakis Andrew","year":"2020","unstructured":"Andrew Bassilakis, Andrew Drucker, Mika G\u00f6\u00f6s, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. 2020. The power of many samples in query complexity. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00031"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00065"},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming.","author":"Ben-David Shalev","year":"2016","unstructured":"Shalev Ben-David and Robin Kothari. 2016. Randomized query complexity of sabotaged and composed functions. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_8_2","series-title":"LIPIcs","first-page":"63:1\u201363:23","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, September 11-13, 2023, Atlanta, Georgia, USA.","volume":"275","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. In Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, September 11-13, 2023, Atlanta, Georgia, USA.Nicole Megow and Adam D. Smith (Eds.), LIPIcs, Vol. 275, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 63:1\u201363:23."},{"key":"e_1_3_2_9_2","series-title":"LIPIcs","first-page":"64:1\u201364:13","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming.","volume":"132","author":"Gavinsky Dmitry","year":"2019","unstructured":"Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. 2019. A composition theorem for randomized query complexity via max-conflict complexity. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming.LIPIcs, Vol. 132,Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 64:1\u201364:13."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3170711"},{"key":"e_1_3_2_11_2","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming","author":"Harsha Prahladh","year":"2016","unstructured":"Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan. 2016. Partition bound is quadratically tight for product distributions. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09935-x"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897537"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2014.006"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/358589.358616"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.44"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1991.160259"},{"key":"e_1_3_2_19_2","first-page":"218","volume-title":"Proceedings of the 34th annual ACM Symposium on Theory of Computing","author":"Smyth Clifford","year":"2002","unstructured":"Clifford Smyth. 2002. Reimer\u2019s inequality and tardos\u2019 conjecture. In Proceedings of the 34th annual ACM Symposium on Theory of Computing. 218\u2013221."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90210-5"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322383"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3747851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:10:20Z","timestamp":1764339020000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3747851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3747851"],"URL":"https:\/\/doi.org\/10.1145\/3747851","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"2024-11-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}