$\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?
Block sensitivity and degree
complexity theory