Tighter relations between sensitivity and other complexity measures

DOI10.1007/978-3-662-43948-7_9MaRDI QIDQ5167734zbMATH OpenOpenAlexFDO

Authors Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo, Andris Ambainis

Publication date 1 July 2014

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.3419

Mathematics Subject Classification ID

Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25)

Abstract: Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004. In this work, we present new upper bounds for various complexity measures in terms of sensitivity improving the bounds provided by Kenyon and Kutin. Specifically, we show that deg(f)^{1-o(1)}=O(2^{s(f)}) and C(f) < 2^{s(f)-1} s(f); these in turn imply various corollaries regarding the relation between sensitivity and other complexity measures, such as block sensitivity, via known results. The gap between sensitivity and other complexity measures remains exponential but these results are the first improvement for this difficult problem that has been achieved in a decade.

Recommendations

• A tighter relation between sensitivity complexity and certificate complexity
• A tighter relation between sensitivity complexity and certificate complexity
• Sensitivity versus certificate complexity of Boolean functions
• On the sensitivity conjecture
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions

Cited in

(24)

• The average sensitivity of bounded-depth formulas
• Conflict complexity is lower bounded by block sensitivity
• Sensing as a complexity measure
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
• Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
• A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity
• Size of sets with small sensitivity: a generalization of Simon's lemma
• A New Approach to the Sensitivity Conjecture
• scientific article; zbMATH DE number 4130025 (Why is no real title available?)
• Relativization of complexity and sensitivity
• On the sensitivity conjecture
• On the sensitivity conjecture for read-k formulas
• On the sensitivity conjecture for disjunctive normal forms
• Low-sensitivity functions from unambiguous certificates
• Pseudorandom generators for low sensitivity functions
• New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity
• On the resolution of the sensitivity conjecture
• A communication game related to the sensitivity conjecture
• Sensitivity versus certificate complexity of Boolean functions
• A tighter relation between sensitivity complexity and certificate complexity
• On the modulo degree complexity of Boolean functions
• A tighter relation between sensitivity complexity and certificate complexity
• Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

This page was built for publication: Tighter relations between sensitivity and other complexity measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167734)