[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

REMINDER:

Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar

Tuesday, October 24, 2016
3:00 pm
Ryerson 251

Danny Nguyen
UCLA Math

Tuesday, October 24, 2017
Ryerson 251 @ 3:30pm

Title:  Integer points, generating functions, and computational complexity.

Abstract: 
The structure of integer points in polytopes is of interest both in Combinatorics and Integer Programming. In fixed dimensions, the works of Lenstra (1983) and Barvinok (1993) showed that integer points can be found can counted in polynomial time. This led to a series of subsequent developments, generalizing these results in many directions. An important common generalization asks for satisfiability of formulas in Presburger Arithmetic. We show that there are sharp limits on any positive results in this general setting, even in low dimension. Notably, satisfiability with 3 quantifiers, 10 inequalities in dimension 5 is NP-complete. A parallel picture is drawn with short generating functions, which were introduced by Barvinok to count integer points in polytopes. We show that these seemingly simple objects provide another model for the whole (non-uniform) Polynomial Hierarchy. Whether such functions can encode "non-linear" sets, such as square numbers, efficiently or not is still open. Joint work with Igor Pak.

Host: Prof. Razborov
============

(Refreshments prior to talk in Ry. 251 @ 3pm)

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20171024/c12bfb2b/attachment-0001.html>