# Block sensitivity and degree

$\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?

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