{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:40Z","timestamp":1787341420681,"version":"build-2736575974"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100001412","name":"Council of Scientific 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\/000909"],"award-info":[{"award-number":["MTR\/2017\/000909"]}],"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. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\\mathrm{AC}}^0[\\oplus]$. In particular, we show that for any fixed $d$ and integer parameter $k$, the class ${\\mathcal{{C}}}_{d,k}$ of functions that have uniform ${\\mathrm{AC}}^0[\\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform ${\\mathrm{AC}}^0[\\oplus]$ formulas of size $n^k$ but no ${\\mathrm{AC}}^0[\\oplus]$ formulas of size less than $n^{\\varepsilon_0 k}$ for some absolute constant $\\varepsilon_0 &gt; 0$. The uniform formulas are designed to solve the $\\delta$-coin problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\\delta)\/2$ or $(1-\\delta)\/2,$ where $\\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Regarding Upper bounds, for any constant $d\\geq 2$, we show that there are uniform monotone ${\\mathrm{AC}}^0$ formulas (i.e., made up of AND and OR gates only) solving the $\\delta$-coin problem that have depth $d$, size $\\exp(O(d\\cdot(1\/\\delta)^{1\/(d-1)}))$, and sample complexity (i.e., number of inputs) ${\\mathop{\\mathrm{poly}}}(1\/\\delta).$ This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195--206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59--70] in terms of size (which is optimal), while improving the sample complexity from $\\exp(O(d\\cdot(1\/\\delta)^{1\/(d-1)}))$ to ${\\mathop{\\mathrm{poly}}}(1\/\\delta)$. The improved sample complexity is crucial for proving the size-hierarchy theorem. Regarding Lower bounds, we show that the preceding upper bounds are nearly tight (in terms of size) even for the significantly stronger model of ${\\mathrm{AC}}^0[\\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any ${\\mathrm{AC}}^0[\\oplus]$ formula solving the $\\delta$-coin problem must have size $\\exp(\\Omega(d\\cdot(1\/\\delta)^{1\/(d-1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122--3154], who prove an $\\exp(\\Omega((1\/\\delta)^{1\/(d+2)}))$ lower bound for ${\\mathrm{AC}}^0[\\oplus]$ circuits, and a result of Cohen, Ganor, and Raz [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618--629], who show an $\\exp(\\Omega((1\/\\delta)^{1\/(d-1)}))$ lower bound for ${\\mathrm{AC}}^0$ circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomial-based combinatorial designs. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over ${\\mathbb{F}}_2$ solving the $\\delta$-coin problem, which may be of independent interest.<\/jats:p>","DOI":"10.1137\/19m1276467","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T18:24:10Z","timestamp":1630434250000},"page":"1461-1499","source":"Crossref","is-referenced-by-count":2,"title":["A Fixed-Depth Size-Hierarchy Theorem for $\\mathrm{AC}^0[\\oplus]$ via the Coin Problem"],"prefix":"10.1137","volume":"50","author":[{"given":"Nutan","family":"Limaye","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karteek","family":"Sreenivasaiah","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","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,8,31]]},"reference":[{"key":"atypb1","first-page":"141","author":"Aaronson S.","year":"2010","journal-title":"ACM"},{"key":"atypb2","first-page":"471","author":"Ajtai M.","year":"1984","journal-title":"ACM"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"S. Arora and B. Barak,\n                      Computational Complexity: A Modern Approach\n                      , Cambridge University Press, Cambridge, UK, 2009,http:\/\/www.cambridge.org\/catalogue\/catalogue.asp?isbn=9780521424264.","DOI":"10.1017\/CBO9780511804090"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215346"},{"key":"atypb6","unstructured":"R. Agrawal,\n                      Coin theorems and the Fourier expansion\n                      , CoRR,http:\/\/arxiv.org\/abs\/1906.03743, 2019."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1057"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"atypb9","first-page":"59","author":"Amano K.","year":"2009","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0288-y"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01978380"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"N. Alon and J. Spencer,\n                      The Probabilistic Method\n                      , John Wiley & Sons, New York, 2008,https:\/\/doi.org\/10.1002\/9780470277331.","DOI":"10.1002\/9780470277331"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/83.3.532"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.007"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"atypb17","first-page":"30","author":"Brody J.","year":"2010","journal-title":"IEEE Computer Society"},{"key":"atypb18","first-page":"618","author":"Cohen G.","year":"2014","journal-title":"APPROX-RANDOM."},{"key":"atypb19","first-page":"1","author":"Chattopadhyay E.","year":"2018","journal-title":"CCC."},{"key":"atypb20","first-page":"22","author":"Chattopadhyay E.","year":"2019","journal-title":"ITCS."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80028-5"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, New York, 2009,https:\/\/doi.org\/10.1145\/1753171.1753179.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772959"},{"key":"atypb24","unstructured":"W. Feller,\n                      An Introduction to Probability Theory and Its Applications\n                      , 2nd ed., John Wiley & Sons, New York, 1971."},{"key":"atypb25","first-page":"316","author":"Fortnow L.","year":"2004","journal-title":"IEEE Computer Society"},{"key":"atypb26","unstructured":"A. Golovnev, R. Ilango, R. Impagliazzo, V. Kabanets, A. Kolokolova, and A. Tal,\n                      $\\mathrm{AC}^0[p]$ Lower bounds against MCSP via the coin problem\n                      , in\n                      \n                        ICALP\n                        2019\n                        :\n                        46\n                        th International Colloquium on Automata, Languages, and Programming\n                      \n                      ,\n                      LIPI\n                      cs Leibniz Inf. Proc. Inform. 132, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2019,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.66."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001599"},{"key":"atypb28","first-page":"143","volume":"5","author":"Hastad J.","year":"1989","journal-title":"Adv. Comput. Res."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10095"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1145\/3095799"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1965-0170805-7"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010209"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90020-9"},{"key":"atypb34","first-page":"36","author":"Kopparty S.","year":"2012","journal-title":"FSTTCS."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"atypb36","first-page":"442","author":"Limaye N.","year":"2019","journal-title":"ACM"},{"key":"atypb37","unstructured":"N. Limaye, S. Srinivasan, and U. Tripathi,\n                      More on \\(\\mathrmAC^0[\u00f8plus]\\) and variants of the majority function\n                      , in 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Bombay, LIPIcs Leibniz Int. Proc. Inform. 150, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2019,https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.22."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/3201787"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/BF01375474"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"R. O'Donnell,\n                      Analysis of Boolean Functions\n                      , Cambridge University Press, Cambridge, UK, 2014,https:\/\/doi.org\/10.1017\/CBO9781139814782.","DOI":"10.1017\/CBO9781139814782"},{"key":"atypb42","unstructured":"I. Carboni Oliveira, R. Santhanam, and S. Srinivasan,\n                      Parity helps to compute majority\n                      , Electronic Colloquium on Computational Complexity, 26:73, 2019,https:\/\/eccc.weizmann.ac.il\/report\/2019\/073."},{"key":"atypb43","first-page":"195","author":"O'Donnell R.","year":"2007","journal-title":"New York"},{"key":"atypb44","unstructured":"A. Potukuchi,\n                      On the $\\mathrm{AC}^0[\\oplus]$ Complexity of Andreev's problem\n                      , in FSTTCS 2019: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Bombay, LIPIcs Leibniz Int. Proc. Inform. 150, Schloss Dagstuhl, Leibniz-Zentrum f\u00fcr Informatik, 2019,https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.25."},{"key":"atypb45","first-page":"167","author":"Razborov A. A.","year":"1989","journal-title":"ACM"},{"key":"atypb46","first-page":"721","author":"Rossman B.","year":"2008","journal-title":"Victoria, BC"},{"key":"atypb47","first-page":"721","author":"Rossman B.","year":"2008","journal-title":"ACM"},{"key":"atypb48","first-page":"50","author":"Rossman B.","year":"2017","journal-title":"ICALP."},{"key":"atypb49","first-page":"179","author":"Stearns R. E.","year":"1965","journal-title":"MI"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"atypb51","first-page":"77","author":"Smolensky R.","year":"1987","journal-title":"ACM"},{"key":"atypb52","first-page":"130","author":"Smolensky R.","year":"1993","journal-title":"IEEE Computer Society"},{"key":"atypb53","first-page":"248","author":"Steinberger J. P.","year":"2013","journal-title":"IEEE Conference on Computational Complexity"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/080735096"},{"key":"atypb55","unstructured":"M. Szegedy,\n                      Algebraic Methods in Lower Bounds for Computational Models with Limited Communication\n                      , Ph.D. thesis, University of Chicago, 1989."},{"key":"atypb56","unstructured":"A. Tal,\n                      private communication\n                      , 2018."},{"key":"atypb57","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-013-0076-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1276467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:35Z","timestamp":1787339915000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1276467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1276467"],"URL":"https:\/\/doi.org\/10.1137\/19m1276467","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}