LFCS Seminar: Valentine Kabanets
Lower bounds against weakly uniform circuits
What 


When 
Jun 08, 2012 from 02:00 PM to 03:00 PM 
Where  IF 4.3133 
Add event to calendar 
vCal iCal 
Understanding the power and limitation of efficient algorithms is the major goal of complexity theory, with the P vs. NP problem being the most famous open question in the area. While proving that no NPcomplete problem has a uniform polynomialtime algorithm would suffice for separating P and NP, a considerable amount of effort was put into the more ambitious goal of trying to show that no NPcomplete problem can be decided by even a nonuniform family of polynomialsize Boolean circuits.
However, after more than 20 years of effort, complexity theorists have made little progress along this line. Various natural restrictions have been introduced on circuits, with two important ones: bounded depth and uniformity. Roughly speaking, a circuit family is called uniform if there is an efficient algorithm that can construct any circuit from the family. Allender [All99] showed that Permanent, which is a #Pcomplete problem, cannot be computed by uniform threshold circuits of subsubexponential size and constant depth. Allender's result is still one of the strongest currently known uniform circuit lower bounds, whose proof is relies on the correspondence between uniform constantdepth circuits and alternating Turing machines, as well as on the standard diagonalization technique.
Recently, Jansen and Santhanam [JS11] proposed a natural relaxation of uniformity, termed succinctness, which allows one to interpolate between nonuniformity and uniformity. They showed that Permanent cannot be computed by succinct arithmetic circuits of constant depth (a subclass of Boolean constantdepth threshold circuits). Their proof utilizes a connection between derandomization and circuit lower bounds, and is quite different from the previous arguments a la Allender for uniform circuit lower bounds.
In this work, we improve upon [JS11] by showing that Permanent does not have succinct polynomialsize Boolean threshold circuits of constant depth. In addition to strengthening the main result from [JS11], we also give a simpler proof, which goes along the lines of Allender's uniform circuit lower for Permanent. Our argument is quite general and allows us to extend to the ``succinct'' setting all previously known uniform circuit lower bounds of Allender [All99] and Koiran and Perifel [KP09].
Joint work with Ruiwen Chen (SFU).