{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:54Z","timestamp":1759638954531,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319741796"},{"type":"electronic","value":"9783319741802"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-74180-2_22","type":"book-chapter","created":{"date-parts":[[2018,1,15]],"date-time":"2018-01-15T15:12:55Z","timestamp":1516029175000},"page":"260-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Alternation, Sparsity and Sensitivity: Combinatorial Bounds and Exponential Gaps"],"prefix":"10.1007","author":[{"given":"Krishnamoorthy","family":"Dinesh","sequence":"first","affiliation":[]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,16]]},"reference":[{"key":"22_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-319-34171-2_2","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Ambainis","year":"2016","unstructured":"Ambainis, A., Pr\u016bsis, K., Vihrovs, J.: Sensitivity versus certificate complexity of Boolean functions. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 16\u201328. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-34171-2_2"},{"key":"22_CR2","unstructured":"Bafna, M., Lokam, S.V., Tavenas, S., Velingker, A.: On the sensitivity conjecture for read-$$k$$ formulas. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krak\u00f3w, Poland, pp. 16:1\u201316:14 (2016)"},{"issue":"3","key":"22_CR3","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1109\/12.755000","volume":"48","author":"A Bernasconi","year":"1999","unstructured":"Bernasconi, A., Codenotti, B.: Spectral analysis of Boolean functions as a graph eigenvalue problem. IEEE Trans. Comput. 48(3), 345\u2013351 (1999)","journal-title":"IEEE Trans. Comput."},{"key":"22_CR4","unstructured":"Blais, E., Canonne, C.L., Oliveira, I.C., Servedio, R.A., Tan, L.-Y.: Learning circuits with few negations. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, 24\u201326 August 2015, Princeton, NJ, USA, pp. 512\u2013527 (2015)"},{"issue":"1","key":"22_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. Theor. Comput. Sci. 288(1), 21\u201343 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR6","unstructured":"Karthik, C.S., Tavenas, S.: On the sensitivity conjecture for disjunctive normal forms. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, 13\u201315 December 2016, Chennai, India, pp. 15:1\u201315:15 (2016)"},{"issue":"4","key":"22_CR7","first-page":"51","volume":"13","author":"S Chakraborty","year":"2011","unstructured":"Chakraborty, S.: On the sensitivity of cyclically-invariant Boolean functions. Discrete Math. Theor. Comput. Sci. 13(4), 51\u201360 (2011)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"1","key":"22_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"S Cook","year":"1986","unstructured":"Cook, S., Dwork, C., Reischuk, R.: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. 15(1), 87\u201397 (1986)","journal-title":"SIAM J. Comput."},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Gilmer, J., Kouck\u00fd, M., Saks, M.E.: A new approach to the sensitivity conjecture. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, pp. 247\u2013254. ACM, New York (2015)","DOI":"10.1145\/2688073.2688096"},{"key":"22_CR10","unstructured":"Gopalan, P., Servedio, R.A., Wigderson, A.: Degree and sensitivity: tails of two distributions. In: 31st Conference on Computational Complexity, CCC 2016, Tokyo, Japan, pp. 13:1\u201313:23 (2016)"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2016.11.027","volume":"660","author":"S Guo","year":"2017","unstructured":"Guo, S., Komargodski, I.: Negation-limited formulas. Theor. Comput. Sci. 660, 75\u201385 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"22_CR12","first-page":"1","volume":"4","author":"P Hatami","year":"2011","unstructured":"Hatami, P., Kulkarni, R., Pankratov, D.: Variations on the sensitivity conjecture. Theor. Comput. Libr. Grad. Surv. 4, 1\u201327 (2011)","journal-title":"Theor. Comput. Libr. Grad. Surv."},{"key":"22_CR13","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4","volume-title":"Boolean Function Complexity: Advances and Frontiers","author":"S Jukna","year":"2012","unstructured":"Jukna, S.: Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics. Springer, Heidelberg (2012)"},{"issue":"1","key":"22_CR14","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 $$\\ell $$-block sensitivity of Boolean functions. Inf. Comput. 189(1), 43\u201353 (2004)","journal-title":"Inf. Comput."},{"key":"22_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-642-38233-8_25","volume-title":"Algorithms and Complexity","author":"R Kulkarni","year":"2013","unstructured":"Kulkarni, R., Santha, M.: Query complexity of matroids. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 300\u2013311. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38233-8_25"},{"key":"22_CR16","unstructured":"Lin, C., Zhang, S.: Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), vol. 80, pp. 51:1\u201351:13, Dagstuhl, Germany (2017)"},{"issue":"3","key":"22_CR17","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N Linial","year":"1993","unstructured":"Linial, N., Mansour, Y., Nisan, N.: Constant depth circuits, fourier transform, and learnability. J. ACM 40(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"issue":"4","key":"22_CR18","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1145\/320941.320945","volume":"5","author":"AA Markov","year":"1958","unstructured":"Markov, A.A.: On the inversion complexity of a system of functions. J. ACM 5(4), 331\u2013334 (1958)","journal-title":"J. ACM"},{"key":"22_CR19","unstructured":"Montanaro, A., Osborne, T.: On the communication complexity of XOR functions. CoRR abs\/0909.3392 (2009)"},{"issue":"6","key":"22_CR20","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1137\/0220062","volume":"20","author":"N Nisan","year":"1991","unstructured":"Nisan, N.: CREW PRAMs and decision trees. SIAM J. Comput. 20(6), 999\u20131007 (1991)","journal-title":"SIAM J. Comput."},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 462\u2013467. ACM, New York (1992)","DOI":"10.1145\/129712.129757"},{"key":"22_CR22","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, New York (2014)"},{"key":"22_CR23","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 $$\\omega $$(loglog n)-bound on the time for parallel Ram\u2019s to compute nondegenerated boolean functions. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol. 158, pp. 439\u2013444. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/3-540-12689-9_124"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Tal, A.: Properties and applications of Boolean function composition. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 441\u2013454. ACM, New York (2013)","DOI":"10.1145\/2422436.2422485"},{"key":"22_CR25","doi-asserted-by":"crossref","unstructured":"Tsang, H.Y., Wong, C.H., Xie, N., Zhang, S.: Fourier sparsity, spectral norm, and the log-rank conjecture. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26\u201329 October 2013, Berkeley, CA, USA, pp. 658\u2013667 (2013)","DOI":"10.1109\/FOCS.2013.76"},{"issue":"3","key":"22_CR26","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(84)90019-X","volume":"18","author":"G Tur\u00e1n","year":"1984","unstructured":"Tur\u00e1n, G.: The critical complexity of graph properties. Inf. Process. Lett. 18(3), 151\u2013153 (1984)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"22_CR27","first-page":"255","volume":"9","author":"Z Zhang","year":"2009","unstructured":"Zhang, Z., Shi, Y.: Communication complexities of symmetric XOR functions. Quantum Inf. Comput. 9(3), 255\u2013263 (2009)","journal-title":"Quantum Inf. Comput."},{"issue":"26\u201328","key":"22_CR28","doi-asserted-by":"publisher","first-page":"2612","DOI":"10.1016\/j.tcs.2010.03.027","volume":"411","author":"Z Zhang","year":"2010","unstructured":"Zhang, Z., Shi, Y.: On the parity complexity measures of Boolean functions. Theor. Comput. Sci. 411(26\u201328), 2612\u20132618 (2010)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-74180-2_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:52:12Z","timestamp":1709826732000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-74180-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319741796","9783319741802"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-74180-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 January 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CALDAM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Algorithms and Discrete Applied Mathematics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guwahati","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"India","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 February 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 February 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"caldam2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.iitg.ac.in\/caldam2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}