A Dual Polynomial for OR
arXiv:0803.4516
Abstract
We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynomial for a given function, and apply the duality theory. The duality theory says that the primal program has no solution if and only if its dual has a solution. Therefore one can prove the nonexistence of an approximate polynomial by exhibiting a dual solution, coined the dual polynomial. We construct such a polynomial.
6 pages
References in corpus (2)
Cited by in corpus (5)
- Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
- Faster Private Release of Marginals on Small Databases
- Dual Polynomials for Collision and Element Distinctness
- Improved Approximate Degree Bounds For k-distinctness
- Semidefinite programming formulations for the completely bounded norm of a tensor