Max-Planck-Institut für Informatik
max planck institut
informatik
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
Language:English
Date, Time and Location
Date:Monday, 23 February 2015
Time:09:00
Duration:120 Minutes
Location:Saarbrücken
Building:E1 4
Room:r024
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.

Contact
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
Note:
Attachments, File(s):

Created by:Stephanie Jörg/MPI-INF, 02/20/2015 09:19 AMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Stephanie Jörg, 02/20/2015 09:54 AM -- Created document.