Please join us on Dec 2nd at 10am in Siebel 3401 where Michael A. Forbes will give a talk, “Approximating Transcendence Degree in Medium Characteristic”. Please see their abstract below:
Abstract: A set of multivariate polynomials F=(f_1,...,f_m) are algebraically independent if there is no non-zero polynomial P such that P(f_1,...,f_m)=0. The transcendence degree of the set F is the maximum size of any algebraically independent subset. We consider the problem of computing the transcendence degree, when the polynomials F are given succinctly by algebraic circuits. This problem is motivated by applications to the polynomial identity testing problem, as well as the task of computing the dimension of algebraic varieties.
It is currently known that this problem is efficiently solvable over fields of characteristic zero, and also when the field is of exponentially large characteristic. We show that the transcendence degree can be efficiently approximated when the characteristic is polynomially large.