|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
Event Organizer: David Fernandez Breton email@example.com