ECCC-Report TR23-024https://eccc.weizmann.ac.il/report/2023/024Comments and Revisions published for TR23-024en-usTue, 30 May 2023 16:58:03 +0300
Revision 1
| Approximate degree lower bounds for oracle identification problems |
Mark Bun,
Nadezhda Voronova
https://eccc.weizmann.ac.il/report/2023/024#revision1The 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.Tue, 30 May 2023 16:58:03 +0300https://eccc.weizmann.ac.il/report/2023/024#revision1
Paper TR23-024
| Approximate degree lower bounds for oracle identification problems |
Mark Bun,
Nadezhda Voronova
https://eccc.weizmann.ac.il/report/2023/024The 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. 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.Wed, 15 Mar 2023 23:14:17 +0200https://eccc.weizmann.ac.il/report/2023/024