Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.
Is there a set of lecture notes, books, papers and surveys for students who have read standard textbook about theory like Sipser's book or the Arora-Barak's complexity textbook.
The set of references will includes recent advanced results.
The massive tome of Burgisser-Clausen-Shokrollahi is the standard reference for algebraic complexity theory (and I'm not really sure there are others from the complexity point of view, though there are definitely others about algebraic algorithms), but doesn't do much of PIT.
The surveys of Chen-Kayal-Wigderson (freely available from Wigderon's webpage) and Shpilka-Yehudayoff (freely available from Shpilka's webpage) cover much more of the recent results on lower bounds and derandomizing PIT for small algebraic circuit classes.
Agrawal's 2006 ICM address gives a good overview of the permanent versus determinant problem, and despite being 8 years old is still fairly up to date. (I think the only more recent lower bound is Landsberg-Manivel-Ressayre, which gets the same lower bound but for approximative determinantal complexity instead of just determinantal complexity.)
