Thursday, November 2, 2017, from 4 to 5:30pm
East Hall, room 3096
Speaker: Danny Nguyen (University of California, Los Angeles)
Title: Presburger Arithmetic and its computational complexity
Presburger Arithmetic (PA) is a classical topic in logic, with numerous connections 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. Joint work with Igor Pak.