Let F be a field and f1, .. , fk be a set of n-variate polynomials of degree d over F. These polynomials are said to be algebraically dependent if there exists a nonzero k-variate polynomial A such that A(f1, .. , fk) = 0. A is then said to be an (f1, .. , fk)-annihilating polynomial.
Within computer science, the notion of algebraic dependence was used by Dvir, Gabizon and Wigderson (FOCS 2007) to construct explicit deterministic extractors from low-degree polynomial sources. They also observed that given (f1, .. , fk) as arithmetic circuits, there exists an efficient randomized algorithm for testing their algebraic independence. The problems of determining good bounds on the degree of the annihilating polynomial and of computing it explicitly were posed as open questions. We solve the two posed problems in the following way:
This then, to the best of our knowledge, is the only natural computational problem where determining the existence of an object (the annihilating polynomial in our case) can be done efficiently but the actual computation of the object is provably hard.
|Published in||Conference on Computational Complexity (CCC)|
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. http://www.ieee.org/