{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:53:37Z","timestamp":1763459617928,"version":"3.45.0"},"publisher-location":"New York, NY, USA","reference-count":24,"publisher":"ACM","license":[{"start":{"date-parts":[[2017,1,14]],"date-time":"2017-01-14T00:00:00Z","timestamp":1484352000000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1319788, CCF-1420349"],"award-info":[{"award-number":["CCF-1319788, CCF-1420349"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2016,1,14]]},"DOI":"10.1145\/2840728.2840738","type":"proceedings-article","created":{"date-parts":[[2016,1,5]],"date-time":"2016-01-05T09:26:11Z","timestamp":1451985971000},"page":"59-70","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Smooth Boolean Functions are Easy"],"prefix":"10.1145","author":[{"given":"Parikshit","family":"Gopalan","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noam","family":"Nisan","sequence":"additional","affiliation":[{"name":"Microsoft Research and the Hebrew University, Jerusalem, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Columbia University, New York, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"School of Mathematics, Institute for Advanced Study, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,1,14]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"101","volume-title":"41st International Colloquium, ICALP 2014","author":"Ambainis Andris","year":"2014","unstructured":"Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, pages 101--113, 2014."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.021"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_4"},{"key":"e_1_3_2_1_4_1","volume-title":"Sensitivity versus certificate complexity of boolean functions. CoRR, abs\/1503.07691","author":"Ambainis Andris","year":"2015","unstructured":"Andris Ambainis, Krisjanis Prusis, and Jevgenijs Vihrovs. Sensitivity versus certificate complexity of boolean functions. CoRR, abs\/1503.07691, 2015."},{"key":"e_1_3_2_1_5_1","volume-title":"New separation betweent $s(f)$ and $bs(f)$. CoRR, abs\/1108.3494","author":"Ambainis Andris","year":"2011","unstructured":"Andris Ambainis and Xiaoming Sun. New separation betweent $s(f)$ and $bs(f)$. CoRR, abs\/1108.3494, 2011."},{"key":"e_1_3_2_1_6_1","first-page":"122","volume-title":"TAMC 2015","author":"Ambainis Andris","year":"2015","unstructured":"Andris Ambainis and Jevgenijs Vihrovs. Size of sets with small sensitivity: a generalization of simon's lemma. In Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, pages 122--133, 2015."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0451-6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215006"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1088\/0022-3719\/12\/1\/008"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688096"},{"key":"e_1_3_2_1_12_1","volume-title":"Variations on the Sensitivity Conjecture. Number 4 in Graduate Surveys","author":"Hatami Pooya","year":"2011","unstructured":"Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the Sensitivity Conjecture. Number 4 in Graduate Surveys. Theory of Computing Library, 2011."},{"key":"e_1_3_2_1_13_1","first-page":"30","article-title":"The theory of approximation","volume":"19","author":"Jackson Dunham","year":"1930","unstructured":"Dunham Jackson. The theory of approximation. New York, 19:30, 1930.","journal-title":"New York"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2190632"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2002.12.001"},{"key":"e_1_3_2_1_16_1","volume-title":"Extremal bounds for bootstrap percolation in the hypercube","author":"Morrison Natasha","year":"2015","unstructured":"Natasha Morrison and Jonathan A. Noel. Extremal bounds for bootstrap percolation in the hypercube, 2015."},{"key":"e_1_3_2_1_17_1","unstructured":"K. Matulef R. O'Donnell R. Rubinfeld and R. Servedio. Testing Halfspaces. Technical Report 128 Electronic Colloquium in Computational Complexity 2007. Full version in FOCS 2007."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220062"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-4131-3_20"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2683783"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200762"},{"key":"e_1_3_2_1_23_1","volume-title":"A tight omega(log log n)-bound on the time for parallel ram's to compute nondegenerated boolean functions. Information and Control, 55(1--3):102--106","author":"Simon Hans-Ulrich","year":"1982","unstructured":"Hans-Ulrich Simon. A tight omega(log log n)-bound on the time for parallel ram's to compute nondegenerated boolean functions. Information and Control, 55(1--3):102--106, 1982."},{"key":"e_1_3_2_1_24_1","volume-title":"\u00dcber die analytische darstellbarkeit sogenannter willk\u00fcrlicher functionen einer reellen ver\u00e4nderlichen. Sitzungsberichte der K\u00f6niglich Preu\u00dfischen Akademie der Wissenschaften zu Berlin, 2:633--639","author":"Weierstrass Karl","year":"1885","unstructured":"Karl Weierstrass. \u00dcber die analytische darstellbarkeit sogenannter willk\u00fcrlicher functionen einer reellen ver\u00e4nderlichen. Sitzungsberichte der K\u00f6niglich Preu\u00dfischen Akademie der Wissenschaften zu Berlin, 2:633--639, 1885."}],"event":{"name":"ITCS'16: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts USA","acronym":"ITCS'16"},"container-title":["Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840738","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2840728.2840738","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2840728.2840738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:48:38Z","timestamp":1763459318000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2840728.2840738"}},"subtitle":["Efficient Algorithms for Low-Sensitivity Functions"],"short-title":[],"issued":{"date-parts":[[2016,1,14]]},"references-count":24,"alternative-id":["10.1145\/2840728.2840738","10.1145\/2840728"],"URL":"https:\/\/doi.org\/10.1145\/2840728.2840738","relation":{},"subject":[],"published":{"date-parts":[[2016,1,14]]},"assertion":[{"value":"2016-01-14","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}