{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:16:39Z","timestamp":1751516199841,"version":"3.41.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"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-77404-6_21","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"275-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions"],"prefix":"10.1007","author":[{"given":"Sourav","family":"Chakraborty","sequence":"first","affiliation":[]},{"given":"Sushrut","family":"Karmalkar","sequence":"additional","affiliation":[]},{"given":"Srijita","family":"Kundu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0218-6668","authenticated-orcid":false,"given":"Satyanarayana V.","family":"Lokam","sequence":"additional","affiliation":[]},{"given":"Nitin","family":"Saurabh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"issue":"3","key":"21_CR1","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":"5","key":"21_CR2","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"RB Boppana","year":"1997","unstructured":"Boppana, R.B.: The average sensitivity of bounded-depth circuits. Inf. Process. Lett. 63(5), 257\u2013261 (1997)","journal-title":"Inf. Process. Lett."},{"key":"21_CR3","unstructured":"Ganor, A., Komargodski, I., Lee, T., Raz, R.: On the noise stability of small Demorgan formulas, Technical report, Electronic Colloquium on Computational Complexity (ECCC) TR 12-174 (2012)"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Saks, M., Schramm, O.: Every decision tree has an influential variable. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 31\u201339. IEEE Computer Society (2005)","DOI":"10.1109\/SFCS.2005.34"},{"key":"21_CR5","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, Cambridge (2014)"},{"issue":"10","key":"21_CR6","doi-asserted-by":"publisher","first-page":"2993","DOI":"10.1090\/S0002-9939-96-03732-X","volume":"124","author":"E Friedgut","year":"1996","unstructured":"Friedgut, E., Kalai, G.: Every monotone graph property has a sharp threshold. Proc. Am. Math. Soc. 124(10), 2993\u20133002 (1996)","journal-title":"Proc. Am. Math. Soc."},{"issue":"3","key":"21_CR7","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1007\/s000390050015","volume":"7","author":"J Bourgain","year":"1997","unstructured":"Bourgain, J., Kalai, G.: Influences of variables and threshold intervals under group symmetries. Geom. Funct. Anal. (GAFA) 7(3), 438\u2013461 (1997)","journal-title":"Geom. Funct. Anal. (GAFA)"},{"issue":"3","key":"21_CR8","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1006\/jcss.1995.1043","volume":"50","author":"Y Mansour","year":"1995","unstructured":"Mansour, Y.: An $$\\cal{O}$$(n$$^{\\log \\log n}$$) learning algorithm for DNF under the uniform distribution. J. Comput. Syst. Sci. 50(3), 543\u2013550 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Kalai, A.T., Klivans, A.: Agnostically learning decision trees. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 527\u2013536 (2008)","DOI":"10.1145\/1374376.1374451"},{"key":"21_CR10","unstructured":"Gopalan, P., Kalai, A., Klivans, A.R.: A query algorithm for agnostically learning DNF? In: 21st Annual Conference on Learning Theory - COLT 2008, 9\u201312 July 2008, Helsinki, Finland, pp. 515\u2013516 (2008)"},{"issue":"1","key":"21_CR11","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/PL00009809","volume":"18","author":"E Friedgut","year":"1998","unstructured":"Friedgut, E.: Boolean functions with low average sensitivity depend on few coordinates. Combinatorica 18(1), 27\u201335 (1998)","journal-title":"Combinatorica"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions. In: Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 68\u201380 (1988)","DOI":"10.1109\/SFCS.1988.21923"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/978-3-642-22006-7_28","volume-title":"Automata, Languages and Programming","author":"R O\u2019Donnell","year":"2011","unstructured":"O\u2019Donnell, R., Wright, J., Zhou, Y.: The Fourier entropy\u2013influence conjecture for certain classes of Boolean functions. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 330\u2013341. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_28"},{"key":"21_CR14","unstructured":"Kalai, G.: The entropy\/influence conjecture. Terence Tao\u2019s blog: https:\/\/terrytao.wordpress.com\/2007\/08\/16\/gil-kalai-the-entropyinfluence-conjecture\/"},{"key":"21_CR15","unstructured":"Klivans, A., Lee, H., Wan, A.: Mansour\u2019s conjecture is true for random DNF formulas. In: Proceedings of the 23rd Conference on Learning Theory, pp. 368\u2013380 (2010)"},{"key":"21_CR16","unstructured":"Das, B., Pal, M., Visavaliya, V.: The entropy influence conjecture revisited. Technical report, arXiv:1110.4301 (2011)"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Tan, L.Y.: A composition theorem for the Fourier entropy-influence conjecture. In: Proceedings of Automata, Languages and Programming - 40th International Colloquium, pp. 780\u2013791 (2013)","DOI":"10.1007\/978-3-642-39206-1_66"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2016.05.006","volume":"654","author":"S Chakraborty","year":"2016","unstructured":"Chakraborty, S., Kulkarni, R., Lokam, S.V., Saurabh, N.: Upper bounds on Fourier entropy. Theor. Comput. Sci. 654, 92\u2013112 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR19","doi-asserted-by":"crossref","unstructured":"Wan, A., Wright, J., Wu, C.: Decision trees, protocols and the entropy-influence conjecture. In: Innovations in Theoretical Computer Science, pp. 67\u201380 (2014)","DOI":"10.1145\/2554797.2554806"},{"issue":"4","key":"21_CR20","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/377939.377945","volume":"2","author":"JS Hicks","year":"1959","unstructured":"Hicks, J.S., Wheeling, R.F.: An efficient method for generating uniformly distributed points on the surface of an n-dimensional sphere. Commun. ACM 2(4), 17\u201319 (1959)","journal-title":"Commun. ACM"},{"issue":"4","key":"21_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/377939.377946","volume":"2","author":"ME Muller","year":"1959","unstructured":"Muller, M.E.: A note on a method for generating points uniformly on n-dimensional spheres. Commun. ACM 2(4), 19\u201320 (1959)","journal-title":"Commun. ACM"},{"issue":"2","key":"21_CR22","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1214\/aoms\/1177692644","volume":"43","author":"G Marsaglia","year":"1972","unstructured":"Marsaglia, G.: Choosing a point from the surface of a sphere. Ann. Math. Stat. 43(2), 645\u2013646 (1972)","journal-title":"Ann. Math. Stat."},{"key":"21_CR23","unstructured":"Petersen, W.P., Bernasconi, A.: Uniform sampling from an $$n$$-sphere. Technical report. Swiss Center for Scientific Computing (1997)"},{"key":"21_CR24","doi-asserted-by":"publisher","first-page":"197","DOI":"10.4064\/sm-58-2-197-208","volume":"58","author":"SJ Szarek","year":"1976","unstructured":"Szarek, S.J.: On the best constants in the Khinchine inequality. Studia Math. 58, 197\u2013208 (1976)","journal-title":"Studia Math."},{"key":"21_CR25","first-page":"241","volume":"39","author":"I Shevtsova","year":"2012","unstructured":"Shevtsova, I.: Moment-type estimates with asymptotically optimal structure for the accuracy of the normal approximation. Annales Mathematicae Et Informaticae 39, 241\u2013307 (2012)","journal-title":"Annales Mathematicae Et Informaticae"},{"key":"21_CR26","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001","volume-title":"Concentration Inequalities: A Nonasymptotic Theory of Independence","author":"S Boucheron","year":"2013","unstructured":"Boucheron, S., Lugosi, G., Massart, P.: Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford (2013)"},{"key":"21_CR27","doi-asserted-by":"publisher","DOI":"10.1002\/0471722162","volume-title":"Order Statistics","author":"HA David","year":"2003","unstructured":"David, H.A., Nagaraja, H.N.: Order Statistics, 3rd edn. Wiley, Hoboken (2003)","edition":"3"},{"key":"21_CR28","volume-title":"An Introduction to Probability Theory and Its Applications","author":"W Feller","year":"1968","unstructured":"Feller, W.: An Introduction to Probability Theory and Its Applications, vol. 1, 3rd edn. Wiley, Hoboken (1968)","edition":"3"},{"issue":"2","key":"21_CR29","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s00037-014-0086-z","volume":"23","author":"DM Kane","year":"2014","unstructured":"Kane, D.M.: The correct exponent for the Gotsman-Linial Conjecture. Comput. Complex. 23(2), 151\u2013175 (2014)","journal-title":"Comput. Complex."}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:29:29Z","timestamp":1751480969000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_21","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":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","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":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}