Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew upper bound on block sensitivity and certificate complexity in terms of sensitivity
224
0
0.0
(
0
)
Added by
Xiaoming Sun
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Sensitivity cite{CD82,CDR86} and block sensitivity cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexity, the Sensitivity versus Block Sensitivity question, proposed by Nisan and Szegedy cite{Nisan94} in 1992, is whether these two complexity measures are polynomially related, i.e., whether $bs(f)=O(s(f)^{O(1)})$. We prove an new upper bound on block sensitivity in terms of sensitivity: $bs(f) leq 2^{s(f)-1} s(f)$. Previously, the best upper bound on block sensitivity was $bs(f) leq (frac{e}{sqrt{2pi}}) e^{s(f)} sqrt{s(f)}$ by Kenyon and Kutin cite{KK}. We also prove that if $min{s_0(f),s_1(f)}$ is a constant, then sensitivity and block sensitivity are linearly related, i.e. $bs(f)=O(s(f))$.
rate research
Read More
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.
We establish a precise relationship between spherical harmonics and Fourier basis functions over a hypercube randomly embedded in the sphere. In particular, we give a bound on the expected Boolean noise sensitivity of a randomly rotated function in terms of its spherical sensitivity, which we define according to its evolution under the spherical heat equation. As an application, we prove an average case of the Gotsman-Linial conjecture, bounding the sensitivity of polynomial threshold functions subjected to a random rotation.
In this work we introduce, both for classical communication complexity and query complexity, a modification of the partition bound introduced by Jain and Klauck [2010]. We call it the public-coin partition bound. We show that (the logarithm to the base two of) its communication complexity and query complexi
We prove upper bounds on deterministic communication complexity in terms of log of the rank and simp
In arXiv:1711.10132 a new approximating invariant ${mathsf{TC}}^{mathcal{D}}$ for topological complexity was introduced called $mathcal{D}$-topological complexity. In this paper, we explore more fully the properties of ${mathsf{TC}}^{mathcal{D}}$ and the connections between ${mathsf{TC}}^{mathcal{D}}$ and invariants of Lusternik-Schnirelmann type. We also introduce a new $mathsf{TC}$-type invariant $widetilde{mathsf{TC}}$ that can be used to give an upper bound for $mathsf{TC}$, $$mathsf{TC}(X)le {mathsf{TC}}^{mathcal{D}}(X) + leftlceil frac{2dim X -k}{k+1}rightrceil,$$ where $X$ is a finite dimensional simplicial complex with $k$-connected universal cover $tilde X$. The above inequality is a refinement of an estimate given by Dranishnikov.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
