{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T15:09:30Z","timestamp":1790089770746,"version":"4.0.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1994,6,1]],"date-time":"1994-06-01T00:00:00Z","timestamp":770428800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[1994,6]]},"DOI":"10.1007\/bf01215346","type":"journal-article","created":{"date-parts":[[2005,2,25]],"date-time":"2005-02-25T15:10:17Z","timestamp":1109344217000},"page":"135-148","source":"Crossref","is-referenced-by-count":92,"title":["The expressive power of voting polynomials"],"prefix":"10.1007","volume":"14","author":[{"given":"J.","family":"Aspnes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R.","family":"Beigel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Furst","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Rudich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"CR1","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/0022-0000(91)90040-C","volume":"42","author":"R. Beigel","year":"1991","unstructured":"R. Beigel: Relativized counting classes: Relations among thresholds, parity, and mods.Journal of Computer and System Sciences 42(1) February 1991, 76?96.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"R. Beigel, N. Reingold, andD. Spielman: The perceptron strikes back.Proceedings of the 6th Annual Conference on Structure in Complexity Theory (1991), 286?291.","DOI":"10.1109\/SCT.1991.160270"},{"issue":"1","key":"CR3","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. H. Bennett","year":"1981","unstructured":"C. H. Bennett, andJ. Gill: Relative to a random oracleA, P A ?NP A ?co-NP A with probability 1.SIAM Journal on Computing 10(1) February 1981, 96?113.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"CR4","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/0403015","volume":"3","author":"J. Bruck","year":"1990","unstructured":"J. Bruck: Harmonic analysis of polynomial threshold functions.SIAM Journal on Discrete Mathematics 3(2) May 1990, 168?177.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"J. Bruck, andR. Smolensky: Polynomial threshold functions, AC0 functions and spectral norms. InProceedings of the 31st Annual Symposium on Foundations of Computer Science (1990), 632?641.","DOI":"10.1109\/FSCS.1990.89585"},{"key":"CR6","unstructured":"V. Chv\ufffdtal:Linear Programming. W. H. Freeman and Company, (1983)."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. Saxe, andM. Sipser: Parity, circuits and the polynomial time hierarchy.Mathematical Systems Theory 17 (1984), 13?27.","journal-title":"Mathematical Systems Theory"},{"key":"CR8","unstructured":"C. Gotsman: On boolean functions, polynomials, and algebraic threshold functions. Unpublished manuscript."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour andN. Nisan: Constant depth circuits, fourier transform, and learnability. InProceedings of the 30th Annual Symposium on Foundations of Computer Science (1989), 574?579.","DOI":"10.1109\/SFCS.1989.63537"},{"key":"CR10","volume-title":"Perceptrons","author":"M. L. Minsky","year":"1988","unstructured":"M. L. Minsky, andS. Papert:Perceptrons. MIT Press, Cambridge, MA, (1988), Expanded Edition. The first edition appeared in 1968.","edition":"Expanded Editio"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"R. Paturi, andM. E. Saks: On threshold circuits for parity. InProceedings of the 31st Annual Symposium on Foundations of Computer Science (1990), 397?404.","DOI":"10.1016\/B978-1-55860-146-8.50036-9"},{"issue":"4","key":"CR12","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. A. Razborov","year":"1987","unstructured":"A. A. Razborov: Lower bounds for the size of circuits of bounded depth with basis {?,?}.Math. Notes of the Academy of Sciences of the USSR 41(4) September 1987, 333?338.","journal-title":"Math. Notes of the Academy of Sciences of the USSR"},{"key":"CR13","unstructured":"A. Schrijver:Theory of Linear and Integer Programming. John Wiley and Sons., (1986)."},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"R. Smolensky: Algebraic methods in the theory of lower bounds for boolean circuit complexity. InProceedings of the 19th Annual ACM Symposium on Theory of Computing (1987), 77?82.","DOI":"10.1145\/28395.28404"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/BF01458147","volume":"76","author":"E. Stiemke","year":"1915","unstructured":"E. Stiemke: \ufffdber positive L\ufffdsungen homogener linearer Gleichungen.Mathematische Annalen 76 (1915), 340?342.","journal-title":"Mathematische Annalen"},{"key":"CR16","unstructured":"J. Tarui: Randomized polynomials, threshold circuits, and the polynomial hierarchy. Manuscript, August 1990."},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"L. G. Valiant, andV. V. Vazirani: NP is as easy as detecting unique solutions. InProceedings of the 17th Annual ACM Symposium on Theory of Computing (1985).","DOI":"10.1145\/22145.22196"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"A. Yao: Separating the polynomial-time hierarchy by oracles. InProceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (1985), 1?10.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01215346.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01215346\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01215346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T22:57:29Z","timestamp":1734994649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01215346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["BF01215346"],"URL":"https:\/\/doi.org\/10.1007\/bf01215346","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}