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]