Campus Event Calendar: Gorav Jindal (07/10/2018 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

A deterministic PTAS for the transcendence degree of constant degree polynomials

Gorav Jindal

Max-Planck-Institut für Informatik - D1

AG1 Mittagsseminar (own work)

AG 1, RG1, SWS, MMCI

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Tuesday, 10 July 2018

13:00

45 Minutes

Warning: Date has changed!

E1 4

024

Saarbrücken

Abstract

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.

Contact

Gorav Jindal

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Gorav Jindal, 06/26/2018 12:35
Gorav Jindal, 06/19/2018 11:51
Gorav Jindal, 06/06/2018 04:04
Gorav Jindal, 06/02/2018 20:23
Gorav Jindal, 06/02/2018 20:22 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis