|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 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.
Speaker: Danny Nguyen
Event Organizer: David Fernandez Breton firstname.lastname@example.org