{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:28Z","timestamp":1759063648766},"reference-count":22,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":7502,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1993,1]]},"DOI":"10.1016\/0304-3975(93)90254-q","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T03:31:50Z","timestamp":1027654310000},"page":"63-76","source":"Crossref","is-referenced-by-count":13,"title":["On read-once threshold formulae and their randomized decision tree complexity"],"prefix":"10.1016","volume":"107","author":[{"given":"Rafi","family":"Heiman","sequence":"first","affiliation":[]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(93)90254-Q_BIB1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","article-title":"\u03a311-formulae on finite structures","volume":"24","author":"Ajtai","year":"1983","journal-title":"Ann. Pure and Appl. Logic"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB2","series-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science","first-page":"580","article-title":"A note on the power of threshold circuits","author":"Allender","year":"1989"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB3","unstructured":"R.B. Boppana, private communication."},{"key":"10.1016\/0304-3975(93)90254-Q_BIB4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","article-title":"Parity, circuits and the polynomial time hierarchy","volume":"17","author":"Furst","year":"1984","journal-title":"Math. Systems Theory"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB5","series-title":"Tech. Report 88-19","article-title":"An \u03a9(N43) lower bound on the randomized complexity of graph properties","author":"Hajnal","year":"1988"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB6","series-title":"Proc. 28th IEEE Symp. on Foundations of Computer Science","first-page":"99","article-title":"Threshold circuits of bounded depth","author":"Hajnal","year":"1987"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB7","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1073\/pnas.79.8.2554","article-title":"Neural network and physical systems with emergent collective computational abilities","volume":"79","author":"Hopfield","year":"1982","journal-title":"Nat. Acad. Sci. USA"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB8","series-title":"Proc. 20th ACM Symp. on Theory of Computing","first-page":"468","article-title":"Lower bounds on the complexity of graph properties","author":"King","year":"1988"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB9","series-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science","first-page":"574","article-title":"Constant depth circuits, Fourier transform, and learnability","author":"Linial","year":"1989"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB10","series-title":"Proc. 21st ACM Symp. on Theory of Computing","first-page":"327","article-title":"CREW PRAMs and decision trees","author":"Nisan","year":"1989"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB11","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/BF01137685","article-title":"Lower bounds on the size of bounded depth networks over a complete basis with logical addition","volume":"41","author":"Razborov","year":"1987","journal-title":"Math. Notes"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB12","series-title":"Proc. 2nd Structure in Complexity Theory Conf.","first-page":"118","article-title":"On threshold circuits and polynomial computations","author":"Reif","year":"1987"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB13","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/0304-3975(76)90053-0","article-title":"On recognizing graph properties from adjacency matrices","volume":"3","author":"Rivest","year":"1978","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(93)90254-Q_BIB14","series-title":"Parallel Distributed Processing: Exploration in the Microstructure of Cognition, Vol. 1","author":"Rumelhardt","year":"1986"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB15","series-title":"Proc. 27th IEEE Symp. on Foundations of Computer Science","first-page":"29","article-title":"Probabilistic Boolean decision trees and the complexity of evaluating game trees","author":"Saks","year":"1986"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB16","series-title":"Proc. 6th Structure in Complexity Theory Conf.","first-page":"180","article-title":"On the Monte Carlo Boolean decision tree complexity of read-once formulae","author":"Santha","year":"1991"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB17","series-title":"Proc. 19th ACM Symp. on Theory of Computing","first-page":"77","article-title":"Algebraic methods in the theory of lower bounds for Boolean circuit complexity","author":"Smolensky","year":"1987"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB18","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","article-title":"Lower bounds for probabilistic linear decision trees","volume":"38","author":"Snir","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(93)90254-Q_BIB19","unstructured":"C. Sturtivant, G. Frandsen and J. Boyar, Is finite field arithmetic a restricted model of computation?, manuscript, 1989."},{"key":"10.1016\/0304-3975(93)90254-Q_BIB20","series-title":"Proc. 30th IEEE Symp. on Foundations of Computer Science","first-page":"514","article-title":"On the computational power of PP and \u2295P","author":"Toda","year":"1989"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB21","series-title":"Proc. 28th IEEE Symp. on Foundations of Computer Science","first-page":"393","article-title":"Lower bounds to randomized algorithms for graph properties","author":"Yao","year":"1987"},{"key":"10.1016\/0304-3975(93)90254-Q_BIB22","series-title":"Proc. 21st ACM Symp. on Theory of Computing","first-page":"186","article-title":"Circuits and Local Computation","author":"Yao","year":"1989"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759390254Q?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759390254Q?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T11:28:54Z","timestamp":1555154934000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759390254Q"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["030439759390254Q"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(93)90254-q","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}