$\newcommand{\bs}{\mathrm{bs}}$What is the largest gap known between block sensitivity ($\bs(f)$) of a boolean function ($f$) and degree of a polynomial ($\deg(f)$) that represents/approximates it?

We know of lower bound $$\bs(f)\leq c\deg^2(f)$$ for some $c>0$. Is there a Boolean function that achieves this separation?

  • $\begingroup$ Turbo, there are some surveys on the subject. Have you looked at them? Surely one of them will contain the answer. $\endgroup$ Jan 11 '15 at 22:07
  • $\begingroup$ I looked at buhrman's survey. Have I missed obvious facts? $\endgroup$
    – Mr.
    Jan 12 '15 at 2:36
  • 1
    $\begingroup$ Whatever's not in the up to date surveys is probably not known. Was it explicitly mentioned that no separation is known? $\endgroup$ Jan 12 '15 at 7:16
  • $\begingroup$ @YuvalFilmus I will check back again. $\endgroup$
    – Mr.
    Jan 12 '15 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.