joint work with Anuj Dawar

Speaker(s)

Eryk Kopczyński

Affiliation

Uniwersytet Warszawski

Date

Nov. 9, 2011, 2:15 p.m.

Room

room 5870

Title in Polish

Bounded degree and planar spectra

Seminar

Seminar Automata Theory

---

There are many problems about which we know a lot in the unrestricted
classes, but are still not researched thoroughly in the restricted case.
One of them was the problem of spectra of formulae. A set of integers S
is a spectrum of phi if n \in S iff phi has a model of size n. It is well
known that S is a spectrum of some formula iff the problem of deciding
whether n \in S is in NP when n is given in unary (equivalently, in NE
when n is given in binary). What happens if we restrict our models to
only bounded degree graphs, or only planar graphs?

We provide complexity theoretic characterizations of sets which are
bounded degree and planar spectra of formulae. In case of bounded degree,
there is a very small (polylogarythmic) gap between our lower and upper
bound. In case of planar spectra (where the formula is not required to
check planarity) the gap is polynomial. We also provide a weaker
complexity theoretic characterization of spectra of formulae which force
planarity.

 

---