{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:53Z","timestamp":1725663773996},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-57811-0_7","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T08:24:47Z","timestamp":1330244687000},"page":"63-72","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Measures of Boolean function complexity based on Harmonic Analysis"],"prefix":"10.1007","author":[{"given":"A.","family":"Bernasconi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Codenotti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"7_CR1","volume-title":"Technical Report, TR-93-030","author":"A. Bernasconi","year":"1993","unstructured":"A. Bernasconi, B. Codenotti. Sensitivity of Boolean Functions, Abstract Harmonic Analysis, and Circuit Complexity. Technical Report, TR-93-030 International Computer Science Institute, Berkeley, CA. (1993)."},{"issue":"2","key":"7_CR2","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1109\/12.45216","volume":"39","author":"Y. Brandman","year":"1990","unstructured":"Y. Brandman, A. Orlitsky, J. Hennessy. A Spectral Lower Bound Technique for the Size of Decision Trees and Two-Level AND\/OR Circuits. IEEE Trans. on Computers Vol. 39 (2) (1990), pp.282\u2013287.","journal-title":"IEEE Trans. on Computers"},{"key":"7_CR3","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 Vol. 3 (1990), pp.168\u2013177.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"7_CR4","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/0221003","volume":"21","author":"J. Bruck","year":"1992","unstructured":"J. Bruck, R. Smolensky. Polynomial Threshold Functions, AC 0 Functions, and Spectral Norms. SIAM Journal on Computing Vol. 21(1) (1992), pp.33\u201342.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"7_CR5","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S. Cook","year":"1986","unstructured":"S. Cook, C. Dwork, R. Reischuk. Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous writes. SIAM Journal on Computing Vol. 15(1) (1986), pp.87\u201397.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR6","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(85)90045-3","volume":"36","author":"R. Fagin","year":"1985","unstructured":"R. Fagin, M.M. Klawe, N.J. Pippenger, L. Stockmeyer. Bounded-Depth, Polynomial Size Circuits for Symmetric Functions. Theoretical Computer Science Vol. 36 (1985), pp.239\u2013250.","journal-title":"Theoretical Computer Science"},{"issue":"33","key":"7_CR7","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1049\/el:19820387","volume":"18","author":"S. L. Hurst","year":"1982","unstructured":"S.L. Hurst, D.M. Miller, J.C Muzio. Spectral Method of Boolean Function Complexity. Electronics Letters Vol. 18 (33) (1982), pp.572\u2013574.","journal-title":"Electronics Letters"},{"key":"7_CR8","unstructured":"J. Kahn, G. Kalai, N. Linial. The Influence of Variables on Boolean Functions. Proc. 29th FOCS (1988),pp.68\u201380."},{"key":"7_CR9","volume-title":"Finite. Orthogonal Series in the Design of Digital Devices","author":"M. G. Karpovsky","year":"1976","unstructured":"M.G. Karpovsky. Finite. Orthogonal Series in the Design of Digital Devices. John Wiley and Son, New York (1976)."},{"key":"7_CR10","unstructured":"E. Kushilevitz, Y. Mansour. Learning Decision Trees using the. Fourier Spectrum Proc. 23rd STOC (1991), pp. 455\u2013464."},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"R. J. Lechner. Harmonic Analysis of Switching Functions. In Recent Development in Switching Theory, Academic Press (1971), pp.122\u2013229.","DOI":"10.1016\/B978-0-12-509850-2.50010-5"},{"key":"7_CR12","unstructured":"N. Linial, Y. Mansour, N. Nisan. Constant Depth Circuits, Fourier Transform, and learnability. Proc. 30th FOCS (1989), pp.574\u2013579."},{"key":"7_CR13","volume-title":"An Introduction to Abstract Harmonic. Analysis","author":"L. M. Loomis","year":"1953","unstructured":"L.M. Loomis. An Introduction to Abstract Harmonic. Analysis. Van Nostrand0, Princeton, New Jersey (1953)."},{"key":"7_CR14","unstructured":"N. Nisan. CREW PRAMs and Decision Trees. Proc. 21st STOC (1989), pp. 327\u2013335."},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"A.A. Razborov. On Submodular Complexity Measures. In \u201cBoolean Function Complexity\u201d, Edited by M.S. Paterson, Cambridge University Press (1992), pp.129\u2013139.","DOI":"10.1017\/CBO9780511526633.007"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"H.U. Simon A Tight \u03a9(log log n) Round on the Time for Parallel RAM's to compute non degenerate. Boolean functions. FCT'83, Lecture notes in Comp. Sci. 158, 1983.","DOI":"10.1007\/3-540-12689-9_124"},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"I. Wegener. The. Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science. John Wiley and Son (1987).","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,3]],"date-time":"2020-07-03T01:17:44Z","timestamp":1593739064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}