A Dual Polynomial for OR

Simple item page
dc.creatorSpalek, Robert
dc.date2008-03-31
dc.date.accessioned2026-07-07T09:29:28Z
dc.date.available2026-07-07T09:29:28Z
dc.descriptionWe 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.
dc.description6 pages
dc.identifierhttps://arxiv.org/abs/0803.4516
dc.identifierhttp://arxiv.org/abs/0803.4516
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/157796
dc.subjectComputational Complexity
dc.subjectF.1.2
dc.titleA Dual Polynomial for OR
dc.typetext

Files

Collections

arXiv