Invited Talk by Anuj Dawar (University of Cambridge): Notions of Width: Variables, Pebbles and Supports

Given a formula, what is the smallest number of variables with which it can be equivalently written? What seems like an abstruse question in syntactic manipulation turns out to have significance in a variety of areas of theoretical computer science. The number of variables in a formula emerges as an important measure related to notions of width arising in fields as varied as database theory; combinatorics and graph theory; and permutation groups. In this talk, I will explore how these notions are related to each other and the exploration will take us through a diverse landscape of topics, from comonads to lower bounds in circuit complexity.