文章基本信息

标题：Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions
本地全文：下载
作者：Siddhesh Chaubal ; Anna Gal
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-16
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Nisan and Szegedy [18] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. Until a recent breakthrough of Huang [15], the conjecture had been wide open in the general case, and was proved only for a few special classes of Boolean functions. Huang’s result [15] implies that block sensitivity is at most the 4th power of sensitivity for any Boolean function. It remains open if a tighter relationship between sensitivity and block sensitivity holds for arbitrary Boolean functions; the largest known gap between these measures is quadratic [20, 23, 9, 12, 4, 10]. We prove tighter bounds showing that block sensitivity is at most 3rd power, and in some cases at most square of sensitivity for subclasses of transitive functions, defined by various properties of their DNF (or CNF) representation. Our results improve and extend previous results regarding transitive functions. We obtain these results by proving tight (up to constant factors) lower bounds on the smallest possible sensitivity of functions in these classes. In another line of research, it has also been examined what is the smallest possible block sensitivity of transitive functions. Our results yield tight (up to constant factors) lower bounds on the block sensitivity of the classes we consider.