Algebraic Independence and Applications

algebra that generalizes linear independence of linear polynomials to
higher degree. Polynomials f_1,...,f_m are called *algebraically
independent* if there is no non-zero polynomial F such that
F(f_1,...,f_m)=0. Based on this we could also define a notion of rank
for a set of polynomials - transcendence degree (short, trdeg). Being
a fundamental concept, trdeg appears in many contexts in algebraic
computation. In this talk I will describe algorithms for computing
trdeg efficiently in practice, and then mention various situations
where the concept is useful. To name a few - circuit lower bounds,
constructions of algebraic extractors, and polynomial identity
testing.

This is based on a joint work with Malte Beecken and Johannes Mittmann
(ICALP 2011).