2
$\begingroup$

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 thse 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?

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

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.

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

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.