Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Lower Bounding the AND-OR Tree via Symmetrization

Lower Bounding the AND-OR Tree via Symmetrization We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that deg(ANDm ORn) = (√mn). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2]. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Lower Bounding the AND-OR Tree via Symmetrization

Loading next page...
 
/lp/association-for-computing-machinery/lower-bounding-the-and-or-tree-via-symmetrization-Cy1O3ENo0K
Publisher
Association for Computing Machinery
Copyright
Copyright © 2021 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3434385
Publisher site
See Article on Publisher Site

Abstract

We prove a simple, nearly tight lower bound on the approximate degree of the two-level AND-OR tree using symmetrization arguments. Specifically, we show that deg(ANDm ORn) = (√mn). We prove this lower bound via reduction to the OR function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [6, 10, 21]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson et al. [2].

Journal

ACM Transactions on Computation Theory (TOCT)Association for Computing Machinery

Published: Jan 21, 2021

Keywords: AND-OR tree

References