CS 642: Circuit Complexity Theory
Announcements:
Endsem is online!
Midsem is online!
Reading material:
Division and other related problems
in one of the intial works.
Determinant
algorithm by Mahajan and Vinay.
P-uniform NC
thesis of Eric Allender.
logspace-uniform division algorithm
by Davida, Litow and Xu.
Dlogtime-uniform division algorithm
by William Hesse.
Some L-complete Problems
. This has links to several other interesting papers too.
Natural Proofs
by Razborov and Rudich.
Hardness versus Randomness
by Nisan and Wigderson.