You are cordially invited to our next Monday Lecture &
Colloquium on June 28 th. Time is back to normal. Monday's Lecture & Colloquium will be online via Zoom, as used to. Invitation link: Zoom - Invitation Time: Monday, June 28th - 14:15 h Lecture: Xavier Allamigeon (Inria and Ecole Polytechnique) Title: Formalizing the theory of polyhedra in a proof assistant Abstract:In this talk, I will present the project Coq-Polyhedra that
aims at formalizing the theory of polyhedra as well as
polyhedral computations in the proof assistant Coq. Coffee Break! Time: Monday, June 28th - 16:00 h s.t. Colloquium: Gorav Jindal (Technische Universität Berlin) Title: Arithmetic Circuit Complexity of Division and Truncation Abstract:Given n-variate polynomials f,g,h such that f=g/h, where both g and h are computable by arithmetic circuits of size s, we show that f can be computed by a circuit of size poly(s, deg(h)). This solves a special case of division elimination for high-degree circuits (Kaltofen’87 & WACT’16). This result is an exponential improvement over Strassen’s classic result (Strassen’73) when deg(h) is poly(s) and deg(f) is exp(s), since the latter gives an upper bound of poly(s, deg(f)). The second part of this work deals with the complexity of computing the truncations of uni-variate polynomials or power series. We first show that the truncations of rational functions are easy to compute. We also prove that the truncations of even very simple algebraic functions are hard to compute,unless integer factoring is easy. This is a joint work with Pranjal Dutta, Anurag Pandey and Amit Sinhababu. A pre-print can be found at https://eccc.weizmann.ac.il/report/2021/072/ . |