The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f within 13 at every point. We prove that the function ni=1nj=1xij , known as the AND-OR tree, has approximate degree (n) This lower bound is tight and closes a line of research on the problem, the best previous bound being (n075). More generally, we prove that the function mi=1nj=1xij has approximate degree (mn) which is tight. The same lower bound was obtained independently by Bun and Thaler (2013) using related techniques.
展开▼
