  We introduce and study Certificate Game complexity, a measure of complexity
based on the probability of winning a game where two players are given inputs
with different function values and are asked to output $i$ such that $x_i\neq
y_i$ (zero-communication setting).
  We give upper and lower bounds for private coin, public coin, shared
entanglement and non-signaling strategies, and give some separations. We show
that complexity in the public coin model is upper bounded by Randomized query
and Certificate complexity. On the other hand, it is lower bounded by
fractional and randomized certificate complexity, making it a good candidate to
prove strong lower bounds on randomized query complexity. Complexity in the
private coin model is bounded from below by zero-error randomized query
complexity.
  The quantum measure highlights an interesting and surprising difference
between classical and quantum query models. Whereas the public coin certificate
game complexity is bounded from above by randomized query complexity, the
quantum certificate game complexity can be quadratically larger than quantum
query complexity. We use non-signaling, a notion from quantum information, to
give a lower bound of $n$ on the quantum certificate game complexity of the
$OR$ function, whose quantum query complexity is $\Theta(\sqrt{n})$, then go on
to show that this ``non-signaling bottleneck'' applies to all functions with
high sensitivity, block sensitivity or fractional block sensitivity.
  We consider the single-bit version of certificate games (inputs of the two
players have Hamming distance $1$). We prove that the single-bit version of
certificate game complexity with shared randomness is equal to sensitivity up
to constant factors, giving a new characterization of sensitivity. The
single-bit version with private randomness is equal to $\lambda^2$, where
$\lambda$ is the spectral sensitivity.
