# Reference request: Arithmetic circuit complexity

I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/video) for a gentle introduction? I found these two given below.

Determinant versus permanent by Manindra Agarwal https://pdfs.semanticscholar.org/6a05/a4fe63e409ba040b890bbf5da0f3b1ca7085.pdf

Arithmetic circuits by Amir Shpilka

https://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

Is there any other material which can be more appropriate for a beginner?

• Vollmer's book has a section on arithmetic circuit complexity; that's fairly light. Heribert Vollmer, "Introduction to Circuit Complexity". – Michaël Cadilhac Jun 19 '18 at 13:39

This depends on what you want to do. For more structural questions there is a relatively recent survey by Meena Mahajan:

Meena Mahajan: Algebraic Complexity Classes.

There is also the book by Bürgisser:

Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory.

For Geometric Complexity Theory, you might try the theses of Joshua Grochow or Christian Ikenmeyer. I think both of them have introduction into the field, but I must admit that I have read neither of them.

• Thanks but already checked these materials before,not the geometric one though. – ViX28 Jun 19 '18 at 12:33

In addition to the references already mentioned, you could check out

Xi Chen, Neeraj Kayal and Avi Wigderson (2011), Partial Derivatives in Arithmetic Complexity and Beyond, Foundations and Trends® in Theoretical Computer Science: Vol. 6: No. 1–2, pp 1-138. (Freely available author's version)

Although the title makes it sound fairly specific, it's a pretty decent introduction.

I only know of one textbook devoted to this topic (Burgisser-Clausen-Shokrollahi "Algebraic Complexity Theory"), but it may not be the easiest introduction for beginners.

Another good source that I am surprised hasn't been mentioned yet is the survey by Ramprasad Saptharishi.

This is course on Arithmetic Circuit Complexity, offered by Prof Nitin Saxena (the S of AKS primality test). The syllabus and pre-requisites can be found here.