Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Theory of Computing, Volume 11(16), pp. 403-412, 2015
Bibliography with links to cited articles
[1] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf: Efficient quantum algorithms for (gapped) group testing and junta testing. Preprint, 2015. To appear in SODA’16. [arXiv:1507.03126]
[2] Aleksandrs Belovs: Learning-graph-based quantum algorithm for k-distinctness. In Proc. 53rd FOCS, pp. 207–216. IEEE Comp. Soc. Press, 2012. [doi:10.1109/FOCS.2012.18, arXiv:1205.1534]
[3] Aleksandrs Belovs: Span programs for functions with constant-sized 1-certificates. In Proc. 44th STOC, pp. 77–84. ACM Press, 2012. [doi:10.1145/2213977.2213985, arXiv:1105.4024]
[4] Aleksandrs Belovs: Quantum algorithms for learning symmetric juntas via the adversary bound. Comput. Complexity, 24(2):255–293, 2015. Preliminary version in CCC’14. [doi:10.1007/s00037-015-0099-2, arXiv:1311.6777]
[5] Aleksandrs Belovs and Ben W. Reichardt: Span programs and quantum algorithms for st-connectivity and claw detection. In Proc. 20th Ann. European Symp. on Algorithms (ESA’12), volume 7501 of LNCS, pp. 193–204, 2012. [doi:10.1007/978-3-642-33090-2_18, arXiv:1203.2603]
[6] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp: Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pp. 53–74, 2002. [doi:10.1090/conm/305, arXiv:quant-ph/0005055]
[7] Jop Briët, Sourav Chakraborty, David García-Soriano, and Arie Matsliah: Monotonicity testing and shortest-path routing on the cube. Combinatorica, 32(1):35–53, 2012. Preliminary versions in RANDOM’10 and ECCC. [doi:10.1007/s00493-012-2765-1]
[8] Harry Buhrman and Ronald de Wolf: Complexity measures and decision tree complexity: a survey. Theoret. Comput. Sci., 288(1):21–43, 2002. [doi:10.1016/S0304-3975(01)00144-X]
[9] Deeparnab Chakrabarty and Comandur Seshadhri: A o(n) monotonicity tester for boolean functions over the hypercube. In Proc. 45th STOC, pp. 411–418. ACM Press, 2013. [doi:10.1145/2488608.2488660, arXiv:1302.4536]
[10] Xi Chen, Anindya De, Rocco A. Servedio, and Li-Yang Tan: Boolean function monotonicity testing requires (almost) n1∕2 non-adaptive queries. In Proc. 47th STOC, pp. 519–528. ACM Press, 2015. [doi:10.1145/2746539.2746570, arXiv:1412.5657]
[11] Xi Chen, Rocco A. Servedio, and Li-Yang Tan: New algorithms and lower bounds for monotonicity testing. In Proc. 55th FOCS, pp. 286–295. IEEE Comp. Soc. Press, 2014. [doi:10.1109/FOCS.2014.38, arXiv:1412.5655]
[12] Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, and Alex Samorodnitsky: Monotonicity testing over general poset domains. In Proc. 34th STOC, pp. 474–483. ACM Press, 2002. [doi:10.1145/509907.509977]
[13] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky: Testing monotonicity. Combinatorica, 20(3):301–337, 2000. Preliminary version in FOCS’98. [doi:10.1007/s004930070011]
[14] 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]
[15] Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Junichi Teruyama: Quantum counterfeit coin problems. Theoret. Comput. Sci., 456:51–64, 2012. Preliminary version in ISAAC’10. [doi:10.1016/j.tcs.2012.05.039, arXiv:1009.0416]
[16] Subhash Khot, Dor Minzer, and Muli Safra: On monotonicity testing and boolean isoperimetric type theorems. In Proc. 56th FOCS, pp. 52–58. IEEE Comp. Soc. Press, 2015. ECCC 2015/011. [doi:10.1109/FOCS.2015.13]
[17] Troy Lee, Frédéric Magniez, and Miklos Santha: Improved quantum query algorithms for triangle finding and associativity testing. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1486–1502. ACM Press, 2013. [doi:10.1137/1.9781611973105.107, arXiv:1210.1014]
[18] 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]
[19] Ashley Montanaro and Ronald de Wolf: A Survey of Quantum Property Testing. Preprint, 2013. To appear as a Theory of Computing Graduate Survey. [arXiv:1310.2035]
[20] Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, 2014.
[21] Ben W. Reichardt: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In Proc. 50th FOCS, pp. 544–551. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.55, arXiv:0904.2759]
[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, arXiv:1005.1601]
[23] Ben W. Reichardt and Robert Špalek: Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291–319, 2012. Preliminary version in STOC’08. [doi:10.4086/toc.2012.v008a013]
[24] Wim van Dam and Igor E. Shparlinski: Classical and quantum algorithms for exponential congruences. In Proc. 3rd Conf. Theory of Quantum Comput., Communic. and Cryptography (TQC’08), volume 5106 of LNCS, pp. 1–10. Springer, 2008. [doi:10.1007/978-3-540-89304-2_1, arXiv:0804.1109]
[25] Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim: Super-polynomial quantum speed-ups for Boolean evaluation trees with hidden structure. In Proc. 3rd Symp. Innovations in Theoretical Computer Science (ITCS’12), pp. 249–265. ACM Press, 2012. [doi:10.1145/2090236.2090258, arXiv:1101.0796]