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