[Colloquium] Talk by Ramamohan Paturi, UCSD on June 3, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Thursday, June 3, 2010
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:		Ramamohan Paturi

From:		University of California, San Diego

Web:		http://www.jacobsschool.ucsd.edu/faculty/faculty_bios/findprofile.pl?fmp_recid=118
  
Title: On the Complexity of Circuit Satisfiability

Abstract: In this paper, we are concerned with the exponential complexity of the Circuit Satisfiability (CktSat) problem. Our main technique is a a suc- cess probability amplification technique, called the Exponential Amplifica- tion Lemma, which shows that for any f(n,m)-size bounded probabilistic circuit family A that decides CktSat with success probability at least 2−αn for α < 1 on inputs which are circuits of size m with n variables, there is another probabilistic circuit family B that decides CktSat with size roughly f(αn,f(n,m)) and success probability about 2−α2n > 2−αn. In contrast, the standard method for boosting success probability by re- peated trials will improve it to (1−(1−2−αn)t) (≈ t2−αn for t = O(2αn)) using circuits of size about tf(n,m). 
Using this lemma, we derive tight bounds on the exponent of the success probability for deciding the CktSat problem in a variety of prob- abilistic computational models under complexity assumptions. For exam- ple, we show that the success probability cannot be better than 2−n+o(n) for deciding CktSat by probabilistic polynomial size circuits unless CktSat (thereby all of NP) for polynomial size instances can be decided by 2nμ size deterministic circuits for some μ < 1, which is considered an unlikely event. As another example, we show that probabilistic quasilinear size circuits cannot achieve success probability better than 2−n+o(n) unless CktSat (as well as NP) has O(mO(lg lg m)) size deterministic circuits, which is very close to the statement NP ⊆ P/poly, an unlikely scenario.

Jointly with Pavel Pudl ́ak, Institute of Mathematics, Academy of Sciences of the Czech Republic.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100519/ed97baea/attachment.htm