{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:40:03Z","timestamp":1706650803939},"reference-count":11,"publisher":"Duke University Press","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[1997,1,1]]},"DOI":"10.1305\/ndjfl\/1039700695","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T20:56:26Z","timestamp":1046206586000},"source":"Crossref","is-referenced-by-count":0,"title":["Algebraic Methods and Bounded Formulas"],"prefix":"10.1215","volume":"38","author":[{"given":"Domenico","family":"Zambella","sequence":"first","affiliation":[]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., \u201c$\\Sigma^1_1$ formulas on finite structures,\" <i>Annals of Pure and Applied Logic<\/i>, vol. 24 (1983), pp. 1\u201348. MR 85b:03048","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"2","unstructured":"Feller, W., <i>An Introduction to Probability Theory and Its Applications<\/i>, vol. 1, 2d edition, J. Wiley and Sons, New York, 1957. Zbl 0077.12201 MR 19,466a"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Furst, M., J. B. Saxe, and M. Sipser, \u201cParity circuits and the polynomial-time hierarchy,\" <i>Mathematical Systems Theory<\/i>, vol. 17 (1984), pp. 13\u201327. Zbl 0534.94008 MR 86e:68048","DOI":"10.1007\/BF01744431"},{"key":"4","unstructured":"H\u00e5 stad, J., \u201cAlmost optimal lower bounds for small depth circuits,\" pp. 143\u201370 in <i>Randomness and Computation<\/i>, vol. 5, <i>Advances in Computing Research<\/i>, edited by S. Micali, JAI Press, Greenwich, 1989."},{"key":"5","doi-asserted-by":"crossref","unstructured":"Razborov, A. A., \u201cLower bounds for the size of circuits of bounded depth with basis $\\{\\and,\\oplus\\}$,\" <i>Mathematical Notes of the Academy of Science of the USSR<\/i>, vol. 41 (1987), pp. 333\u201338.","DOI":"10.1007\/BF01137685"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Razborov, A. A., \u201cBounded arithmetic and lower bounds in Boolean complexity,\" pp. 344\u201386 in <i>Feasible Mathematics 2<\/i>, Birkh\u00e4user, Boston, 1995. Zbl 0838.03044 MR 96d:03057","DOI":"10.1007\/978-1-4612-2566-9_12"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Smolensky, R., \u201cAlgebraic methods in the theory of lower bounds for Boolean circuit complexity,\" pp. 77\u201382 in <i>Proceedings of the 19th Annual ACM Symposium on the Theory of Computing<\/i>, 1987.","DOI":"10.1145\/28395.28404"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Tauri, J., \u201cProbabilistic polynomials, $AC_0$ functions, and the polynomial-time hierarchy,\" <i>Theoretical Computer Science<\/i>, vol. 113 (1993), pp. 167\u201383.","DOI":"10.1016\/0304-3975(93)90214-E"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Toda S., and M. Ogiwara, \u201cCounting classes are at least as hard as the polynomial-time hierarchy,\" <i>SIAM Journal on Computing<\/i>, vol. 21 (1992), pp. 316\u201328. Zbl 0755.68055 MR 93h:68052","DOI":"10.1137\/0221023"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Valiant, L. G., and V. V. Vazirani, \u201cNP is as easy as detecting unique solutions,\" <i>Theoretical Computer Science<\/i>, vol. 47 (1986), pp. 85\u201393. Zbl 0621.68030 MR 88i:68021","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Yao, A. C., \u201cSeparating the polynomial-time hierarchy by oracles,\" pp. 1\u201310 in <i>Proceedings of the 26th Annual Symposium on Foundations of Computer Science<\/i>, IEEE Computer Society Press, Los Alamitos, 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1039700695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:12:59Z","timestamp":1706649179000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-38\/issue-1\/Algebraic-Methods-and-Bounded-Formulas\/10.1305\/ndjfl\/1039700695.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1,1]]},"references-count":11,"journal-issue":{"issue":"1","published-online":{"date-parts":[[1997,1,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1039700695","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[1997,1,1]]}}}