We show a partial Boolean function $f$ together with an input $xin f^{-1}left(*right)$ such that both $C_{bar{0}}left(f,xright)$ and $C_{bar{1}}left(f,xright)$ are at least $Cleft(fright)^{2-oleft(1right)}$. Due to recent results by Ben-David, G{o}{o}s, Jain, and Kothari, this result implies several other separations in query and communication complexity. For example, it gives a function $f$ with $C(f)=Omega(deg^{2-oleft(1right)}(f))$ where $C$ and $deg$ denote certificate complexity and polynomial degree of $f$. (This is the first improvement over a separation between $C(f)$ and $deg(f)$ by Kushilevitz and Nisan in 1995.) Other implications of this result are an improved separation between sensitivity and polynomial degree, a near-optimal lower bound on conondeterministic communication complexity for Clique vs. Independent Set problem and a near-optimal lower bound on complexity of Alon--Saks--Seymour problem in graph theory.
تحميل البحث