Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR23-024 | 9th March 2023 19:23

#### Approximate degree lower bounds for oracle identification problems

TR23-024
Publication: 15th March 2023 23:14
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. We apply this 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 new lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.