Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
Theory of Computing, Volume 14(5), pp. 1-27, 2018
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] Scott Aaronson, Shalev Ben-David, and Robin Kothari: Separations in query complexity using cheat sheets. In Proc. 48th STOC, pp. 863–876. ACM Press, 2016. [doi:10.1145/2897518.2897644, arXiv:1511.01937]
[3] Andris Ambainis, Martins Kokainis, and Robin Kothari: Nearly optimal separations between communication (or query) complexity and partitions. In Proc. 31st IEEE Conf. on Computational Complexity (CCC’16), pp. 4:1–4:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.4, arXiv:1512.01210]
[4] Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, and Miklos Santha: Separations in communication complexity using cheat sheets and information complexity. In Proc. 57st FOCS, pp. 555–564. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.66, arXiv:1605.01142]
[5] Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao: How to compress interactive communication. SIAM J. Computing, 42(3):1327–1363, 2013. Preliminary version in STOC’10. [doi:10.1137/100811969]
[6] Shalev Ben-David and Robin Kothari: Randomized query complexity of sabotaged and composed functions. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 60:1–60:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.60, arXiv:1605.09071]
[7] Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: A survey. Theoret. Computer Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]
[8] Andrew Drucker: Improved direct product theorems for randomized query complexity. Comput. Complexity, 21(2):197–244, 2012. Preliminary version in CCC’11. [doi:10.1007/s00037-012-0043-7, arXiv:1005.0644]
[9] Tomàs Feder, Eyal Kushilevitz, Moni Naor, and Noam Nisan: Amortized communication complexity. SIAM J. Computing, 24(4):736–750, 1995. [doi:10.1137/S0097539792235864]
[10] 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]
[11] Mika Göös, Toniann Pitassi, and Thomas Watson: Deterministic communication vs. partition number. In Proc. 56st FOCS, pp. 1077–1088. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.70]
[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] Rahul Jain and Hartmut Klauck: The partition bound for classical communication complexity and query complexity. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 247–258. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.31, arXiv:0910.4266]
[14] Rahul Jain, Hartmut Klauck, and Miklos Santha: Optimal direct sum results for deterministic and randomized decision tree complexity. Inform. Process. Lett., 110(20):893–897, 2010. [doi:10.1016/j.ipl.2010.07.020, arXiv:1004.0105]
[15] Rahul Jain, Troy Lee, and Nisheeth K. Vishnoi: A quadratically tight partition bound for classical communication complexity and query complexity, 2014. Available at author’s webpage. [arXiv:1401.4512]
[16] Mauricio Karchmer, Ran Raz, and Avi Wigderson: Super-logarithmic depth lower bounds via the direct sum in communication complexity. Comput. Complexity, 5(3-4):191–204, 1995. Preliminary version in SCT’91. [doi:10.1007/BF01206317]
[17] Shelby Kimmel: Quantum adversary (upper) bound. Chicago J. Theoret. Computer Sci., (4), 2013. [doi:10.4086/cjtcs.2013.004]
[18] Raghav Kulkarni and Avishay Tal: On fractional block sensitivity. Chicago J. Theoret. Computer Sci., 2016(8), 2016. [doi:10.4086/cjtcs.2016.008]
[19] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy: Quantum query complexity of state conversion. In Proc. 52nd FOCS, pp. 344–353. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.75, arXiv:1011.3020]
[20] Ashley Montanaro: A composition theorem for decision tree complexity. Chicago J. Theoret. Computer Sci., 2014(6), 2014. [doi:10.4086/cjtcs.2014.006, arXiv:1302.4207]
[21] Denis Pankratov: Direct sum questions in classical communication complexity. Master’s thesis, University of Chicago, 2012. Available at advisor’s webpage.
[22] Ben W. Reichardt: Reflections for quantum query algorithms. In Proc. 22nd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’11), pp. 560–569. ACM Press, 2011. [doi:10.1137/1.9781611973082.44]
[23] Maurice Sion: On general minimax theorems. Pacific J. Math., 8(1):171–176, 1958. [doi:10.2140/pjm.1958.8.171]
[24] Avishay Tal: Properties and applications of Boolean function composition. In Proc. 4th Innovations in Theoret. Computer Sci. Conf. (ITCS’13), pp. 441–454. ACM Press, 2013. [doi:10.1145/2422436.2422485]
[25] Nikolai K. Vereshchagin: Randomized Boolean decision trees: Several remarks. Theoret. Computer Sci., 207(2):329–342, 1998. [doi:10.1016/S0304-3975(98)00071-1]
[26] John Watrous: The Theory of Quantum Information. Cambridge University Press, 2018. Available at CUP and at author’s webpage.
[27] Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. 18st FOCS, pp. 222–227. IEEE Comp. Soc. Press, 1977. [doi:10.1109/SFCS.1977.24]