Mixing finite and infinite structure

Add to your list(s) Download to your calendar using vCal

• Michael Benedikt, University of Oxford
• Monday 10 October 2022, 16:00-17:00
• SS03.

If you have a question about this talk, please contact Jamie Vicary.

A basic distinction between logic in databases and “vanilla mathematical logic” is that in the former quantifiers range over the objects that are stored in finite relations — stuff in the database; while in the latter we quantify over the domain of the model, which can be infinite—all strings, all real numbers, all integers, etc. Once upon a time, researchers studied what happens when you mix these two kinds of quantification within the same logic. In the resulting formalism, “embedded finite model theory”, you can, for example, write a query asking whether there is a vector of real numbers which satisfy certain inequalities with respect to all rows in a database table.

The talk will revisit embedded finite model theory, arguing that it’s relevant to a number of recent develpments in data management, such as performing linear algebra and ML tasks within a DBMS . The talk focus will be on new connections to theoretical CS: spectrum problems, bounds in decision procedures, and Ramsey theory.

There will be some classical model theory in the lecture, but it should be accessible to a theory-leaning CS audience. The talk includes joint work with Ehud Hrushovski and joint work with Anthony Lin.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• SS03
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.