Room P3.10, Mathematics Building

Juha Kontine, U Helsinki, Finland

Regular representations of uniform $TC^0$

The complexity class DLOGTIME-uniform $\operatorname{AC}^0$ is known to be a modest subclass of DLOGTIME-uniform $\operatorname{TC}^0$. The weakness of $\operatorname{AC}^0$ is due, put in logical terms, to the fact that the logics corresponding to $\operatorname{AC}^0$ do not have the relativization property and hence they are not regular. This weakness of $\operatorname{AC}^0$ has been elaborated in the line of research on the Crane Beach Conjecture. In this talk we show that DLOGTIME-uniform $\operatorname{TC}^0$ can be logically characterized in terms of quantifier logics with cardinality quantifiers $\operatorname{FO}_{\lt}(C_S)$, where $S$ is the range of some polynomial of degree at least two. Then we adapt the key properties of abstract logics to accomodate built-in relations and define the regular interior $R-\operatorname{int}(L)$ and regular closure $R-\operatorname{cl}(L)$, of a logic $L$. Finally we show that the Crane Beach Conjecture can be interpreted as a statement concerning the regular interior of a logic and that the regular closure of $\operatorname{AC}^0$ is $\operatorname{TC}^0$. Joint work with Lauri Hella and Kerkko Luosto.