  We show a partial Boolean function $f$ together with an input $x\in
f^{-1}\left(*\right)$ such that both $C_{\bar{0}}\left(f,x\right)$ and
$C_{\bar{1}}\left(f,x\right)$ are at least
$C\left(f\right)^{2-o\left(1\right)}$. 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-o\left(1\right)}(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.
