Bounded degree and planar spectra

Prelegent(ci)

Eryk Kopczyński

Afiliacja

Uniwersytet Warszawski

Termin

9 listopada 2011 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Anuj Dawar

Seminarium

Seminarium „Teoria automatów”

---

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.

 

---