Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminar: Valentine Kabanets

LFCS Seminar: Valentine Kabanets

— filed under:

Lower bounds against weakly uniform circuits

What
  • LFCS Seminar
When Jun 08, 2012
from 02:00 PM to 03:00 PM
Where IF 4.31-33
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 NP-complete problem has a uniform polynomial-time 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 NP-complete problem can be decided by even a nonuniform family of polynomial-size 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 #P-complete 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 constant-depth 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 non-uniformity and uniformity. They showed that Permanent cannot be computed by succinct arithmetic circuits of constant depth (a subclass of Boolean constant-depth 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 polynomial-size 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).
Document Actions