{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T01:35:06Z","timestamp":1784424906939,"version":"3.55.0"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T00:00:00Z","timestamp":1499212800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00037-017-0156-0","type":"journal-article","created":{"date-parts":[[2017,7,5]],"date-time":"2017-07-05T07:40:33Z","timestamp":1499240433000},"page":"209-223","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Average Sensitivity of Bounded-Depth Formulas"],"prefix":"10.1007","volume":"27","author":[{"given":"Benjamin","family":"Rossman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,7,5]]},"reference":[{"key":"156_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"Ajtai Mikl\u00f3s","year":"1983","unstructured":"Mikl\u00f3s Ajtai (1983) $${\\Sigma^1_1}$$ \u03a3 1 1 formulae on finite structures. Annals of Pure and Applied Logic 24: 1\u201348","journal-title":"Annals of Pure and Applied Logic"},{"key":"156_CR2","doi-asserted-by":"crossref","unstructured":"Shelby Kimmel Andrew M. Childs & Robin Kothari (2012). The quantum query complexity of read-many formulas. In European Symposium on Algorithms, 337\u2013348.","DOI":"10.1007\/978-3-642-33090-2_30"},{"issue":"5","key":"156_CR3","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"Ravi B. Boppana","year":"1997","unstructured":"Ravi B. Boppana (1997) The average sensitivity of bounded-depth circuits. Information Processing Letters 63(5): 257\u2013261","journal-title":"Information Processing Letters"},{"key":"156_CR4","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad (1986). Almost optimal lower bounds for small depth circuits. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 6\u201320. ACM.","DOI":"10.1145\/12130.12132"},{"key":"156_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF01405045","volume":"9","author":"V.M. Khrapchenko","year":"1971","unstructured":"Khrapchenko V.M. (1971) Complexity of the realization of a linear function in the case of $${\\Pi}$$ \u03a0 -circuits. Math. Notes Acad. Sciences 9: 21\u201323","journal-title":"Math. Notes Acad. Sciences"},{"key":"156_CR6","doi-asserted-by":"crossref","unstructured":"James B. Saxe Merrick L. Furst & Michael Sipser (1984). Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory 17, 13\u201327.","DOI":"10.1007\/BF01744431"},{"key":"156_CR7","unstructured":"Benjamin Rossman (2014). Formulas vs. circuits for small distance connectivity. In 46th Annual ACM Symposium on Theory of Computing, 203\u2013212."},{"key":"156_CR8","unstructured":"P.M. Spira (1971). On time-hardware complexity tradeoffs for Boolean functions. In 4th Hawaii Symposium on System Sciences, 525\u2013527."},{"key":"156_CR9","unstructured":"Andrew C.C. Yao (1985). Separating the polynomial-time hierarchy by oracles. In 26th Annual IEEE Symposium on Foundations of Computer Science, 1\u201310."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0156-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0156-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0156-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T10:37:57Z","timestamp":1569667077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0156-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,5]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["156"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0156-0","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,5]]}}}