Arithmetic Circuit Complexity

• Instructors: Pascal Koiran, Natacha Portier

• Prerequisites: No specialized knowedge is required, however basic notions in algorithms, complexity theory, linear algebra and discrete probability will help.

• Objective: In arithmetic circuit complexity we evaluate the cost of an algorithm by the number of arithmetic operations (additions and multiplications) performed on inputs of a given size. Many classical algorithms, e.g., for matrix multiplication or polynomial multiplication, naturally fit in this model. Moreover, it should be easier to prove lower bounds for that model as it is more restricted than the standard boolean model (algorithms do not have access to the indivual digits of inputs). One central problem in this area is to prove a super-polynomial lower bound for an  “explicit” polynomial such as for instance the permanent polynomial. While this problem is still open, some significant progress has been achieved in the last few years. We will cover some classical results in this area and some of the recent developments.

• Course outline:
  
  1) Upper bounds: structural properties of arithmetic circuits
  
  We will examine some of the main classes of arithmetic circuits and their relationships. One recurring theme is depth reduction (or “parallelization”) of arithmetic circuits. This is a classical topic, but some surprising results were achieved recently. For instance, it was shown that any arithmetic circuit can be transformed into an equivalent circuit of depth 4 (and sometimes just 3!) without blowing up its size too much.
  
  2) Lower bounds
  
  We will review some classical lower bound methods such as Nisan and Wigderson’s method of partial derivatives, and recent developments such as the method of shifted partial derivatives (Neeraj Kayal). The latter is especially well suited to depth 4 circuits and comes tantalizingly close to proving the much-coveted super-polynomial lower bound for general arithmetic circuits. If time allows, we may also cover some booelan circuit lower bounds.
  
  3) Polynomial identity testing
  
  Polynomial identity testing (PIT) is the following problem: given a polynomial P in a “compact representation” (for instance, represented by an arithmetic circuit), decide if P is identically equal to zero. If time allows we will present some simple randomized algorithms for this problem, some combinatorial applications of PIT and the main related open question: is there a deterministic polynomial-time algorithm for PIT? It turns out that derandomizing PIT is essentially equivalent to proving lower bounds for arithmetic circuits.

• Validation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.

• Bibliography:
  
  Books: Some chapters of general texts on complexity theory are relevant for this course, e.g., Introduction to Computational Complexity by Arora and Barak, or Complexité Algorithmique by Sylvain Perifel (in French). Completeness and Reduction in Algebraic Complexity by Peter Bürgisser is an older but more focused reference.

  
  Surveys: Thanks to the rapid development of the field, several recent surveys are available, for instance,

• Arithmetic circuits: A survey of recent results and open questions by Shpilka and Yehudayoff.

• Partial Derivatives in Arithmetic Complexity and Beyond by Chen, Kayal and Wigderson.

• A selection of lower bounds for arithmetic circuits by Kayal and Saptharishi.

•   Recent progress on lower bounds for arithmetic circuits by Shubhangi Saraf.