Seminar Event Detail


Date:  Thursday, November 02, 2017
Location:  3096 East Hall (4:00 PM to 5:30 PM)

Title:  Presburger Arithmetic and its computational complexity

Abstract:   Presburger Arithmetic (PA) is a classical topic in logic, with numerous connection to computer science and combinatorics. Formally, is the first order structure on the integers with only additions and inequalities. Despite its long history, many problems in PA have remained unsolved until recently. We study the complexity of decision problems in PA, and classify them according to hierarchy levels. Along the way, connections to Integer Programming and Optimization will be explained. The talk will be self contained and assumes no prior knowledge of the subject.


Speaker:  Danny Nguyen
Institution:  UCLA

Event Organizer:   David Fernandez Breton


Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact

Back to previous page
Back to UM Math seminars/events page.