Campus Event Calendar
Event Entry
What and Who
Testing Algebraic Independence of Polynomials over Finite Fields
Anurag Pandey
Indian Institute of Technology Kanpur
PhD Application Talk
Master's student at IIT Kanpur (India)
AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI
Public Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 23 February 2015
09:00
120 Minutes
E1 4
r024
Saarbrücken
Abstract
Two polynomials f and g are said to be algebraically dependent over a field K if there exists a non-zero bivariate polynomial A with coefficients in K such that A(f,g) = 0. If no such polynomial exists, we say f and g are independent.
We consider the problem of finding an algorithm to test whether the given polynomials are algebraically independent. When the field has characteristic zero (eg: Rationals), this problem has a Randomised Polynomial (RP) time solution using the Jacobian Matrix of the given polynomials. The Jacobian matrix is full-rank iff the given polynomials are algebraically independent. However this criterion fails when the polynomials are taken over fields of positive characteristics. The current best known algorithm for the finite field case has the time complexity NP#P. The talk will cover the ideas we explored and discovered while studying the problem.
We consider the problem of finding an algorithm to test whether the given polynomials are algebraically independent. When the field has characteristic zero (eg: Rationals), this problem has a Randomised Polynomial (RP) time solution using the Jacobian Matrix of the given polynomials. The Jacobian matrix is full-rank iff the given polynomials are algebraically independent. However this criterion fails when the polynomials are taken over fields of positive characteristics. The current best known algorithm for the finite field case has the time complexity NP#P. The talk will cover the ideas we explored and discovered while studying the problem.
Contact
IMPRS-CS Office
0681 9325 1800
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
Stephanie Jörg, 02/20/2015 09:54 -- Created document.