max planck institut
informatik

# 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)
Title: A deterministic PTAS for the transcendence degree of constant degree polynomials Gorav Jindal Max-Planck-Institut für Informatik - D1 AG1 Mittagsseminar (own work) D1, RG1, SWS, MMCIWe use this to send out email in the morning. AG Audience English
Date: Tuesday, 10 July 2018 13:00 45 Minutes Saarbrücken E1 4 024
 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