University of Birmingham > Talks@bham > Theoretical computer science seminar > On the complexity of linear arithmetic theories over the integers

## On the complexity of linear arithmetic theories over the integersAdd to your list(s) Download to your calendar using vCal - Dmitry Chistikov, University of Warwick
- Friday 17 January 2020, 11:00-12:00
- Computer Science, The Sloman Lounge (UG).
If you have a question about this talk, please contact Rajesh Chitnis. Given a system of linear Diophantine equations, how difficult is it to determine whether it has a solution? What changes if equations are replaced with inequalities? If some of the variables are quantified universally? These and similar questions relate to the computational complexity of deciding the truth value of statements in various logics. This includes in particular Presburger arithmetic, the first-order logic over the integers with addition and order. In this talk, I will survey constructions and ideas that underlie known answers to these questions, from classical results to recent developments, and open problems. This will include the geometry of integer linear programming, how it interacts with quantifiers, and ultimately periodic sets of integer points in several dimensions (semi-linear sets). We will also discuss “sources of hardness”, such as representations of big numbers with small logical formulae. This talk is part of the Theoretical computer science seminar series. ## This talk is included in these lists:- Computer Science Departmental Series
- Computer Science Distinguished Seminars
- Computer Science, The Sloman Lounge (UG)
- Theoretical computer science seminar
- computer sience
Note that ex-directory lists are not shown. |
## Other listsCargo Topology and Dynamics Seminar Type the title of a new list here## Other talksHodge Theory: Connecting Algebra and Analysis Modelling uncertainty in image analysis. Perfect matchings in random sparsifications of Dirac hypergraphs Sensing and metrology activities at NPL, India Provably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems When less is more - reduced physics simulations of the solar wind |