Laboratory of Mathematical Logic at PDMI

Пятница, 5 июля, ауд. 203. Начало в 17:00.

Докладчик: Dieter van Melkebeek (University of Wisconsin).

Тема: Locality from Circuit Lower Bounds.

Abstract

Expressibility and inexpressibility in logics over finite structures plays an important role in various areas of computer science, such as databases, automated verification, and descriptive complexity theory. One potent tool for proving inexpressibility results is the notion of locality. Informally, a logical query is local if it can be answered by only looking at small, localized parts of the input. Once a class of queries is known to be local it is often simple to prove a particular query cannot be expressed in this class by showing that the query is not local. For example, each first-order query over graphs only depends on the neighborhoods of the arguments up to some constant distance. On the other hand, the query checking whether two vertices are connected cannot be answered by considering only the neighborhoods of those two vertices up to a constant distance. These two facts imply that connectivity is not expressible in first-order logic.

In this presentation we show how to use circuit lower bounds to establish upper bounds on the locality of logics. In particular, we consider a logic closely related to the complexity class AC0 of all languages that can be decided by nonuniform families of polynomial-size constant-depth circuits. We exploit the known lower bounds for parity on constant-depth circuits to obtain a tight upper bound for the locality of queries expressible in that logic.

As the topic bridges between "theory A'' and "theory B'', I will try to provide enough background so as to make the presentation accessible to both communities.

Joint work with Matthew Anderson, Nicole Schweikardt, and Luc Segoufin.