Title: Succinctness of First-Order Logics

Speaker: Philipp Weis

Abstract:

How large does a logical formula need to be to express a desired
property? And given two different logical formalisms, is one of them
more efficient at expressing desired properties?

While the first of these questions has been a main thread running
through finite model theory, the second question about the
succinctness of logical languages has received relatively little
attention, even though (or maybe because?) it does have close
connections to interesting open questions in complexity theory.

In this talk, we will survey some recent results on the succinctness
of first-order languages, and present a general framework (bulding on
both game theory and communication complexity) to analyse succinctness
questions.