Department of

# Mathematics

Seminar Calendar
for Logic Seminar events the next 2 months of Sunday, October 22, 2017.

.
events for the
events containing

More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
    September 2017          October 2017          November 2017
Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
1  2    1  2  3  4  5  6  7             1  2  3  4
3  4  5  6  7  8  9    8  9 10 11 12 13 14    5  6  7  8  9 10 11
10 11 12 13 14 15 16   15 16 17 18 19 20 21   12 13 14 15 16 17 18
17 18 19 20 21 22 23   22 23 24 25 26 27 28   19 20 21 22 23 24 25
24 25 26 27 28 29 30   29 30 31               26 27 28 29 30



Tuesday, October 31, 2017

1:00 pm in 345 Altgeld Hall,Tuesday, October 31, 2017

#### Presburger Arithmetic and its computational complexity

###### Danny Nguyen (UCLA)

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.