BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Bounded degree and planar spectra - Kopczynski\, E (Uniwersytet Wa
 rszawski)
DTSTART:20120327T140000Z
DTEND:20120327T143000Z
UID:TALK37188@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:There are many problems in finite model theory about which we 
 know a lot in the unrestricted classes\, but which are still not thoroughl
 y researched in the case where we restrict the class of considered models 
 (for example\, in terms of properties of their Gaifman graphs). In this ta
 lk we consider 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 know
 n 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).\n\nRestricting the class of models we can get\, for exam
 ple\, bounded degree spectra (S is a bounded degree spectrum of phi iff ph
 i has a bounded degree model of size n)\, weak planar spectra (S is a boun
 ded degree spectrum of phi iff phi has a planar model of size n)\, and for
 ced planar spectra (S is a spectrum of phi which admits only planar models
 ).\n\nWe provide the complexity theoretic characterizations for these case
 s\, similar to the one above. In case of bounded degree spectra\, there is
  a very small\n(polylogarythmic) gap between our lower and upper bound. In
  case of weak planar spectra the gap is polynomial. We also provide a weak
 er complexity theoretic characterization of forced planar spectra.\n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR