{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:03Z","timestamp":1763468223975},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_9","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"101-113","source":"Crossref","is-referenced-by-count":5,"title":["Tighter Relations between Sensitivity and Other Complexity Measures"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[]},{"given":"Mohammad","family":"Bavarian","sequence":"additional","affiliation":[]},{"given":"Yihan","family":"Gao","sequence":"additional","affiliation":[]},{"given":"Jieming","family":"Mao","sequence":"additional","affiliation":[]},{"given":"Xiaoming","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Song","family":"Zuo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Aaronson, S.: My philomath project: Sensitivity versus block-sensitivity, Shtetl Optimized blog (June 13, 2010), \n                    \n                      http:\/\/www.scottaaronson.com\/blog\/?p=453","key":"9_CR1"},{"unstructured":"Aaronson, S., Ambainis, A., Balodis, K., Bavarian, M.: Weak Parity. In: ICALP (to appear, 2014)","key":"9_CR2"},{"key":"9_CR3","first-page":"116","volume":"18","author":"A. Ambainis","year":"2011","unstructured":"Ambainis, A., Sun, X.: New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 116 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"9_CR4","volume-title":"Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability","author":"B. Bollob\u00e1s","year":"1986","unstructured":"Bollob\u00e1s, B.: Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge (1986)"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science\u00a0288(1), 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Chung, F.R.K., F\u00fcredi, Z., Graham, R.L., Seymour, P.: On induced subgraphs of the cube. J. Comb. Theory Ser. A\u00a049 (1988)","key":"9_CR6","DOI":"10.1016\/0097-3165(88)90034-9"},{"issue":"5","key":"9_CR7","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1017\/S0963548306008340","volume":"16","author":"D. Falik","year":"2007","unstructured":"Falik, D., Samorodnitsky, A.: Edge-isoperimetric inequalities and influences. Combinatorics, Probability & Computing\u00a016(5), 693\u2013712 (2007)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/0097-3165(92)90060-8","volume":"61","author":"C. Gotsman","year":"1992","unstructured":"Gotsman, C., Linial, N.: The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A\u00a061(1), 142\u2013146 (1992)","journal-title":"Journal of Combinatorial Theory, Series A"},{"doi-asserted-by":"crossref","unstructured":"Harper, L.: Optimal numberings and isoperimetric problems on graphs. Journal of Combinatorial Theory\u00a01 (1966)","key":"9_CR9","DOI":"10.1016\/S0021-9800(66)80059-5"},{"doi-asserted-by":"crossref","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the Sensitivity Conjecture. Theory of Computing Library, Graduate Surveys\u00a0(4), 1\u201327 (2011)","key":"9_CR10","DOI":"10.4086\/toc.gs.2011.004"},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ic.2002.12.001","volume":"189","author":"C. Kenyon","year":"2004","unstructured":"Kenyon, C., Kutin, S.: Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions. Information and Computation\u00a0189(1), 43\u201353 (2004)","journal-title":"Information and Computation"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity\u00a04, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"issue":"2","key":"9_CR13","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/BF01200762","volume":"15","author":"D. Rubinstein","year":"1995","unstructured":"Rubinstein, D.: Sensitivity vs. Block Sensitivity of Boolean functions. Combinatorica\u00a015(2), 297\u2013299 (1995)","journal-title":"Combinatorica"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-12689-9_124","volume-title":"Foundations of Computation Theory","author":"H.U. Simon","year":"1983","unstructured":"Simon, H.U.: A Tight \u03a9(loglogn)-Bound on the Time for Parallel Ram\u2019s to Compute Nondegenerated Boolean Functions. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol.\u00a0158, pp. 439\u2013444. Springer, Heidelberg (1983)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:42:35Z","timestamp":1558910555000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}