max planck institut

informatik

informatik

<< 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 |
---|---|

Speaker: | Gorav Jindal |

coming from: | Max-Planck-Institut für Informatik - D1 |

Speakers Bio: | |

Event Type: | AG1 Mittagsseminar (own work) |

Visibility: | D1, RG1, SWS, MMCI We use this to send out email in the morning. |

Level: | AG Audience |

Language: | English |

Date: | Tuesday, 10 July 2018 |
---|---|

Time: | 13:00 |

Duration: | 45 Minutes |

Location: | Saarbrücken |

Building: | E1 4 |

Room: | 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. |

Name(s): | Gorav Jindal |
---|

Video Broadcast: | No | To Location: |
---|

Note: | |
---|---|

Attachments, File(s): |

Created: | Gorav Jindal, 06/02/2018 08:22 PM |

Last modified: | Uwe Brahm/MPII/DE, 07/10/2018 07:01 AM |

- Gorav Jindal, 06/26/2018 12:35 PM
- Gorav Jindal, 06/19/2018 11:51 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.