Seminar by Nitin Saxena
The rank and file of circuits
Nitin Saxena
Hausdorff centre, Bonn University
Date: Thursday, October 11th, 2012
Time: 5PM
Venue: CS101.Abstract:
A long term goal in complexity theory is to prove lower bounds - natural problems like satisfiability or permanent are 'hard'. The convenient way to study this is via arithmetic circuits. The lower bound questions here allow a flip to upper bound ones; the key being that of designing hitting-sets (or blackbox identity testing). Such designs are known only for restricted circuit models; the restriction being on the depth and shape. The proofs almost always also give a notion of rank for the corresponding model.
In this talk we will briefly define these circuits and the associated notions of rank. The rank notions are algebraic in nature, and generalize the basic 'vector space rank' to higher algebraic concepts.