COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Bounded degree and planar spectra

## Bounded degree and planar spectraAdd to your list(s) Download to your calendar using vCal - Kopczynski, E (Uniwersytet Warszawski)
- Tuesday 27 March 2012, 15:00-15:30
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact Mustapha Amrani. Semantics and Syntax: A Legacy of Alan Turing There are many problems in finite model theory about which we know a lot in the unrestricted classes, but which are still not thoroughly researched in the case where we restrict the class of considered models (for example, in terms of properties of their Gaifman graphs). In this talk 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 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). Restricting the class of models we can get, for example, bounded degree spectra (S is a bounded degree spectrum of phi iff phi has a bounded degree model of size n), weak planar spectra (S is a bounded 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). We provide the complexity theoretic characterizations for these cases, similar to the one above. In case of bounded degree spectra, there is a very small (polylogarythmic) gap between our lower and upper bound. In case of weak planar spectra the gap is polynomial. We also provide a weaker complexity theoretic characterization of forced planar spectra. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsVilamovicean Occasional neuroscience talks Winton Discussions## Other talksAdvanced NMR applications Improving on Nature: Biotechnology and the Ethics of Animal Enhancement Roland the Hero TO A TRILLION AND BEYOND: THE FUTURE OF COMPUTING AND THE INTERNET OF THINGS - The IET Cambridge Prestige Lecture RA250 at the Fitz: academicians celebrating 250 years of the Royal Academy Malaria’s Time Keeping |