Lower Bounding the AND-OR Tree via Symmetrization

We prove a simple, nearly tight lower bound on the approximate degree of the two-level $\mathsf{A}\mathsf{N}\mathsf{D}$-$\mathsf{O}\mathsf{R}$ tree using symmetrization arguments. Specifically, we show that $\widetilde{$\mathrm{d}\mathrm{e}\mathrm{g}$}($\mathsf{A}\mathsf{N}\mathsf{D}$_m \circ $\mathsf{O}\mathsf{R}$_n) = \widetilde{\Omega}(\sqrt{mn})$. We prove this lower bound via reduction to the $\mathsf{O}\mathsf{R}$ 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].