{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:45:27Z","timestamp":1787323527494,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001412","name":"Council\u00a0of\u00a0Scientific and Industrial Research, India","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001412","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001843","name":"Science and Engineering Research Board","doi-asserted-by":"publisher","award":["MTR\/2017\/000958"],"award-info":[{"award-number":["MTR\/2017\/000958"]}],"id":[{"id":"10.13039\/501100001843","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005276","name":"National Board for Higher Mathematics","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100005276","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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 Razborov [ Mat. Zametki, 41 (1987), pp. 598--607], 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).<\/jats:p>","DOI":"10.1137\/19m1294162","type":"journal-article","created":{"date-parts":[[2021,9,13]],"date-time":"2021-09-13T12:37:38Z","timestamp":1631536658000},"page":"2070-2092","source":"Crossref","is-referenced-by-count":0,"title":["On the Probabilistic Degrees of Symmetric Boolean Functions"],"prefix":"10.1137","volume":"35","author":[{"given":"Srikanth","family":"Srinivasan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Utkarsh","family":"Tripathi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Venkitesh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,13]]},"reference":[{"key":"atypb1","first-page":"136","author":"Alman J.","year":"2015","journal-title":"IEEE"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"R. Beigel,\n                      The polynomial method in circuit complexity\n                      , in Proceedings of the 8th Annual Structure in Complexity Theory Conference, pp. 82-95,https:\/\/doi.org\/10.1109\/SCT.1993.336538, 1993.","DOI":"10.1109\/SCT.1993.336538"},{"key":"atypb3","unstructured":"S. Bhandari, P. Harsha, T. Molli, and S. Srinivasan,\n                      On the probabilistic degree of OR over the reals\n                      , 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."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"atypb5","first-page":"286","author":"Beigel R.","year":"1991","journal-title":"Chicago"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90163-3"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, 2009.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90045-3"},{"key":"atypb9","unstructured":"P. Harsha and S. Srinivasan,\n                      On polynomial approximations to $\\mathrm{AC}^0$\n                      , 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."},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"D. L. Johnson, D. L. Johnson, and S. S. Johnson,\n                      Topics in the theory of group presentations\n                      , London Math. Soc. Lecture Note Ser. 42, Cambridge University Press, Cambridge, 1980,https:\/\/doi.org\/10.1017\/CBO9780511629303.","DOI":"10.1017\/CBO9780511629303"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128670"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00145-6"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"E. Lucas,\n                      Th\u00e9orie des fonctions num\u00e9riques simplement p\u00e9riodiques\n                      , Amer. J. Math., pp. 289-321,https:\/\/doi.org\/10.2307\/2369308, 1878.","DOI":"10.2307\/2369373"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a011"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"R. O'Donnell,\n                      Analysis of Boolean Functions\n                      , Cambridge University Press, Cambridge, 2014,https:\/\/doi.org\/10.1017\/CBO9781139814782.","DOI":"10.1017\/CBO9781139814782"},{"key":"atypb16","first-page":"468","author":"Paturi R.","year":"1992","journal-title":"New York"},{"key":"atypb17","first-page":"598","volume":"41","author":"Razborov A. A.","year":"1987","journal-title":"Mat. Zametki"},{"key":"atypb18","first-page":"77","author":"Smolensky R.","year":"1987","journal-title":"New York"},{"key":"atypb19","first-page":"77","author":"Smolensky R.","year":"1987","journal-title":"New York"},{"key":"atypb20","first-page":"130","author":"Smolensky R.","year":"1993","journal-title":"IEEE"},{"key":"atypb21","first-page":"130","author":"Smolensky R.","year":"1993","journal-title":"Proceedings of FOCS"},{"key":"atypb22","first-page":"1","author":"Srinivasan S.","year":"2019","journal-title":"LIPIcs. Int. Proc. Inform. ISO"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90214-E"},{"key":"atypb24","unstructured":"R. R. Williams,\n                      The polynomial method in circuit complexity applied to algorithm design (invited talk)\n                      , 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."},{"key":"atypb25","first-page":"535","author":"Zhang Z. L.","year":"1993","journal-title":"New York"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1294162","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:17Z","timestamp":1787321237000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1294162"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1294162"],"URL":"https:\/\/doi.org\/10.1137\/19m1294162","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}