[1]   Scott Aaronson: Impossibility of succinct quantum proofs for collision-freeness. Quantum Inf. Comput., 12(1-2):21–28, 2012. [arXiv:1101.0403]

[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]

[3]   Scott Aaronson and Yaoyun Shi: Quantum lower bounds for the collision and the element distinctness problems. J. ACM, 51(4):595–605, 2004. Preliminary version in  STOC’02. [doi:10.1145/1008731.1008735]

[4]   Miklós Ajtai: Σ₁¹-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1–48, 1983. [doi:10.1016/0168-0072(83)90038-6]

[5]   Andris Ambainis: Quantum lower bounds by quantum arguments. J. Comput. System Sci., 64(4):750–767, 2002. Preliminary version in  STOC’00. [doi:10.1006/jcss.2002.1826]

[6]   Andris Ambainis: Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(3):37–46, 2005. [doi:10.4086/toc.2005.v001a003]

[7]   Andris Ambainis: Polynomial degree vs. quantum query complexity. J. Comput. System Sci., 72(2):220–238, 2006. Preliminary version in FOCS’03. [doi:10.1016/j.jcss.2005.06.006]

[8]   Andris Ambainis: Quantum walk algorithm for element distinctness. SIAM J. Comput., 37(1):210–239, 2007. Preliminary version in  FOCS’04. [doi:10.1137/S0097539705447311]

[9]   Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf: Efficient quantum algorithms for (gapped) group testing and junta testing. In Proc. 27th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’16), pp. 903–922. ACM Press, 2016. [doi:10.1137/1.9781611974331.ch65]

[10]   Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Špalek, and Shengyu Zhang: Any AND-OR formula of size N can be evaluated in time N^1∕2+o(1) on a quantum computer. SIAM J. Comput., 39(6):2513–2530, 2010. Preliminary version in FOCS’07. [doi:10.1137/080712167]

[11]   Alp Atc and Rocco A. Servedio: Quantum algorithms for learning and testing juntas. Quantum Information Processing, 6(5):323–348, 2007. [doi:10.1007/s11128-007-0061-6]

[12]   Howard Barnum, Michael Saks, and Mario Szegedy: Quantum query complexity and semi-definite programming. In Proc. 18th IEEE Conf. on Computational Complexity (CCC’03), pp. 179–193. IEEE Comp. Soc., 2003. [doi:10.1109/CCC.2003.1214419]

[13]   Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Preliminary version in  FOCS’98. [doi:10.1145/502090.502097]

[14]   Paul Beame and Widad Machmouchi: The quantum query complexity of AC. Quantum Inf. Comput., 12(7–8):670–676, 2012. Link at ACM DL. [arXiv:1008.2422]

[15]   Richard Beigel: Perceptrons, PP, and the polynomial hierarchy. Comput. Complexity, 4:339–349, 1994. Preliminary version in  SCT’92. [doi:10.1007/BF01263422]

[16]   Aleksandrs Belovs: Learning-graph-based quantum algorithm for k-distinctness. In Proc. 53rd FOCS, pp. 207–216. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.18]

[17]   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]

[18]   Aleksandrs Belovs and Robert Špalek: Adversary lower bound for the k-sum problem. In Proc. 4th Symp. Innovations in Theoretical Computer Science (ITCS’13), pp. 323–328. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013. [doi:10.1145/2422436.2422474]

[19]   Eric Blais: Testing juntas nearly optimally. In Proc. 41st STOC, pp. 151–158. ACM Press, 2009. [doi:10.1145/1536414.1536437]

[20]   Andrej Bogdanov, Yuval Ishai, Emanuele Viola, and Christopher Williamson: Bounded indistinguishability and the complexity of recovering secrets. In Proc. 36th Annual Intern. Cryptology Conf. (CRYPTO’16), pp. 593–618, 2016. [doi:10.1007/978-3-662-53015-3_21]

[21]   Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan: On the power of statistical zero knowledge. SIAM J. Comput., 49(4):1–58, 2019. Preliminary version in FOCS’17. [doi:10.1137/17M1161749]

[22]   Gilles Brassard, Peter Høyer, and Alain Tapp: Quantum counting. In Proc. 25th Internat. Colloq. on Automata, Languages and Programming (ICALP’98), pp. 820–831. Springer, 1998. [doi:10.1007/BFb0055105]

[23]   Sergey Bravyi, Aram Wettroth Harrow, and Avinatan Hassidim: Quantum algorithms for testing properties of distributions. IEEE Trans. Inform. Theory, 57(6):3971–3981, 2011. Preliminary version in  STACS’10. [doi:10.1109/TIT.2011.2134250]

[24]   Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc., 1999. [doi:10.1109/SFFCS.1999.814607]

[25]   Harry Buhrman, Ilan Newman, Hein Röhrig, and Ronald de Wolf: Robust polynomials and quantum algorithms. Theory Comput. Syst., 40(4):379–395, 2007. Preliminary version in  STACS’05. [doi:10.1007/s00224-006-1313-z]

[26]   Harry Buhrman and Robert Špalek: Quantum verification of matrix products. In Proc. 17th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’06), pp. 880–889. ACM Press, 2006. Link at ACM DL.

[27]   Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf: On computation and communication with small bias. In Proc. 22nd IEEE Conf. on Computational Complexity (CCC’07), pp. 24–32. IEEE Comp. Soc., 2007. [doi:10.1109/CCC.2007.18]

[28]   Mark Bun, Robin Kothari, and Justin Thaler: The polynomial method strikes back: Tight quantum query bounds via dual polynomials. In Proc. 50th STOC, pp. 297–310. ACM Press, 2018. [doi:10.1145/3188745.3188784]

[29]   Mark Bun and Justin Thaler: Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inform. Comput., 243:2–25, 2015. Preliminary version in ICALP’13. [doi:10.1016/j.ic.2014.12.003]

[30]   Mark Bun and Justin Thaler: Hardness amplification and the approximate degree of constant-depth circuits. In Proc. 42nd Internat. Colloq. on Automata, Languages and Programming (ICALP’15), pp. 268–280. Springer, 2015. [doi:10.1007/978-3-662-47672-7_22]

[31]   Mark Bun and Justin Thaler: Dual polynomials for collision and element distinctness. Theory of Computing, 12(16):1–34, 2016. [doi:10.4086/toc.2016.v012a016]

[32]   Mark Bun and Justin Thaler: Improved bounds on the sign-rank of AC⁰. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 37:1–37:14. Schloss Dagstuhl–Leibniz-Zentr. fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.37]

[33]   Mark Bun and Justin Thaler: A nearly optimal lower bound on the approximate degree of AC⁰. In Proc. 58th FOCS, pp. 1–12. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.10]

[34]   Mark Bun and Justin Thaler: The large-error approximate degree of AC⁰. In Proc. 23rd Internat. Workshop on Randomization and Computation (RANDOM’19), pp. 55:1–55:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.55]

[35]   Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan: Faster private release of marginals on small databases. In Proc. 5th Symp. Innovations in Theoretical Computer Science (ITCS’14), pp. 387–402. ACM Press, 2014. [doi:10.1145/2554797.2554833]

[36]   Arkadev Chattopadhyay and Anil Ada: Multiparty communication complexity of disjointness. Electron. Colloq. Comput. Complexity, TR08-002:1–15, 2008. [ECCC]

[37]   E.W. Cheney: Introduction to Approximation Theory. AMS Chelsea Pub., 1982.

[38]   Matei David and Toniann Pitassi: Separating NOF communication complexity classes RP and NP. Electron. Colloq. Comput. Complexity, TR08-014:1–11, 2008. [ECCC]

[39]    Matei David, Toniann Pitassi, and Emanuele Viola: Improved separations between nondeterministic and randomized multiparty communication. ACM Trans. Comput. Theory, 1(2):5:1–5:20, 2009. Preliminary version in  RANDOM’08. [doi:10.1145/1595391.1595392]

[40]   Yuval Filmus, Hamed Hatami, Steven Heilman, Elchanan Mossel, Ryan O’Donnell, Sushant Sachdeva, Andrew Wan, and Karl Wimmer: Real analysis in computer science: A collection of open problems, 2014. Preprint at the Simons Institute.

[41]   Dmitry Gavinsky and Alexander A. Sherstov: A separation of NP and coNP in multiparty communication complexity. Theory of Computing, 6(10):227–245, 2010. [doi:10.4086/toc.2010.v006a010]

[42]   Oded Goldreich and Salil P. Vadhan: On the complexity of computational problems regarding distributions (a survey). In Oded Goldreich, editor, Studies in Complexity and Cryptography, volume 6650 of LNCS, pp. 390–405. Springer, 2011. [doi:10.1007/978-3-642-22670-0_27, ECCC:TR11-004]

[43]   Ronald L. Graham, Donald E. Knuth, and Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science. Addison–Wesley, 2nd edition, 1994.

[44]   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]

[45]   Jeff Kahn, Nathan Linial, and Alex Samorodnitsky: Inclusion-exclusion: Exact and approximate. Combinatorica, 16(4):465–477, 1996. [doi:10.1007/BF01271266]

[46]   Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio: Agnostically learning halfspaces. SIAM J. Comput., 37(6):1777–1805, 2008. Preliminary version in  FOCS’05. [doi:10.1137/060649057]

[47]   Varun Kanade and Justin Thaler: Distribution-independent reliable learning. In Proc. 27th Ann. Conf. on Learning Theory (COLT’14), pp. 3–24, 2014. MLR Press. [arXiv:1402.5164]

[48]   Hartmut Klauck, Robert Špalek, and Ronald de Wolf: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM J. Comput., 36(5):1472–1493, 2007. Preliminary version in  FOCS’04. [doi:10.1137/05063235X]

[49]   Adam R. Klivans and Rocco A. Servedio: Learning DNF in time 2^Õ(n1∕3) . J. Comput. System Sci., 68(2):303–318, 2004. Prelim. version in STOC’01. [doi:10.1016/j.jcss.2003.07.007]

[50]   Adam R. Klivans and Rocco A. Servedio: Toward attribute efficient learning of decision lists and parities. J. Mach. Learn. Res., 7:587–602, 2006. JMLR, prelim. version in COLT’04.

[51]   Robin Kothari and Ashwin Nayak: Quantum algorithms for matrix multiplication and product verification. In Encyclopedia of Algorithms, pp. 1673–1677. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_303]

[52]   Sophie Laplante and Frédéric Magniez: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments. SIAM J. Comput., 38(1):46–62, 2008. Preliminary version in  CCC’04. [doi:10.1137/050639090]

[53]   François Le Gall: Improved quantum algorithm for triangle finding via combinatorial arguments. In Proc. 55th FOCS, pp. 216–225. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.31]

[54]   Troy Lee: A note on the sign degree of formulas, 2009. [arXiv:0909.4607]

[55]   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., 2011. [doi:10.1109/FOCS.2011.75]

[56]   Troy Lee and Adi Shraibman: An approximation algorithm for approximation rank. In Proc. 24th IEEE Conf. on Computational Complexity (CCC’09), pp. 351–357. IEEE Comp. Soc., 2009. [doi:10.1109/CCC.2009.25]

[57]   Troy Lee and Adi Shraibman: Disjointness is hard in the multiparty number-on-the-forehead model. Comput. Complexity, 18(2):309–336, 2009. Preliminary version in  CCC’08. [doi:10.1007/s00037-009-0276-2]

[58]   Tongyang Li and Xiaodi Wu: Quantum query complexity of entropy estimation. IEEE Trans. Inform. Theory, 65(5):2899–2921, 2018. [doi:10.1109/TIT.2018.2883306]

[59]   Frédéric Magniez, Miklos Santha, and Mario Szegedy: Quantum algorithms for the triangle problem. SIAM J. Comput., 37(2):413–424, 2007. Preliminary version in  SODA’05. [doi:10.1137/050643684]

[60]   Marvin Minsky and Seymour Papert: Perceptrons – An Introduction to Computational Geometry. MIT Press, 1969. [doi:10.7551/mitpress/11301.001.0001]

[61]   Ashley Montanaro: The quantum complexity of approximating the frequency moments. Quantum Inf. Comput., 16(13–14):1169–1190, 2016. Link at ACM DL. [arXiv:1505.00113]

[62]   Noam Nisan and Mario Szegedy: On the degree of Boolean functions as real polynomials. Comput. Complexity, 4(4):301–313, 1994. Preliminary version in  STOC’92. [doi:10.1007/BF01263419]

[63]   Ryan O’Donnell and Rocco A. Servedio: New degree bounds for polynomial threshold functions. Combinatorica, 30(3):327–358, 2010. Preliminary version in  STOC’03. [doi:10.1007/s00493-010-2173-3]

[64]   Anup Rao and Amir Yehudayoff: Simplified lower bounds on the multiparty communication complexity of disjointness. In Proc. 30th IEEE Conf. on Computational Complexity (CCC’15), pp. 88–101. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.CCC.2015.88]

[65]   Alexander A. Razborov and Alexander A. Sherstov: The sign-rank of AC⁰. SIAM J. Comput., 39(5):1833–1855, 2010. Prelim. version FOCS’08. [doi:10.1137/080744037]

[66]   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]

[67]   Amit Sahai and Salil Vadhan: A complete problem for statistical zero knowledge. J. ACM, 50(2):196–249, 2003. Preliminary version in  FOCS’97. [doi:10.1145/636865.636868]

[68]   Rocco A. Servedio, Li-Yang Tan, and Justin Thaler: Attribute-efficient learning and weight–degree tradeoffs for polynomial threshold functions. In Proc. 25th Ann. Conf. on Learning Theory (COLT’12), pp. 14:1–14:19, 2012. MLR Press.

[69]   Alexander A. Sherstov: Communication lower bounds using dual polynomials. Bull. EATCS, 95:59–93, 2008. [ECCC:TR08-057]

[70]   Alexander A. Sherstov: Approximate inclusion-exclusion for arbitrary symmetric functions. Comput. Complexity, 18(2):219–247, 2009. Preliminary version in  CCC’08. [doi:10.1007/s00037-009-0274-4]

[71]   Alexander A. Sherstov: Separating AC⁰ from depth-2 majority circuits. SIAM J. Comput., 38(6):2113–2129, 2009. Preliminary version in  STOC’07. [doi:10.1137/08071421X]

[72]   Alexander A. Sherstov: The pattern matrix method. SIAM J. Comput., 40(6):1969–2000, 2011. Preliminary version in STOC’08. [doi:10.1137/080733644]

[73]   Alexander A. Sherstov: Approximating the AND-OR tree. Theory of Computing, 9(20):653–663, 2013. [doi:10.4086/toc.2013.v009a020]

[74]   Alexander A. Sherstov: Communication lower bounds using directional derivatives. In Proc. 45th STOC, pp. 921–930. ACM Press, 2013. [doi:10.1145/2488608.2488725]

[75]   Alexander A. Sherstov: The intersection of two halfspaces has high threshold degree. SIAM J. Comput., 42(6):2329–2374, 2013. [doi:10.1137/100785260]

[76]   Alexander A. Sherstov: Making polynomials robust to noise. Theory of Computing, 9(18):593–615, 2013. Preliminary version in  STOC’12. [doi:10.4086/toc.2013.v009a018]

[77]   Alexander A. Sherstov: The multiparty communication complexity of set disjointness. SIAM J. Comput., 45(4):1450–1489, 2016. Preliminary version in  STOC’12. [doi:10.1137/120891587]

[78]   Alexander A. Sherstov: Algorithmic polynomials. In Proc. 50th STOC, pp. 311–324. ACM Press, 2018. Journal v. to appear in SIAM J. Comp. [doi:10.1145/3188745.3188958]

[79]   Alexander A. Sherstov: Breaking the Minsky–Papert barrier for constant-depth circuits. SIAM J. Comput., 47(5):1809–1857, 2018. Prelim. v. STOC’14. [doi:10.1137/15M1015704]

[80]   Alexander A. Sherstov: The power of asymmetry in constant-depth circuits. SIAM J. Comput., 47(6):2362–2434, 2018. Preliminary version in  FOCS’15. [doi:10.1137/16M1064477]

[81]   Yaoyun Shi and Yufan Zhu: Quantum communication complexity of block-composed functions. Quantum Inf. Comput., 9(5):444–460, 2009. [arXiv:0710.0095]

[82]   Robert Špalek: A dual polynomial for OR, 2008. [arXiv:0803.4516]

[83]   Robert Špalek and Mario Szegedy: All quantum adversary methods are equivalent. Theory of Computing, 2(1):1–18, 2006. Prelim. version ICALP’05. [doi:10.4086/toc.2006.v002a001]

[84]   Avishay Tal: Shrinkage of De Morgan formulae by spectral techniques. In Proc. 55th FOCS, pp. 551–560. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.65]

[85]   Avishay Tal: Formula lower bounds via the quantum method. In Proc. 49th STOC, pp. 1256–1268. ACM Press, 2017. [doi:10.1145/3055399.3055472]

[86]    Justin Thaler: Lower bounds for the approximate degree of block-composed functions. In Proc. 43rd Internat. Colloq. on Automata, Languages and Programming (ICALP’16), pp. 17:1–17:15. Schloss Dagstuhl–Leibniz-Zentr. fuer Informatik, 2016. [doi:10.4230/LIPIcs.ICALP.2016.17]

[87]   Justin Thaler, Jonathan Ullman, and Salil P. Vadhan: Faster algorithms for privately releasing marginals. In Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP’12), pp. 810–821. Springer, 2012. [doi:10.1007/978-3-642-31594-7_68]

[88]   Salil Pravin Vadhan: A Study of Statistical Zero-knowledge Proofs. Ph. D. thesis, Massachusetts Institute of Technology, 1999. Link at Springer.

[89]   Gregory Valiant and Paul Valiant: Estimating the unseen: An n∕log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. In Proc. 43rd STOC, pp. 685–694. ACM Press, 2011. [doi:10.1145/1993636.1993727]

[90]   Emanuele Viola: Special Topics in Complexity Theory. Lecture notes, Northeastern Univ., 2017. ECCC.

[91]   Mark Zhandry: A note on the quantum collision and set equality problems. Quantum Inf. Comput., 15(7&8):557–567, 2015. Link at ACM DL. [arXiv:1312.1027]

[92]   Shengyu Zhang: On the power of Ambainis lower bounds. Theoret. Comput. Sci., 339(2):241–256, 2005. Preliminary version in  ICALP’04. [doi:10.1016/j.tcs.2005.01.019]