$\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, 2015 at 22:07
  • $\begingroup$ I looked at buhrman's survey. Have I missed obvious facts? $\endgroup$
    – Turbo
    Jan 12, 2015 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, 2015 at 7:16
  • $\begingroup$ @YuvalFilmus I will check back again. $\endgroup$
    – Turbo
    Jan 12, 2015 at 19:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.