Versions Compared


  • This line was added.
  • This line was removed.
  • Formatting was changed.


Abstract: In this talk I will give a brief introduction to and overview of descriptive complexity. Furthermore, descriptive complexity results in circuit complexity are presented and discussed, with some special focus on the characterization of the class of functions computable by constant-depth polynomial size arithmetic circuits (with Boolean inputs) and an attempt to connect this characterization to a known characterization of the class #P. Finally, some work in progress is presented: Many important classes from circuit complexity can be characterized with first-order logic extended by a certain kind of recursive predicate definition.

back to seminar page