Optimal Composition Theorem for Randomized Query Complexity

by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal

Theory of Computing, Volume 19(9), pp. 1-35, 2023

Bibliography with links to cited articles

[1]   Scott Aaronson: Quantum certificate complexity. J. Comput. System Sci., 74(3):313–322, 2008. Preliminary version in CCC’03. [doi:10.1016/j.jcss.2007.06.020, arXiv:quant-ph/0210020]

[2]   Dana Angluin and Leslie G. Valiant: Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. System Sci., 18(2):155–193, 1979. Preliminary version in STOC’77. [doi:10.1016/0022-0000(79)90045-X]

[3]   Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal: A composition theorem for randomized query complexity. In Proc. 37th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’17), pp. 10:1–13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.FSTTCS.2017.10, arXiv:1706.00335]

[4]   Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao: How to compress interactive communication. SIAM J. Comput., 42(3):1327–1363, 2013. [doi:10.1137/100811969]

[5]   Shalev Ben-David and Eric Blais: A tight composition theorem for the randomized query complexity of partial functions. In Proc. 61st FOCS, pp. 240–246. IEEE Comp. Soc., 2020. [doi:10.1109/FOCS46700.2020.00031, arXiv:2002.10809]

[6]   Shalev Ben-David, Eric Blais, Mika Göös, and Gilbert Maystre: Randomised composition and small-bias minimax. In Proc. 63rd FOCS, pp. 624–635. IEEE Comp. Soc., 2022. [doi:10.1109/FOCS54457.2022.00065, arXiv:2208.12896]

[7]   Shalev Ben-David and Robin Kothari: Randomized query complexity of sabotaged and composed functions. Theory of Computing, 14(5):1–27, 2018. Preliminary version in ICALP’16. [doi:10.4086/toc.2018.v014a005, arXiv:1605.09071]

[8]   Amit Chakrabarti and Oded Regev: An optimal lower bound on the communication complexity of Gap-Hamming-Distance. SIAM J. Comput., 41(5):1299–1317, 2012. Preliminary version in STOC’11. [doi:10.1137/120861072, arXiv:1009.3460]

[9]   Dmitry Gavinsky, Troy Lee, and Miklos Santha: On the randomised query complexity of composition, 2018. [arXiv:1801.02226]

[10]   Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal: A composition theorem for randomized query complexity via max-conflict complexity. In Proc. 46th Internat. Colloq. on Automata, Languages, and Programming (ICALP’19), pp. 64:1–13. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.64]

[11]   Justin Gilmer, Michael Saks, and Srikanth Srinivasan: Composition limits and separating examples for some Boolean function complexity measures. Combinatorica, 36(3):265–311, 2016. Preliminary version in CCC’13. [doi:10.1007/s00493-014-3189-x, arXiv:1306.0630]

[12]   Peter Høyer, Troy Lee, and Robert Špalek: Negative weights make adversaries stronger. In Proc. 39th STOC, pp. 526–535. ACM Press, 2007. [doi:10.1145/1250790.1250867, arXiv:quant-ph/0611054]

[13]   Yaqiao Li: Conflict complexity is lower bounded by block sensitivity. Theoret. Comput. Sci., 856:169–172, 2021. [doi:10.1016/j.tcs.2020.12.038, arXiv:1810.08873]

[14]   Ashley Montanaro: A composition theorem for decision tree complexity. Chicago J. Theoret. Comp. Sci., 2014(6):1–8. [doi:10.4086/cjtcs.2014.006]

[15]   Ben W. Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. SIAM, 2011. [doi:10.1137/1.9781611973082.44, arXiv:1005.1601]

[16]   Swagato Sanyal: A composition theorem via conflict complexity, 2018. [arXiv:1801.03285]

[17]   Avishay Tal: Properties and applications of boolean function composition. In Proc. 4th Innovations in Theoret. Comp. Sci. Conf. (ITCS’13), pp. 441–454. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013. [doi:10.1145/2422436.2422485, ECCC:TR12-163]

[18]   John von Neumann: Zur Theorie der Gessellschaftsspiele. Mathematische Annalen, 100:295–320, 1928. EuDML.