7
$\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 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?

Improve this question
$\endgroup$
1
  • 3
    $\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, 2018 at 13:39

4 Answers 4

Reset to default
4
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks but already checked these materials before,not the geometric one though. $\endgroup$
    – ViX28
    Jun 19, 2018 at 12:33
4
$\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.

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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