اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNew upper bound on block sensitivity and certificate complexity in terms of sensitivity
228
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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))$.
قيم البحث
اقرأ أيضاً
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 r
elated 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 t
erms 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 ba
se 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
