Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Testing Algebraic Independence of Polynomials over Finite Fields
Speaker:Anurag Pandey
coming from:Indian Institute of Technology Kanpur
Speakers Bio:Master's student at IIT Kanpur (India)
Event Type:PhD Application Talk
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 23 February 2015
Duration:120 Minutes
Building:E1 4
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.

Name(s):IMPRS-CS Office
Phone:0681 9325 1800
EMail:--email address not disclosed on the web
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Stephanie Jörg, 02/20/2015 09:54 AM -- Created document.