

Miniworkshop on Arithmetic Circuit ComplexityMiniworkshop on Arithmetic Circuit Complexity (ENS Lyon, March 5, 2014). Postworkshop update: the slides of Neeraj Kayal's tutorial are online. Final schedule at the bottom of this page. Conference rooms: tutorial, lunch and coffee breaks in "amphi Mérieux". Contributed talks in "amphi B", on the 3rd floor of the main building. Arithmetic circuits provide a simple and natural model for computing polynomials. Two of the main open problems in this field are:
While these outstanding problems remain open, significant progress has been made in the last few years. We hope to share these exciting developments with a wide audience. In order to make the workshop easily accessible to nonexperts, we will begin the day with the traditional 3hour STACS tutorial. This year’s topic is arithmetic circuit complexity, and the tutorial will be delivered by Neeraj Kayal (Microsoft Research India). The tutorial starts at 10am. We will continue with contributed talks. If you would like to contribute, please get in touch with Pascal Koiran.
This workshop is supported by CompA, a research project funded by the Agence Nationale de la Recherche (ANR). Tentative schedule:
Suryajith Chillara: On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields Hervé Fournier: Lower bounds for depth 4 formulas computing iterated matrix multiplication
Youming Qiao: On symbolic determinant identity test problem. Miklos Santha: Hidden symmetry subgroups and hidden polynomials.
