On the Probabilistic Degree of an $n$-variate Boolean Function

by Srikanth Srinivasan and S. Venkitesh

Theory of Computing, Volume 22(2072), pp. 1-27, 2026

Bibliography with links to cited articles

[1]   Josh Alman, Timothy M. Chan, and R. Ryan Williams: Polynomial representations of threshold functions and algorithmic applications. In Proc. 57th FOCS, pp. 467–476. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.57]

[2]   Josh Alman and R. Ryan Williams: Probabilistic polynomials and Hamming nearest neighbors. In Proc. 56th FOCS, pp. 136–150. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.18]

[3]   Noga Alon and Joel H. Spencer: The Probabilistic Method. Wiley, 3rd edition, 2008. [doi:10.1002/9780470277331]

[4]   Andris Ambainis and Ronald de Wolf: How low can approximate degree and quantum query complexity be for total Boolean functions? Comput. Complexity, 23(2):305–322, 2014. Preliminary version in CCC’13. [doi:10.1007/s00037-014-0083-2]

[5]   James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich: The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994. [doi:10.1007/BF01215346]

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

[7]   Richard Beigel: The polynomial method in circuit complexity. In Proc. 8th IEEE Conf. Structure in Complexity Theory (SCT’93), pp. 82–95. IEEE Comp. Soc., 1993. [doi:10.1109/SCT.1993.336538]

[8]   Richard Beigel, Nick Reingold, and Daniel Spielman: The perceptron strikes back. In Proc. 6th IEEE Conf. Structure in Complexity Theory (SCT’91), pp. 286–291. IEEE Comp. Soc., 1991. [doi:10.1109/SCT.1991.160270]

[9]   Mark Braverman: Polylogarithmic independence fools AC0 circuits. J. ACM, 57(5):28:1–10, 2010. [doi:10.1145/1754399.1754401]

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

[11]   Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova: Learning algorithms from natural proofs. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 10:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.10]

[12]   Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan: Near-optimal small-depth lower bounds for small distance connectivity. In Proc. 48th STOC, pp. 612–625. ACM Press, 2016. [doi:10.1145/2897518.2897534]

[13]   John Chiarelli, Pooya Hatami, and Michael E. Saks: An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function. Combinatorica, 40(2):237–244, 2020. [doi:10.1007/s00493-019-4136-7]

[14]   Alexander Golovnev, Alexander S. Kulikov, and R. Ryan Williams: Circuit depth reductions. In Proc. 12th Innovations in Theoret. Comp. Sci. Conf. (ITCS’21), pp. 24:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.ITCS.2021.24]

[15]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866]

[16]   Prahladh Harsha and Srikanth Srinivasan: On polynomial approximations to AC0. Random Struct. Algor., 54(2):289–303, 2019. [doi:10.1002/rsa.20786]

[17]   Johan Håstad, Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan: An average-case depth hierarchy theorem for Boolean circuits. J. ACM, 64(5):35:1–27, 2017. [doi:10.1145/3095799]

[18]   Hao Huang: Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Ann. Math., 190(3):949–955, 2019. [doi:10.4007/annals.2019.190.3.6]

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

[20]   Michael Mitzenmacher and Eli Upfal: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge Univ. Press, USA, 2nd edition, 2017. [doi:10.1017/CBO9780511813603]

[21]   Noam Nisan: CREW PRAMs and decision trees. SIAM J. Comput., 20(6):999–1007, 1991. Preliminary version in STOC’89. [doi:10.1137/0220062]

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

[23]   Ryan O’Donnell: Analysis of Boolean Functions. Cambridge Univ. Press, USA, 2014. [doi:10.1017/CBO9781139814782]

[24]   Alexander A. Razborov: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki, 41(4):598–607, 1987. An English translation in Math. Notes, 41(4):333–338, 1987. [doi:10.1007/BF01137685]

[25]   Alexander Schrijver: Theory of Linear and Integer Programming. Wiley, 1998. Available at Wiley.

[26]   Hans-Ulrich Simon: A tight ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated Boolean functions. Inform. Control, 55(1–3):102–106, 1982. Preliminary version in FCT’93. [doi:10.1016/S0019-9958(82)90477-6]

[27]   Roman Smolensky: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In Alfred V. Aho, editor, Proc. 19th STOC, pp. 77–82. ACM Press, 1987. [doi:10.1145/28395.28404]

[28]   Srikanth Srinivasan and S. Venkitesh: On the probabilistic degree of an n  -variate Boolean function. In Proc. 25th Internat. Conf. on Randomization and Computation (RANDOM’21), pp. 42:1–20. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2021. [doi:10.4230/LIPIcs.APPROX/RANDOM.2021.42]

[29]   Jun Tarui: Probabilistic polynomials, AC0 functions and the polynomial-time hierarchy. Theoret. Comput. Sci., 113(1):167–183, 1993. [doi:10.1016/0304-3975(93)90214-E]

[30]   Emanuele Viola: New lower bounds for probabilistic degree and AC0 with parity gates. Electron. Colloq. Comput. Complexity, TR20-015, 2020. [ECCC]

[31]   R. Ryan Williams: Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965–1985, 2018. [doi:10.1137/15M1024524]

[32]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th FOCS, pp. 222–227. IEEE Comp. Soc., 1977. [doi:10.1109/SFCS.1977.24]