文章基本信息

标题：New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
本地全文：下载
作者：Siddhesh Chaubal ; Anna G{\'a}l
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：122
页码：1-16
DOI：10.4230/LIPIcs.FSTTCS.2018.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Nisan and Szegedy [Nisan and Szegedy, 1994] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity. In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Our constructions have several novel aspects. For example, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.
关键词：Sensitivity Conjecture; Boolean Functions; Complexity Measures