BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Bounded degree and planar spectra - Kopczynski\, E
(Uniwersytet Warszawski)
DTSTART;TZID=Europe/London:20120327T150000
DTEND;TZID=Europe/London:20120327T153000
UID:TALK37188AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37188
DESCRIPTION:There are many problems in finite model theory abo
ut which we know a lot in the unrestricted classes
\, but which are still not thoroughly researched i
n the case where we restrict the class of consider
ed models (for example\, in terms of properties of
their Gaifman graphs). In this talk we consider t
he problem of spectra of formulae. A set of intege
rs 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 spec
trum of some formula iff the problem of deciding w
hether n in S is in NP when n is given in unary (e
quivalently\, in NE when n is given in binary).\n\
nRestricting the class of models we can get\, for
example\, bounded degree spectra (S is a bounded d
egree spectrum of phi iff phi has a bounded degree
model of size n)\, weak planar spectra (S is a bo
unded degree spectrum of phi iff phi has a planar
model of size n)\, and forced planar spectra (S is
a spectrum of phi which admits only planar models
).\n\nWe provide the complexity theoretic characte
rizations for these cases\, similar to the one abo
ve. In case of bounded degree spectra\, there is a
very small\n(polylogarythmic) gap between our low
er and upper bound. In case of weak planar spectra
the gap is polynomial. We also provide a weaker c
omplexity theoretic characterization of forced pla
nar spectra.\n\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR