Date: Dec. 12 (Fri), 2014
Time: 11:00 - 13:00
Place: CELC seminar room (CIC 4F)

Speaker: Suguru Tamaki(A02, Kyoto Univ.)
Title: SAT Algorithms and Average Sensitivity
Abstract:
In this talk, I will discuss a connection between satisfiability
algorithm and average sensitivity. For some circuit class C such as
CNF, AC0 and De Morgan formula, there exists a satisfiability
algorithm whose running time is of the form 2^{(1-1/as(C))n}, where
as(C) denotes the average sensitivity of C. Is this connection
coincidence? Does it hold for other circuit classes? I will explain
why we have such connections for CNF, AC0 and De Morgan formula and
would like to encourage people to seek more such connections.