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:A deterministic PTAS for the transcendence degree of constant degree polynomials
Speaker:Gorav Jindal
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 26 June 2018
Duration:45 Minutes
Building:E1 4
Consider a square m x m matrix M whose entries are polynomials in n variables x1,x2,..,xn over a field F. We want to compute the rank of this matrix M over the rational function field F(x1,x2,...,xn). If the entries of M are linear polynomials then computation of rank of M is equivalent to the polynomial identity testing (of algebraic branching programs). So we have trivial randomized polynomial time algorithms for this problem. But a deterministic polynomial time algorithm remains elusive. Therefore it is reasonable to ask whether one can approximate the rank of M in deterministic polynomial time. A deterministic PTAS for the rank of M (when the entries of M are linear polynomials) was given in BJP17.

In this work we consider the matrices M whose entries are constant degree polynomials. One again wants to compute the rank of M over the rational function field F(x1,x2,...,xn). This can be used to compute the transcendence degree of any set of constant degree polynomials by using the Jacobian criterion. We describe a deterministic PTAS for the rank of M (when the entries of M are constant degree polynomials). This naturally generalizes the results of BJP17.

This is based on joint work with Vishwas Bhargava (Rutgers University), Markus Bläser (Saarland University) and Anurag Pandey (Max-Planck-Institut für Informatik).

[BJP17] : Markus Bläser, Gorav Jindal, and Anurag Pandey. Greedy strikes again: A deterministic PTAS for commutative rank of matrix spaces. In Proc. 32nd IEEE Conf. on Computational Complexity (CCC'17), volume 79 of LIPIcs, pages 33:1-33:16. IEEE Comp. Soc. Press, 2017.

Name(s):Gorav Jindal
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created:Gorav Jindal, 06/02/2018 08:22 PM Last modified:Uwe Brahm/MPII/DE, 06/11/2018 04:01 AM
  • Gorav Jindal, 06/06/2018 04:04 AM
  • Gorav Jindal, 06/02/2018 08:23 PM
  • Gorav Jindal, 06/02/2018 08:22 PM -- Created document.