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
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:
Note that ex-directory lists are not shown. |
Other listsVilamovicean Occasional neuroscience talks Winton DiscussionsOther talksAutumn Cactus & Succulent Show RA250 at the Fitz: academicians celebrating 250 years of the Royal Academy TO A TRILLION AND BEYOND: THE FUTURE OF COMPUTING AND THE INTERNET OF THINGS - The IET Cambridge Prestige Lecture Roland the Hero Improving on Nature: Biotechnology and the Ethics of Animal Enhancement Advanced NMR applications Computing knot Floer homology Immigration and Freedom Protein Folding, Evolution and Interactions Symposium 70th Anniversary Celebration The Rise of Augmented Intelligence in Edge Networks Malaria’s Time Keeping |