×

On the probabilistic degrees of symmetric Boolean functions. (English) Zbl 1527.68088

Summary: The probabilistic degree of a Boolean function \(f:\{0,1\}^n\rightarrow \{0,1\}\) is defined to be the smallest \(d\) such that there is a random polynomial \({P}\) of degree at most \(d\) that agrees with \(f\) at each point with high probability. Introduced by A. A. Razborov [Math. Notes 41, 333–338 (1987; Zbl 0632.94030); translation from Mat. Zametki 41, No. 4, 598–607 (1987)], upper and lower bounds on probabilistic degrees of Boolean functions – specifically symmetric Boolean functions – have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems. In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).

MSC:

68Q25 Analysis of algorithms and problem complexity
06E30 Boolean functions
68Q06 Networks and circuits as models of computation; circuit complexity
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 0632.94030
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Alman and R. Williams, Probabilistic polynomials and hamming nearest neighbors, in Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2015, pp. 136-150, https://doi.org/10.1109/FOCS.2015.18.
[2] R. Beigel, The polynomial method in circuit complexity, in Proceedings of the 8th Annual Structure in Complexity Theory Conference, pp. 82-95, https://doi.org/10.1109/SCT.1993.336538, 1993.
[3] S. Bhandari, P. Harsha, T. Molli, and S. Srinivasan, On the probabilistic degree of OR over the reals, in Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018), LIPIcs. Leibniz Int. Proc. Inform., S. Ganguly and P. Pandya, eds., pp. 5:1-5:12, https://doi.org/10.4230/LIPIcs.FSTTCS.2018.0. · Zbl 1524.68131
[4] M. Braverman, Polylogarithmic independence fools \(AC^0[øplus]\) circuits, J. ACM, 57 (2010), https://doi.org/10.1145/1754399.1754401. · Zbl 1327.68108
[5] R. Beigel, N. Reingold, and D. A. Spielman, The perceptron strikes back, in Proceedings of the 6th Annual Structure in Complexity Theory Conference, Chicago, IL, 1991, pp. 286-291, https://doi.org/10.1109/SCT.1991.160270.
[6] B. Brustmann and I. Wegener, The complexity of symmetric functions in bounded-depth circuits, Inf. Process. Lett., 25 (1987), pp. 217-219, https://doi.org/10.1016/0020-0190(87)90163-3. · Zbl 0653.68019
[7] D. P. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms, Cambridge University Press, Cambridge, 2009. · Zbl 1213.60006
[8] R. Fagin, M. M. Klawe, N. Pippenger, and L. J. Stockmeyer, Bounded-depth, polynomial-size circuits for symmetric functions, Theoret. Comput. Sci., 36 (1985), pp. 239-250, https://doi.org/10.1016/0304-3975(85)90045-3. · Zbl 0574.94024
[9] P. Harsha and S. Srinivasan, On polynomial approximations to \(\text{AC}^0\), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques in Proceedings of LIPIcs. Leibniz Int. Proc. Inform. 61, K. Jansen, C. Mathieu, J. D. P. Rolim, and C. Umans, eds., 2016, pp. 32:1-32:14, https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.32.
[10] D. L. Johnson, D. L. Johnson, and S. S. Johnson, Topics in the theory of group presentations, London Math. Soc. Lecture Note Ser. 42, Cambridge University Press, Cambridge, 1980, https://doi.org/10.1017/CBO9780511629303. · Zbl 0437.20026
[11] N. Linial and N. Nisan, Approximate inclusion-exclusion, Combinatorica, 10 (1990), pp. 349-365, https://doi.org/10.1007/BF02128670. · Zbl 0738.05009
[12] C.-J. Lu, An exact characterization of symmetric functions in \({qAC}^0[2]\), Theoret. Comput. Sci., 261 (2001), pp. 297-303, https://doi.org/10.1016/S0304-3975(00)00145-6. · Zbl 0972.68090
[13] E. Lucas, Théorie des fonctions numériques simplement périodiques, Amer. J. Math., pp. 289-321, https://doi.org/10.2307/2369308, 1878. · JFM 10.0134.05
[14] R. Meka, O. Nguyen, and V. Vu, Anti-concentration for polynomials of independent random variables, Theory Comput., 12 (2016), pp. 1-17, https://doi.org/10.4086/toc.2016.v012a011. · Zbl 1392.68193
[15] R. O’Donnell, Analysis of Boolean Functions, Cambridge University Press, Cambridge, 2014, https://doi.org/10.1017/CBO9781139814782. · Zbl 1336.94096
[16] R. Paturi, On the degree of polynomials that approximate symmetric Boolean functions (preliminary version), in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 468-474, https://doi.org/10.1145/129712.129758.
[17] A. A. Razborov, Lower bounds on the size of bounded depth circuits over a complete basis with logical addition, Mat. Zametki, 41 (1987), pp. 598-607 (in English). · Zbl 0632.94030
[18] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 77-82, https://doi.org/10.1145/28395.28404.
[19] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, New York, 1987, pp. 77-82, https://doi.org/10.1145/28395.28404.
[20] R. Smolensky, On representations by low-degree polynomials, in Proceedings of the 34th Annual Foundations of Computer Science, IEEE, 1993, pp. 130-138, https://doi.org/10.1109/SFCS.1993.366874.
[21] R. Smolensky, On representations by low-degree polynomials, in Proceedings of FOCS, 1993, pp. 130-138, https://doi.org/10.1109/SFCS.1993.366874.
[22] S. Srinivasan, U. Tripathi, and S. Venkitesh, On the probabilistic degrees of symmetric Boolean functions, in Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, A. Chattopadhyay and P. Gastin, eds., LIPIcs. Int. Proc. Inform. ISO, 2019, pp. 28:1-28:14, https://doi.org/10.4230/LIPIcs.FSTTCS.2019.28. · Zbl 1527.68089
[23] J. Tarui, Probablistic polynomials, \(ac^0\) functions, and the polynomial-time hierarchy, Theoret. Comput. Sci., 113 (1993), pp. 167-183, https://doi.org/10.1016/0304-3975(93)90214-E. · Zbl 0783.68047
[24] R. R. Williams, The polynomial method in circuit complexity applied to algorithm design (invited talk), in Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014), 2014, https://doi.org/10.4230/LIPIcs.FSTTCS.2014.47. · Zbl 1436.68392
[25] Z. L. Zhang, D. A. Mix Barrington, and J. Tarui Computing symmetric functions with AND/OR circuits and a single MAJORITY gate, in Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science, Springer, New York, 1993, pp. 535-544, https://doi.org/10.1007/3-540-56503-5_53. · Zbl 0796.94020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.