Name
Abstract | ||
|---|---|---|
Let F be a field and f_1, ..., f_k in F[x_1, ..., x_n] be a set of k polynomials of degree d in n variables over the field F. These polynomials are said to be algebraically dependent if there exists a nonzero k-variate polynomial A(t_1, ..., t_k) in F[t_1, ..., t_k] such that A(f_1, ..., f_k) = 0. A is then called an (f_1, ..., f_k)-annihilating polynomial. Within computer science, the notion of algebraic dependence was used in Dvir, Gabizon and Wigderson to construct explicit deterministic extractors from low-degree polynomial sources. They also observed that given (f_1, ..., f_k) 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: We give closely matching upper and lower bounds for the degree of the annihilating polynomial. We show that it is NP-hard to decide if A(0, .. ,0) equals zero. Indeed the annihilating polynomial A(t_1, .., t_k)$ does not even admit a small circuit representation unless the polynomial hierarchy collapses. 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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/CCC.2009.37 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
arithmetic circuit,field f.,algebraic dependence,annihilating polynomial,nonzero k-variate polynomial,algebraic independence,polynomial hierarchy collapse,low-degree polynomial source,k polynomial,actual computation,testing,polynomials,geometry,galois fields,data mining,randomized algorithm,algebra,computational complexity,set theory,arithmetic,computer science,np hard problem | Algebraic independence,Discrete mathematics,Finite field,Combinatorics,Zero of a function,Minimal polynomial (field theory),Polynomial,Square-free polynomial,Degree of a polynomial,Matrix polynomial,Mathematics | Conference |
ISSN | Citations | PageRank |
1093-0159 | 9 | 0.61 |
References | Authors | |
7 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |