Speaker: Kazuhisa Seto (The University of Electro-Communications)
Title: An Introduction to Circuit Complexity and Satisfiability Algorithms on Formulas
Time: 1:30pm -, November 9
Place: Room E1011, W8 building, Tokyo Institute of Technology
Abstract:
In this talk, we give a basic introduction to circuit complexity and
satisfiability algorithms on formulas. At first, we show Subbotovskaya's
technique for proving the lower bound of parity function on formulas.
Next, we introduce Santhanam's satisfiability algorithm for de morgan
formulas by using Subbotovskaya's technique. Finally, we give our
satisifiablity algorithm for formulas over the full binary basis by
extension of Santhanam's algorithm.