1
talks
0
committee roles
0
leadership roles
2021–2021
years active
Contributions
QIP QCrypt TQC presenter award · △program ◇steering ○organising □local · filled = chair
Talks
| Title | Conference | Type | Co-authors |
|---|---|---|---|
| Degree vs. Approximate Degree and Quantum Implications of Huangs Sensitivity Theorem | QIP 2021 | regular | Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal |
Abstract Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~deg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. D(f) = O(Q(f)^4): The deterministic query complexity of f is at most quartic in the quantum query complexity of f. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if f is a nontrivial monotone graph property of an n-vertex graph specified by its adjacency matrix, then Q(f)=Omega(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Theta(sqrt{n}). |
|||
Collaborators
| Co-author | Joint talks |
|---|---|
| Avishay Tal | 1 |
| Robin Kothari | 1 |
| Scott Aaronson | 1 |
| Shalev Ben-David | 1 |