  The approximate degree of a Boolean function is the minimum degree of real
polynomial that approximates it pointwise. For any Boolean function, its
approximate degree serves as a lower bound on its quantum query complexity, and
generically lifts to a quantum communication lower bound for a related
function.
  We introduce a framework for proving approximate degree lower bounds for
certain oracle identification problems, where the goal is to recover a hidden
binary string $x \in \{0, 1\}^n$ given possibly non-standard oracle access to
it. Our lower bounds apply to decision versions of these problems, where the
goal is to compute the parity of $x$. We apply our framework to the ordered
search and hidden string problems, proving nearly tight approximate degree
lower bounds of $\Omega(n/\log^2 n)$ for each. These lower bounds generalize to
the weakly unbounded error setting, giving a new quantum query lower bound for
the hidden string problem in this regime. Our lower bounds are driven by
randomized communication upper bounds for the greater-than and equality
functions.
