{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:59Z","timestamp":1725662939192},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540164869"},{"type":"electronic","value":"9783540398257"}],"license":[{"start":{"date-parts":[[1986,1,1]],"date-time":"1986-01-01T00:00:00Z","timestamp":504921600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_105","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:45:45Z","timestamp":1330195545000},"page":"272-290","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parallel computation with threshold functions"],"prefix":"10.1007","author":[{"given":"Ian","family":"Parberry","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0364-0213(85)80012-4","volume":"9","author":"D. H. Ackley","year":"1985","unstructured":"D. H. Ackley, G. E. Hinton, and T. J. Sejnowski, \u201cA learning algorithm for Boltzmann machines,\u201d Cognitive Science, vol. 9, pp. 147\u2013169, 1985.","journal-title":"Cognitive Science"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, \u201c\u03a3\n                  1\n                  1\n                -formulae on finite structures,\u201d Annals of Pure and Applied Logic, vol. 24, pp. 1\u201348, 1983.","journal-title":"Annals of Pure and Applied Logic"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and M. Ben-Or, \u201cA note on probabilistic constant depth computations,\u201d Proc. 16th Ann. ACM Symp. on Theory of Computing, pp. 471\u2013474, Washington, D.C., Apr.-May 1984.","DOI":"10.1145\/800057.808715"},{"key":"21_CR4","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C. G. Bennet","year":"1981","unstructured":"C. G. Bennet and J. Gill, \u201cRelative to a random oracle A, PA \u2260 NPA \u2260 Co-NPA with probability 1,\u201d SIAM J. Comp., vol. 10, pp. 96\u2013113, 1981.","journal-title":"SIAM J. Comp."},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0020-0190(83)90041-8","volume":"17","author":"N. Blum","year":"1983","unstructured":"N. Blum, \u201cA note on the \u2018parallel computation thesis',\u201d Inf. Proc. Lett., vol. 17, pp. 203\u2013205, 1983.","journal-title":"Inf. Proc. Lett."},{"issue":"1","key":"21_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, \u201cAlternation,\u201d J. ACM, vol. 28, no. 1, pp. 114\u2013133, Jan. 1981.","journal-title":"J. ACM"},{"key":"21_CR7","unstructured":"S. A. Cook, \u201cTowards a complexity theory of synchronous parallel computation,\u201d L'Enseignement Mathematique, vol. 30, 1980."},{"key":"21_CR8","unstructured":"P. W. Dymond, \u201cSimultaneous resource bounds and parallel computations,\u201d Ph. D. Thesis, issued as Technical Report TR145\/80, Dept. of Computer Science, Univ. of Toronto, Aug. 1980."},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"P. W. Dymond and S. A. Cook, \u201cHardware complexity and parallel computation,\u201d Proc. 21st Ann. IEEE Symp. on Foundations of Computer Science, Oct. 1980.","DOI":"10.1109\/SFCS.1980.22"},{"key":"21_CR10","doi-asserted-by":"crossref","first-page":"1901","DOI":"10.1109\/PROC.1966.5273","volume":"54","author":"M. Flynn","year":"1966","unstructured":"M. Flynn, \u201cVery high-speed computing systems,\u201d Proc. IEEE, vol. 54, pp. 1901\u20131909, Dec. 1966.","journal-title":"Proc. IEEE"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"S. Fortune and J. Wyllie, \u201cParallelism in random access machines,\u201d Proc. 10th Ann. ACM Symp. on Theory of Computing, pp. 114\u2013118, 1978.","DOI":"10.1145\/800133.804339"},{"issue":"1","key":"21_CR12","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. B. Saxe, and M. Sipser, \u201cParity, circuits and the polynomial time hierarchy,\u201d Math. Syst. Theory, vol. 17, no. 1, pp. 13\u201327, 1984.","journal-title":"Math. Syst. Theory"},{"key":"21_CR13","unstructured":"L. M. Goldschlager, \u201cSynchronous parallel computation,\u201d Ph. D. Thesis, issued as TR-114, Dept. of Computer Science, Univ. of Toronto, Dec. 1977."},{"issue":"4","key":"21_CR14","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1145\/322344.322353","volume":"29","author":"L. M. Goldschlager","year":"1982","unstructured":"L. M. Goldschlager, \u201cA universal interconnection pattern for parallel computers,\u201d J. ACM, vol. 29, no. 4, pp. 1073\u20131086, Oct. 1982.","journal-title":"J. ACM"},{"issue":"1","key":"21_CR15","first-page":"1","volume":"41","author":"L. M. Goldschlager","year":"1986","unstructured":"L. M. Goldschlager and I. Parberry, \u201cOn the construction of parallel computers from various bases of boolean functions,\u201d Theor. Comput. Sci., vol. 41, no. 1, pp. 1\u201316, 1986.","journal-title":"Theor. Comput. Sci."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"J. Hartmanis and J. Simon, \u201cOn the power of multiplication in random access machines,\u201d Proc. 15th Ann. IEEE Symp. on Switching and Automata Theory, pp. 13\u201323, 1974.","DOI":"10.1109\/SWAT.1974.20"},{"key":"21_CR17","unstructured":"G. E. Hinton, T. J. Sejnowski, and D. H. Ackley, \u201cBoltzmann machines: Constraint satisfaction networks that learn,\u201d CMU-CS-84-119, Dept. of Computer Science, Carnegie-Mellon Univ., May 1984."},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1073\/pnas.79.8.2554","volume":"79","author":"J. J. Hopfield","year":"1982","unstructured":"J. J. Hopfield, \u201cNeural networks and physical systems with emergent collective computational abilities,\u201d Proc. National Academy of Sciences, vol. 79, pp. 2554\u20132558, Apr. 1982.","journal-title":"Proc. National Academy of Sciences"},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"M. Luby, \u201cA simple parallel algorithm for the maximal independent set problem,\u201d Proc. 17th Ann. ACM Symp. on Theory of Computing, pp. 1\u201310, Providence, Rhode Island, May 1985.","DOI":"10.1145\/22145.22146"},{"key":"21_CR20","unstructured":"I. Parberry, \u201cParallel speedup of sequential machines: a defense of the parallel computation thesis,\u201d Technical Report CS-84-17, Dept. of Computer Science, Penn. State Univ., Oct. 1984."},{"key":"21_CR21","unstructured":"I. Parberry, \u201cA complexity theory of parallel computation,\u201d Ph. D. Thesis, Dept. of Computer Science, Univ. of Warwick, May 1984."},{"key":"21_CR22","unstructured":"I. Parberry, \u201cOn the number of processors required to simulate Turing machines in constant parallel time,\u201d Technical Report CS-85-17, Dept. of Computer Science, Penn. State Univ., Aug. 1985."},{"key":"21_CR23","first-page":"429","volume-title":"Proc. 24th Ann. IEEE Symp. on Foundations of Computer Science","author":"W. J. Paul","year":"1983","unstructured":"W. J. Paul, N. Pippenger, E. Szemer\u00e9di, and W. T. Trotter, \u201cOn determinism versus non-determinism and related problems,\u201d Proc. 24th Ann. IEEE Symp. on Foundations of Computer Science, pp. 429\u2013438, Tucson, Arizona, Nov. 1983."},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"N. Pippenger, \u201cOn simultaneous resource bounds,\u201d Proc. 20th Ann. IEEE Symp. on Foundations of Computer Science, Oct. 1979.","DOI":"10.1109\/SFCS.1979.29"},{"key":"21_CR25","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/S0022-0000(76)80037-2","volume":"12","author":"V. Pratt","year":"1976","unstructured":"V. Pratt and L. J. Stockmeyer, \u201cA characterization of the power of vector machines,\u201d J. Comput. Sys. Sci., vol. 12, pp. 198\u2013221, 1976.","journal-title":"J. Comput. Sys. Sci."},{"issue":"3","key":"21_CR26","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo, \u201cOn uniform circuit complexity,\u201d J. Comput. Sys. Sci., vol. 22, no. 3, pp. 365\u2013383, June 1981.","journal-title":"J. Comput. Sys. Sci."},{"issue":"4","key":"21_CR27","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1145\/321724.321731","volume":"19","author":"J. E. Savage","year":"1972","unstructured":"J. E. Savage, \u201cComputational work and time on finite machines,\u201d J. ACM, vol. 19, no. 4, pp. 660\u2013674, 1972.","journal-title":"J. ACM"},{"issue":"4","key":"21_CR28","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1145\/357114.357116","volume":"2","author":"J. T. Schwartz","year":"1980","unstructured":"J. T. Schwartz, \u201cUltracomputers,\u201d ACM TOPLAS, vol. 2, no. 4, pp. 484\u2013521, Oct. 1980.","journal-title":"ACM TOPLAS"},{"key":"21_CR29","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin, \u201cFinding the maximum, sorting and merging in a parallel computation model,\u201d J. Algorithms, vol. 2, pp. 88\u2013102, 1981.","journal-title":"J. Algorithms"},{"key":"21_CR30","doi-asserted-by":"crossref","unstructured":"M. Sipser, \u201cBorel sets and circuit complexity,\u201d Proc. 15th Ann. ACM Symp. on Theory of Computing, pp. 61\u201369, Boston, Mass., Apr. 1983.","DOI":"10.1145\/800061.808733"},{"issue":"2","key":"21_CR31","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1137\/0213027","volume":"13","author":"L. Stockmeyer","year":"1984","unstructured":"L. Stockmeyer and U. Vishkin, \u201cSimulation of parallel random access machines by circuits,\u201d SIAM J. Comp., vol. 13, no. 2, pp. 409\u2013422, May 1984.","journal-title":"SIAM J. Comp."},{"key":"21_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer, \u201cThe polynomial time hierarchy,\u201d Theor. Comput. Sci., vol. 3, pp. 1\u201322, 1977.","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR33","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant, \u201cThe complexity of enumeration and reliability problems,\u201d SIAM J. Comp., vol. 8, no. 3, pp. 410\u2013421, 1979.","journal-title":"SIAM J. Comp."},{"key":"21_CR34","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant, \u201cThe complexity of computing the permanent,\u201d Theor. Comput. Sci., vol. 8, pp. 189\u2013201, 1979.","journal-title":"Theor. Comput. Sci."},{"key":"21_CR35","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"C. Wrathall, \u201cComplete sets and the polynomial-time hierarchy,\u201d Theor. Comput. Sci., vol. 3, pp. 23\u201333, 1976.","journal-title":"Theor. Comput. Sci."},{"key":"21_CR36","doi-asserted-by":"crossref","unstructured":"A. C. Yao, \u201cSeparating the polynomial-time hierarchy by oracles,\u201d Proc. 26th Ann. IEEE Symp. on Foundations of Computer Science, Portland, Oregon, Oct. 1985.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T02:22:31Z","timestamp":1578536551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_105"}},"subtitle":["Preliminary version"],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_105","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]},"assertion":[{"value":"2 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}