Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem. (English) Zbl 07765252
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1330-1342 (2021).
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Scott Aaronson, Shalev Ben-David, and Robin Kothari. 2016. Separations in query complexity using cheat sheets. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016. Pages 863-876. · Zbl 1373.68216 · doi:10.1145/2897518.2897644 |
| [2] | Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. 2020. Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem. arXiv preprint arXiv:2010.12629, 2020. |
| [3] | Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal. 2020. Quantum Implications of Huang’s Sensitivity Theorem. arXiv preprint arXiv:2004.13231, 2020. |
| [4] | Andris Ambainis. 2002. Quantum Lower Bounds by Quantum Arguments. J. Comput. System Sci., 64, 4, jun, 2002. Pages 750-767. · Zbl 1015.68075 · doi:10.1006/jcss.2002.1826 |
| [5] | Andris Ambainis. 2013. Superlinear Advantage for Exact Quantum Algorithms. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013). Pages 891-900. · Zbl 1293.68124 · doi:10.1145/2488608.2488721 |
| [6] | Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. 2017. Separations in Query Complexity Based on Pointer Functions. Journal of the ACM, 64, 5, Sept., 2017. · Zbl 1426.68109 · doi:10.1145/3106234 |
| [7] | T. Ando, Roger A. Horn, and Charles R. Johnson. 1987. The singular values of a Hadamard product: a basic inequality. Linear and Multilinear Algebra, 21, 4, 1987. Pages 345-365. · Zbl 0633.15011 · doi:10.1080/03081088708817810 |
| [8] | Nikhil Bansal and Makrand Sinha. 2020. k-Forrelation Optimally Separates Quantum and Classical Query Complexity. arXiv preprint arXiv:2008.07003, 2020. |
| [9] | Howard Barnum and Michael Saks. 2004. A lower bound on the quantum query complexity of read-once functions. J. Comput. System Sci., 69, 2, 2004. Pages 244 - 258. · Zbl 1083.68045 · doi:10.1016/j.jcss.2004.02.002 |
| [10] | Howard Barnum, Michael E. Saks, and Mario Szegedy. 2003. Quantum query complexity and semi-definite programming. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003). Pages 179-193. · doi:10.1109/CCC.2003.1214419 |
| [11] | Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. 2001. Quantum lower bounds by polynomials. J. ACM, 48, 4, 2001. Pages 778-797. · Zbl 1127.68404 · doi:10.1145/502090.502097 |
| [12] | Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari. 2018. Classical Lower Bounds from Quantum Upper Bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 339-349. · doi:10.1109/FOCS.2018.00040 |
| [13] | Shalev Ben-David, Pooya Hatami, and Avishay Tal. 2017. Low-Sensitivity Functions from Unambiguous Certificates. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. LIPIcs. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 28:1-28:23. · Zbl 1402.68082 · doi:10.4230/LIPIcs.ITCS.2017.28 |
| [14] | Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and Weaknesses of Quantum Computing. SIAM J. Comput., 26, 5, Oct., 1997. Pages 1510-1523. · Zbl 0895.68044 · doi:10.1137/S0097539796300933 |
| [15] | Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. 1999. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science. Pages 358-368. · doi:10.1109/SFFCS.1999.814607 |
| [16] | Harry Buhrman and Ronald de Wolf. 2002. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288, 1, 2002. Pages 21-43. https://doi.org/10.1016/S0304-3975(01)00144-X · Zbl 1061.68058 · doi:10.1016/S0304-3975(01)00144-X |
| [17] | Harry Buhrman, Ilan Newman, Hein Rohrig, and Ronald de Wolf. 2007. Robust polynomials and quantum algorithms. Theory of Computing Systems, 40, 4, 2007. Pages 379-395. · Zbl 1121.68049 · doi:10.1007/s00224-006-1313-z |
| [18] | Mark Bun and Justin Thaler. 2013. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. In Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013. Pages 303-314. · Zbl 1327.68116 · doi:10.1007/978-3-642-39206-1_26 |
| [19] | Mark Bun and Justin Thaler. 2015. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015. Pages 268-280. · Zbl 1402.68083 · doi:10.1007/978-3-662-47672-7_22 |
| [20] | Mark Bun and Justin Thaler. 2017. A Nearly Optimal Lower Bound on the Approximate Degree of AC^0. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017). Pages 1-12. · doi:10.1109/FOCS.2017.10 |
| [21] | Amit Chakrabarti and Subhash Khot. 2001. Improved Lower Bounds on the Randomized Complexity of Graph Properties. In Automata, Languages and Programming. Pages 285-296. · Zbl 0986.68036 · doi:10.1007/3-540-48224-5_24 |
| [22] | Yevgeniy Dodis and Sanjeev Khanna. 1999. Space-Time Tradeoffs for Graph Properties. In Automata, Languages and Programming. Pages 291-300. · doi:10.1007/3-540-48523-6_26 |
| [23] | Ehud Friedgut, Jeff Kahn, and Avi Wigderson. 2002. Computing Graph Properties by Randomized Subcube Partitions. In Randomization and Approximation Techniques in Computer Science. Pages 105-113. · Zbl 1028.68567 · doi:10.1007/3-540-45726-7_9 |
| [24] | Justin Gilmer, Michael Saks, and Srikanth Srinivasan. 2013. Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. In Proceedings of 2013 IEEE Conference on Computational Complexity (CCC 2013). Pages 185-196. · doi:10.1109/CCC.2013.27 |
| [25] | Chris Godsil and Gordon Royle. 2001. Algebraic Graph Theory. Springer New York. · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9 |
| [26] | Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. 2018. Randomized Communication versus Partition Number. ACM Transactions on Computation Theory, 10, 1, Jan., 2018. · Zbl 1427.68083 · doi:10.1145/3170711 |
| [27] | Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, STOC 1996. Pages 212-219. · Zbl 0922.68044 · doi:10.1145/237814.237866 |
| [28] | Mika Göös, Toniann Pitassi, and Thomas Watson. 2018. Deterministic Communication vs. Partition Number. SIAM J. Comput., 47, 6, 2018. Pages 2435-2450. · Zbl 1409.68115 · doi:10.1137/16M1059369 |
| [29] | Péter Hajnal. 1991. An \Omega (n^4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11, 2, jun, 1991. Pages 131-143. · Zbl 0743.68076 · doi:10.1007/bf01206357 |
| [30] | Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Annals of Mathematics, 190, 3, 2019. Pages 949-955. · Zbl 1427.05116 · doi:10.4007/annals.2019.190.3.6 |
| [31] | Jeff Kahn, Michael Saks, and Dean Sturtevant. 1984. A topological approach to evasiveness. Combinatorica, 4, 4, 1984. Pages 297-306. · Zbl 0577.05061 · doi:10.1007/bf02579140 |
| [32] | Valerie King. 1988. Lower Bounds on the Complexity of Graph Properties. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88. Pages 468-476. · doi:10.1145/62212.62258 |
| [33] | Elias Koutsoupias. 1993. Improvements on Khrapchenko’s theorem. Theoretical Computer Science, 116, 2, 1993. Pages 399-403. https://doi.org/10.1016/0304-3975(93)90330-V · Zbl 0777.94022 · doi:10.1016/0304-3975(93)90330-V |
| [34] | Raghav Kulkarni and Supartha Podder. 2016. Quantum Query Complexity of Subgraph Isomorphism and Homomorphism. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs). 47, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Pages 48:1-48:13. · Zbl 1388.68071 · doi:10.4230/LIPIcs.STACS.2016.48 |
| [35] | Raghav Kulkarni and Avishay Tal. 2016. On Fractional Block Sensitivity. Chicago Journal of Theoretical Computer Science, 2016, 8, July, 2016. · Zbl 1365.68288 · doi:10.4086/cjtcs.2016.008 |
| [36] | Sophie Laplante, Troy Lee, and Mario Szegedy. 2006. THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS. computational complexity, 15, 2, jun, 2006. Pages 163-196. · Zbl 1132.68032 · doi:10.1007/s00037-006-0212-7 |
| [37] | Troy Lee, Adi Shraibman, and Robert Spalek. 2008. A Direct Product Theorem for Discrepancy. In 23rd Annual IEEE Conference on Computational Complexity. · doi:10.1109/ccc.2008.25 |
| [38] | Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. 2007. Complexity measures of sign matrices. Combinatorica, 27, 4, 2007. Pages 439-463. · Zbl 1164.68006 · doi:10.1007/s00493-007-2160-5 |
| [39] | Frédéric Magniez, Miklos Santha, and Mario Szegedy. 2007. Quantum Algorithms for the Triangle Problem. SIAM J. Comput., 37, 2, 2007. Pages 413-424. · Zbl 1166.68032 · doi:10.1137/050643684 |
| [40] | Gatis Midrijanis. 2004. Exact quantum query complexity for total Boolean functions. arXiv preprint quant-ph/0403168, 2004. |
| [41] | Noam Nisan. 1991. CREW PRAMs and Decision Trees. SIAM J. Comput., 20, 6, 1991. Pages 999-1007. · Zbl 0737.68028 · doi:10.1137/0220062 |
| [42] | Noam Nisan and Mario Szegedy. 1994. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity, 4, 4, 1994. Pages 301-313. · Zbl 0829.68047 · doi:10.1007/BF01263419 |
| [43] | Noam Nisan and Avi Wigderson. 1995. On rank vs. communication complexity. Combinatorica, 15, 4, 1995. Pages 557-565. · Zbl 0845.68038 · doi:10.1007/BF01192527 |
| [44] | Ryan O’Donnell. 2009. Analysis of Boolean Functions. Cambridge University Press. · doi:10.1017/cbo9781139814782 |
| [45] | Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A. Servedio. 2005. Every decision tree has an influential variable. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05). Pages 31-39. · doi:10.1109/SFCS.2005.34 |
| [46] | Ben W. Reichardt. 2011. Reflections for Quantum Query Algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’11. Pages 560-569. · Zbl 1373.68230 · doi:10.1137/1.9781611973082.44 |
| [47] | Ronald L. Rivest and Jean Vuillemin. 1976. On recognizing graph properties from adjacency matrices. Theoretical Computer Science, 3, 3, 1976. Pages 371 - 384. issn:0304-3975 https://doi.org/10.1016/0304-3975(76)90053-0 · Zbl 0358.68079 · doi:10.1016/0304-3975(76)90053-0 |
| [48] | David Rubinstein. 1995. Sensitivity vs. block sensitivity of Boolean functions. Combinatorica, 15, 2, 1995. Pages 297-299. · Zbl 0837.68080 · doi:10.1007/BF01200762 |
| [49] | Michael Saks and Avi Wigderson. 1986. Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science. SFCS ’86. Pages 29-38. · doi:10.1109/SFCS.1986.44 |
| [50] | Robert Scheidweiler and Eberhard Triesch. 2013. A Lower Bound for the Complexity of Monotone Graph Properties. SIAM Journal on Discrete Mathematics, 27, 1, 2013. Pages 257-265. · Zbl 1267.68169 · doi:10.1137/120888703 |
| [51] | Alexander A. Sherstov. 2013. Approximating the AND-OR Tree. Theory of Computing, 9, 20, 2013. Pages 653-663. · Zbl 1328.68078 · doi:10.4086/toc.2013.v009a020 |
| [52] | Alexander A. Sherstov. 2013. Making Polynomials Robust to Noise. Theory of Computing, 9, 18, 2013. Pages 593-615. · Zbl 1366.68063 · doi:10.4086/toc.2013.v009a018 |
| [53] | Alexander A Sherstov, Andrey A Storozhenko, and Pei Wu. 2020. An Optimal Separation of Randomized and Quantum Query Complexity. arXiv preprint arXiv:2008.10223, 2020. |
| [54] | Robert Spalek and Mario Szegedy. 2006. All Quantum Adversary Methods are Equivalent. Theory of Computing, 2, 1, 2006. Pages 1-18. · Zbl 1213.68289 · doi:10.4086/toc.2006.v002a001 |
| [55] | Terence Tao. 2008. Structure and randomness : pages from year one of a mathematical blog. American Mathematical Society. isbn:978-0-8218-4695-7 https://terrytao.wordpress.com/2007/09/05/amplification-arbitrage-and-the-tensor-power-trick/ · Zbl 1245.00024 |
| [56] | Martin E. Walter. 1986. On the norm of a Schur product. Linear Algebra Appl., 79, 1986. Pages 209 - 213. issn:0024-3795 https://doi.org/10.1016/0024-3795(86)90300-9 · Zbl 0596.15023 · doi:10.1016/0024-3795(86)90300-9 |
| [57] | Andrew Chi-Chih Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (SFCS 1977). Pages 222-227. · doi:10.1109/SFCS.1977.24 |
| [58] | Andrew Chi-Chih Yao. 1988. Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput., 17, 3, 1988. Pages 517-520. · Zbl 0648.05028 · doi:10.1137/0217031 |
| [59] | Andrew Chi-Chih Yao. 1991. Lower bounds to randomized algorithms for graph properties. J. Comput. System Sci., 42, 3, 1991. Pages 267 - 287. issn:0022-0000 https://doi.org/10.1016/0022-0000(91)90003-N · Zbl 0732.68058 · doi:10.1016/0022-0000(91)90003-N |
| [60] | Scott Aaronson, Shalev Ben-David, and Robin Kothari. 2016. Separations in query complexity using cheat sheets. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016. Pages 863-876. · Zbl 1373.68216 · doi:10.1145/2897518.2897644 |
| [61] | Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. 2020. Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem. arXiv preprint arXiv:2010.12629, 2020. |
| [62] | Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal. 2020. Quantum Implications of Huang’s Sensitivity Theorem. arXiv preprint arXiv:2004.13231, 2020. |
| [63] | Andris Ambainis. 2002. Quantum Lower Bounds by Quantum Arguments. J. Comput. System Sci., 64, 4, jun, 2002. Pages 750-767. · Zbl 1015.68075 · doi:10.1006/jcss.2002.1826 |
| [64] | Andris Ambainis. 2013. Superlinear Advantage for Exact Quantum Algorithms. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC 2013). Pages 891-900. · Zbl 1293.68124 · doi:10.1145/2488608.2488721 |
| [65] | Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. 2017. Separations in Query Complexity Based on Pointer Functions. Journal of the ACM, 64, 5, Sept., 2017. · Zbl 1426.68109 · doi:10.1145/3106234 |
| [66] | T. Ando, Roger A. Horn, and Charles R. Johnson. 1987. The singular values of a Hadamard product: a basic inequality. Linear and Multilinear Algebra, 21, 4, 1987. Pages 345-365. · Zbl 0633.15011 · doi:10.1080/03081088708817810 |
| [67] | Nikhil Bansal and Makrand Sinha. 2020. k-Forrelation Optimally Separates Quantum and Classical Query Complexity. arXiv preprint arXiv:2008.07003, 2020. |
| [68] | Howard Barnum and Michael Saks. 2004. A lower bound on the quantum query complexity of read-once functions. J. Comput. System Sci., 69, 2, 2004. Pages 244 - 258. · Zbl 1083.68045 · doi:10.1016/j.jcss.2004.02.002 |
| [69] | Howard Barnum, Michael E. Saks, and Mario Szegedy. 2003. Quantum query complexity and semi-definite programming. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003). Pages 179-193. · doi:10.1109/CCC.2003.1214419 |
| [70] | Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. 2001. Quantum lower bounds by polynomials. J. ACM, 48, 4, 2001. Pages 778-797. · Zbl 1127.68404 · doi:10.1145/502090.502097 |
| [71] | Shalev Ben-David, Adam Bouland, Ankit Garg, and Robin Kothari. 2018. Classical Lower Bounds from Quantum Upper Bounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pages 339-349. · doi:10.1109/FOCS.2018.00040 |
| [72] | Shalev Ben-David, Pooya Hatami, and Avishay Tal. 2017. Low-Sensitivity Functions from Unambiguous Certificates. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017. LIPIcs. 67, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. Pages 28:1-28:23. · Zbl 1402.68082 · doi:10.4230/LIPIcs.ITCS.2017.28 |
| [73] | Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. 1997. Strengths and Weaknesses of Quantum Computing. SIAM J. Comput., 26, 5, Oct., 1997. Pages 1510-1523. · Zbl 0895.68044 · doi:10.1137/S0097539796300933 |
| [74] | Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. 1999. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science. Pages 358-368. · doi:10.1109/SFFCS.1999.814607 |
| [75] | Harry Buhrman and Ronald de Wolf. 2002. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288, 1, 2002. Pages 21-43. https://doi.org/10.1016/S0304-3975(01)00144-X · Zbl 1061.68058 · doi:10.1016/S0304-3975(01)00144-X |
| [76] | Harry Buhrman, Ilan Newman, Hein Rohrig, and Ronald de Wolf. 2007. Robust polynomials and quantum algorithms. Theory of Computing Systems, 40, 4, 2007. Pages 379-395. · Zbl 1121.68049 · doi:10.1007/s00224-006-1313-z |
| [77] | Mark Bun and Justin Thaler. 2013. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. In Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013. Pages 303-314. · Zbl 1327.68116 · doi:10.1007/978-3-642-39206-1_26 |
| [78] | Mark Bun and Justin Thaler. 2015. Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. In Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015. Pages 268-280. · Zbl 1402.68083 · doi:10.1007/978-3-662-47672-7_22 |
| [79] | Mark Bun and Justin Thaler. 2017. A Nearly Optimal Lower Bound on the Approximate Degree of AC^0. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017). Pages 1-12. · doi:10.1109/FOCS.2017.10 |
| [80] | Amit Chakrabarti and Subhash Khot. 2001. Improved Lower Bounds on the Randomized Complexity of Graph Properties. In Automata, Languages and Programming. Pages 285-296. · Zbl 0986.68036 · doi:10.1007/3-540-48224-5_24 |
| [81] | Yevgeniy Dodis and Sanjeev Khanna. 1999. Space-Time Tradeoffs for Graph Properties. In Automata, Languages and Programming. Pages 291-300. · doi:10.1007/3-540-48523-6_26 |
| [82] | Ehud Friedgut, Jeff Kahn, and Avi Wigderson. 2002. Computing Graph Properties by Randomized Subcube Partitions. In Randomization and Approximation Techniques in Computer Science. Pages 105-113. · Zbl 1028.68567 · doi:10.1007/3-540-45726-7_9 |
| [83] | Justin Gilmer, Michael Saks, and Srikanth Srinivasan. 2013. Composition Limits and Separating Examples for Some Boolean Function Complexity Measures. In Proceedings of 2013 IEEE Conference on Computational Complexity (CCC 2013). Pages 185-196. · doi:10.1109/CCC.2013.27 |
| [84] | Chris Godsil and Gordon Royle. 2001. Algebraic Graph Theory. Springer New York. · Zbl 0968.05002 · doi:10.1007/978-1-4613-0163-9 |
| [85] | Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. 2018. Randomized Communication versus Partition Number. ACM Transactions on Computation Theory, 10, 1, Jan., 2018. · Zbl 1427.68083 · doi:10.1145/3170711 |
| [86] | Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, STOC 1996. Pages 212-219. · Zbl 0922.68044 · doi:10.1145/237814.237866 |
| [87] | Mika Göös, Toniann Pitassi, and Thomas Watson. 2018. Deterministic Communication vs. Partition Number. SIAM J. Comput., 47, 6, 2018. Pages 2435-2450. · Zbl 1409.68115 · doi:10.1137/16M1059369 |
| [88] | Péter Hajnal. 1991. An \Omega (n^4/3) lower bound on the randomized complexity of graph properties. Combinatorica, 11, 2, jun, 1991. Pages 131-143. · Zbl 0743.68076 · doi:10.1007/bf01206357 |
| [89] | Hao Huang. 2019. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Annals of Mathematics, 190, 3, 2019. Pages 949-955. · Zbl 1427.05116 · doi:10.4007/annals.2019.190.3.6 |
| [90] | Jeff Kahn, Michael Saks, and Dean Sturtevant. 1984. A topological approach to evasiveness. Combinatorica, 4, 4, 1984. Pages 297-306. · Zbl 0577.05061 · doi:10.1007/bf02579140 |
| [91] | Valerie King. 1988. Lower Bounds on the Complexity of Graph Properties. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC ’88. Pages 468-476. · doi:10.1145/62212.62258 |
| [92] | Elias Koutsoupias. 1993. Improvements on Khrapchenko’s theorem. Theoretical Computer Science, 116, 2, 1993. Pages 399-403. https://doi.org/10.1016/0304-3975(93)90330-V · Zbl 0777.94022 · doi:10.1016/0304-3975(93)90330-V |
| [93] | Raghav Kulkarni and Supartha Podder. 2016. Quantum Query Complexity of Subgraph Isomorphism and Homomorphism. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs). 47, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Pages 48:1-48:13. · Zbl 1388.68071 · doi:10.4230/LIPIcs.STACS.2016.48 |
| [94] | Raghav Kulkarni and Avishay Tal. 2016. On Fractional Block Sensitivity. Chicago Journal of Theoretical Computer Science, 2016, 8, July, 2016. · Zbl 1365.68288 · doi:10.4086/cjtcs.2016.008 |
| [95] | Sophie Laplante, Troy Lee, and Mario Szegedy. 2006. THE QUANTUM ADVERSARY METHOD AND CLASSICAL FORMULA SIZE LOWER BOUNDS. computational complexity, 15, 2, jun, 2006. Pages 163-196. · Zbl 1132.68032 · doi:10.1007/s00037-006-0212-7 |
| [96] | Troy Lee, Adi Shraibman, and Robert Spalek. 2008. A Direct Product Theorem for Discrepancy. In 23rd Annual IEEE Conference on Computational Complexity. · doi:10.1109/ccc.2008.25 |
| [97] | Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraibman. 2007. Complexity measures of sign matrices. Combinatorica, 27, 4, 2007. Pages 439-463. · Zbl 1164.68006 · doi:10.1007/s00493-007-2160-5 |
| [98] | Frédéric Magniez, Miklos Santha, and Mario Szegedy. 2007. Quantum Algorithms for the Triangle Problem. SIAM J. Comput., 37, 2, 2007. Pages 413-424. · Zbl 1166.68032 · doi:10.1137/050643684 |
| [99] | Gatis Midrijanis. 2004. Exact quantum query complexity for total Boolean functions. arXiv preprint quant-ph/0403168, 2004. |
| [100] | Noam Nisan. 1991. CREW PRAMs and Decision Trees. SIAM J. Comput., 20, 6, 1991. Pages 999-1007. · Zbl 0737.68028 · doi:10.1137/0220062 |
| [101] | Noam Nisan and Mario Szegedy. 1994. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity, 4, 4, 1994. Pages 301-313. · Zbl 0829.68047 · doi:10.1007/BF01263419 |
| [102] | Noam Nisan and Avi Wigderson. 1995. On rank vs. communication complexity. Combinatorica, 15, 4, 1995. Pages 557-565. · Zbl 0845.68038 · doi:10.1007/BF01192527 |
| [103] | Ryan O’Donnell. 2009. Analysis of Boolean Functions. Cambridge University Press. · doi:10.1017/cbo9781139814782 |
| [104] | Ryan O’Donnell, Michael Saks, Oded Schramm, and Rocco A. Servedio. 2005. Every decision tree has an influential variable. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05). Pages 31-39. · doi:10.1109/SFCS.2005.34 |
| [105] | Ben W. Reichardt. 2011. Reflections for Quantum Query Algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’11. Pages 560-569. · Zbl 1373.68230 · doi:10.1137/1.9781611973082.44 |
| [106] | Ronald L. Rivest and Jean Vuillemin. 1976. On recognizing graph properties from adjacency matrices. Theoretical Computer Science, 3, 3, 1976. Pages 371 - 384. issn:0304-3975 https://doi.org/10.1016/0304-3975(76)90053-0 · Zbl 0358.68079 · doi:10.1016/0304-3975(76)90053-0 |
| [107] | David Rubinstein. 1995. Sensitivity vs. block sensitivity of Boolean functions. Combinatorica, 15, 2, 1995. Pages 297-299. · Zbl 0837.68080 · doi:10.1007/BF01200762 |
| [108] | Michael Saks and Avi Wigderson. 1986. Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science. SFCS ’86. Pages 29-38. · doi:10.1109/SFCS.1986.44 |
| [109] | Robert Scheidweiler and Eberhard Triesch. 2013. A Lower Bound for the Complexity of Monotone Graph Properties. SIAM Journal on Discrete Mathematics, 27, 1, 2013. Pages 257-265. · Zbl 1267.68169 · doi:10.1137/120888703 |
| [110] | Alexander A. Sherstov. 2013. Approximating the AND-OR Tree. Theory of Computing, 9, 20, 2013. Pages 653-663. · Zbl 1328.68078 · doi:10.4086/toc.2013.v009a020 |
| [111] | Alexander A. Sherstov. 2013. Making Polynomials Robust to Noise. Theory of Computing, 9, 18, 2013. Pages 593-615. · Zbl 1366.68063 · doi:10.4086/toc.2013.v009a018 |
| [112] | Alexander A Sherstov, Andrey A Storozhenko, and Pei Wu. 2020. An Optimal Separation of Randomized and Quantum Query Complexity. arXiv preprint arXiv:2008.10223, 2020. |
| [113] | Robert Spalek and Mario Szegedy. 2006. All Quantum Adversary Methods are Equivalent. Theory of Computing, 2, 1, 2006. Pages 1-18. · Zbl 1213.68289 · doi:10.4086/toc.2006.v002a001 |
| [114] | Terence Tao. 2008. Structure and randomness : pages from year one of a mathematical blog. American Mathematical Society. isbn:978-0-8218-4695-7 https://terrytao.wordpress.com/2007/09/05/amplification-arbitrage-and-the-tensor-power-trick/ · Zbl 1245.00024 |
| [115] | Martin E. Walter. 1986. On the norm of a Schur product. Linear Algebra Appl., 79, 1986. Pages 209 - 213. issn:0024-3795 https://doi.org/10.1016/0024-3795(86)90300-9 · Zbl 0596.15023 · doi:10.1016/0024-3795(86)90300-9 |
| [116] | Andrew Chi-Chih Yao. 1977. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science (SFCS 1977). Pages 222-227. · doi:10.1109/SFCS.1977.24 |
| [117] | Andrew Chi-Chih Yao. 1988. Monotone Bipartite Graph Properties are Evasive. SIAM J. Comput., 17, 3, 1988. Pages 517-520. · Zbl 0648.05028 · doi:10.1137/0217031 |
| [118] | Andrew Chi-Chih Yao. 1991. Lower bounds to randomized algorithms for graph properties. J. Comput. System Sci., 42, 3, 1991. Pages 267 - 287. issn:0022-0000 https://doi.org/10.1016/0022-0000(91)90003-N · Zbl 0732.68058 · doi:10.1016/0022-0000(91)90003-N |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
