Miniworkshop on Arithmetic Circuit Complexity

Miniworkshop on Arithmetic Circuit Complexity (ENS Lyon, March 5, 2014). 

Post-workshop 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:

• The complexity of the permanent polynomial: can it be computed by polynomial-size arithmetic circuits? This problem can be viewed as an algebraic version of P versus NP (or perhaps more accurately, as an algebraic version of NC versus #P).

• Derandomization of Polynomial Identity Testing. There is a simple and well-known randomized algorithm for this problem (evaluate your circuit at random points), and it forms a building block in the design of many other randomized algorithms. This problem is connected to the first one via hardness versus randomness tradeoffs.

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 non-experts, we will begin the day with the traditional 3-hour 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.

Topics of interest for the workshop include:

• Arithmetic circuit models such as: arithmetic formulas, arithmetic branching programs, multilinear circuits, bounded-depth circuits...

• Upper and lower bounds for the permanent, the determinant and other explicit polynomials.

• Polynomial identity testing, hardness versus randomness tradeoffs.

• Related topics, e.g., the complexity of matrix multiplication.

Registration is free but mandatory. You will be able to register on the STACS web site.

This workshop is supported by CompA, a research project funded by the Agence Nationale de la Recherche (ANR).

Tentative schedule:

• 9.30: welcoming of participants.
• 10-11am Tutorial part 1
• Coffee break
• 11.15-12.15 Tutorial part 2
• 12.15-13.15 lunch
• 13.15-14.15 Tutorial part 3
• 14.30 Contributed talks: 

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

• 15.30 Coffee break.
• 15:45 Contributed talks:

 Youming Qiao: On symbolic determinant identity test problem. 

Miklos Santha: Hidden symmetry subgroups and hidden polynomials.