Seminar on Thursday morning, February 21, 2013

236 Chemistry Building East, University of Tokyo[東京大学本郷キャンパス理学部化学東館236室]
Enter the Science Building 7 (理学部七号館), go one floor up and then go through the connecting corridor.

Threshold Circuits, Communication Complexity, and Polynomial Threshold Functions

Kristoffer Arnsfelt Hansen (Aarhus University)

In this talk I address the circuit lower bound frontier in the setting of Boolean threshold circuits. It is a major and long-standing open problem to show explicit super-polynomial lower bounds already for weighted depth 2 threshold circuits. I will first survey the history of lower bounds for various classes of threshold circuits. The strongest such lower bounds were (either explicitly or implicitly) obtained using various models of communication complexity and I will cover these in detail. Next I will show that communication complexity may also be the correct way to approach the problem of proving lower bounds for depth 2 weighted threshold circuits. This involves use of so-called exact threshold functions as well the use of the familiar polynomial threshold functions in an unusual setting.

Where First-Order and Monadic Second-Order Logic Coincide

Michael Elberfeld (International Computer Science Institute)

We study on which classes of graphs first-order logic (FO) and monadic second-order logic (MSO) have the same expressive power. We show that for all classes C of graphs that are closed under taking subgraphs, FO and MSO have the same expressive power on C if, and only if, C has bounded tree depth. Tree depth is a graph invariant that measures the similarity of a graph to a star in a similar way that tree width measures the similarity of a graph to a tree. For classes just closed under taking induced subgraphs, we show an analogous result for guarded second-order logic (GSO), the variant of MSO that not only allows quantification over vertex sets but also over edge sets. A key tool in our proof is a Feferman-Vaught-type theorem that is constructive and still works for unbounded partitions.

This is joint work with Martin Grohe and Till Tantau.

Seminar in the afternoon