Lower Bounding the AND-OR Tree via Symmetrization

Abstract

We prove a simple, nearly tight lower bound on the approximate degree of the two-level $\mathsf{AND}$-$\mathsf{OR}$ tree using symmetrization arguments. Specifically, we show that $\widetilde{\mathrm{deg}}({\mathsf{AND}}_m\circ {\mathsf{OR}}_n)=\tilde{\Omega }(\sqrt{mn})$. We prove this lower bound via reduction to the $\mathsf{OR}$ function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].

12 pages, 1 figure. V2: fixed typos. V3: improved presentation, added journal reference. V4: added forward reference to [HV20]. V5: corrected various typos

References in corpus (2)

• The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Cited by in corpus (1)

• Quantum Lower Bounds for Approximate Counting via Laurent Polynomials