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 Hyer, 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 Brit, Sourav Chakraborty, David Garca-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) n12 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 Hyer, 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, Frdric 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]