## Seminars and Colloquia by Series

### Planted Distributions of Random Structures: an Introduction and One Problem Solved

Series
ACO Student Seminar
Time
Friday, February 17, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Will PerkinsGeorgia Tech, School of Mathematics
I will define planted distributions of random structures and give plenty of examples in different contexts: from balls and bins, to random permutations, to random graphs and CSP's. I will give an idea of how they are used and why they are interesting. Then I'll focus on one particular problem: under what conditions can you distinguish a planted distribution from the standard distribution on a random structure and how can you do it?

### An Overview of Lattice Cryptography

Series
ACO Student Seminar
Time
Friday, February 10, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
TBD
Speaker
Christopher PeikertSchool of Computer Science
I'll give a high-level tour of how lattices are providing a powerful new mathematical foundation for cryptography. Lattices provide simple, fast, and highly parallel cryptoschemes that, in contrast with many of today's popular methods (like RSA and elliptic curves), even appear to remain secure against quantum computers. No background in lattices, cryptography, or quantum computers will be necessary -- you only need to know how to add and multiply vectors and matrices.

### On the Integer Width of Lattice Free Sets

Series
ACO Student Seminar
Time
Friday, February 3, 2012 - 13:00 for 1 hour (actually 50 minutes)
Location
Executive classroom, ISyE Main Building
Speaker
Daniel DadushGeorgia Tech, School of Industrial and Systems Engineering
A fundamental result in the geometry of numbers states that any lattice free convex set in R^n has integer width bounded by a function of dimension, i.e. the so called Flatness Theorem for Convex Bodies. This result provides the theoretical basis for the polynomial solvability of Integer Programs with a fixed number of (general) integer variables. In this work, we provide a simplified proof of the Flatness Theorem with tighter constants. Our main technical contribution is a new tight bound on the smoothing parameter of a lattice, a concept developed within lattice based cryptography which enables comparisons between certain discrete distributions over integer points with associated continuous Gaussian distributions. Based on joint work with Kai-Min Chung, Feng Hao Liu, and Christopher Peikert.

### Implicit Hitting Set Problems

Series
ACO Student Seminar
Time
Wednesday, April 28, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
Karthik Chandrasekaran CS ACO
Abstract: A hitting set for a collection of sets T is a set that has a non-empty intersection with eachset in T; the hitting set problem is to find a hitting set of minimum cardinality. Motivated bythe fact that there are instances of the hitting set problem where the number of subsets to behit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting setproblem the collection of sets to be hit is typically too large to list explicitly; instead, an oracleis provided which, given a set H, either determines that H is a hitting set or returns a set inT that H does not hit. I will show a number of examples of classic implicit hitting set problems,and give a generic algorithm for solving such problems exactly in an online model.I will also show how this framework is valuable in developing approximation algorithms by presenting a simple on-line algorithm for the minimum feedback vertex set problem. In particular, our algorithm gives an approximation factor of 1+ 2 log(np)/(np) for the random graph G_{n,p}.Joint work with Richard Karp, Erick Moreno-Centeno (UC, Berkeley) and Santosh Vempala (Georgia Tech).

### BILLIARDS-the most visual dynamical systems (from ORDER to CHAOS and COMPLEXITY)

Series
ACO Student Seminar
Time
Wednesday, April 14, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Prof. Leonid BunimovichSchool of Mathematics, Georgia Tech
Billiards is a dynamical system generated by an uniform motion of a point particle (ray of light, sound, etc.) in a domain with piecewise smooth boundary. Upon reaching the boundary the particle reflected according to the law "the angle of incidence equals the angle of reflection". Billiards appear as natural models in various branches of physics. More recently this type of models were used in oceanography, operations research, computer science, etc. I'll explain on very simple examples what is a regular and what is chaotic dynamics, the mechanisms of chaos and natural measures of complexity in dynamical systems. The talk will be accessible to undergraduates.

### "Local Search" Algorithms for Facility Location Problems

Series
ACO Student Seminar
Time
Wednesday, March 31, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
Anand LouisCS ACO, Georgia Tech
Local search is one of the oldest known optimization techniques. It has been studied extensively by Newton, Euler, etc. It is known that this technique gives the optimum solution if the function being optimized is concave(maximization) or convex (minimization). However, in the general case it may only produce a "locally optimum" solution. We study how to use this technique for a class of facility location problems and give the currently best known approximation guarantees for the problem and a matching "locality gap".

### The reflex algorithm - Convex optimization by random reflection

Series
ACO Student Seminar
Time
Wednesday, March 17, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
Prof. Merrick FurstComputer Science, Georgia Tech
Santosh Vempala and I have been exploring an intriguing newapproach to convex optimization. Intuition about first-order interiorpoint methods tells us that a main impediment to quickly finding aninside track to optimal is that a convex body's boundary can get inone's way in so many directions from so many places. If the surface ofa convex body is made to be perfectly reflecting then from everyinterior vantage point it essentially disappears. Wondering about whatthis might mean for designing a new type of first-order interior pointmethod, a preliminary analysis offers a surprising and suggestiveresult. Scale a convex body a sufficient amount in the direction ofoptimization. Mirror its surface and look directly upwards fromanywhere. Then, in the distance, you will see a point that is as closeas desired to optimal. We wouldn't recommend a direct implementation,since it doesn't work in practice. However, by trial and error we havedeveloped a new algorithm for convex optimization, which we arecalling Reflex. Reflex alternates greedy random reflecting steps, thatcan get stuck in narrow reflecting corridors, with simply-biasedrandom reflecting steps that escape. We have early experimentalexperience using a first implementation of Reflex, implemented inMatlab, solving LP's (can be faster than Matlab's linprog), SDP's(dense with several thousand variables), quadratic cone problems, andsome standard NETLIB problems.

### On-Line Graph Coloring

Series
ACO Student Seminar
Time
Wednesday, February 17, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
William T. TrotterSchool of Mathematics, Georgia Tech
On-line graph coloring has a rich history, with a very large number of elegant results together with a near equal number of unsolved problems. In this talk, we will briefly survey some of the classic results including: performance on k-colorable graphs and \chi-bounded classes. We will conclude with a sketch of some recent and on-going work, focusing on the analysis of First Fit on particular classes of graphs.

### On the Chvatal Closure of a Strictly Convex Body

Series
ACO Student Seminar
Time
Wednesday, February 10, 2010 - 13:30 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
The analysis of Chvatal Gomory (CG) cuts and their associated closure for polyhedra was initiated long ago in the study of integer programming. The classical results of Chvatal (73) and Schrijver (80) show that the Chvatal closure of a rational polyhedron is again itself a rational polyhedron. In this work, we show that for the class of strictly convex bodies the above result still holds, i.e. that the Chvatal closure of a strictly convex body is a rational polytope.This is joint work with Santanu Dey (ISyE) and Juan Pablo Vielma (IBM).

### Polyhedral Stochastic Integer Programming

Series
ACO Student Seminar
Time
Wednesday, September 16, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
ISyE Executive Classroom
Speaker
Shabbir AhmedGeorgia Tech, ISyE
I will describe a simple scheme for generating a valid inequality for a stochastic integer programs from a given valid inequality for its deterministic counterpart. Applications to stochastic lot-sizing problems will be discussed. This is joint work with Yongpei Guan and George Nemhauser and is based on the following two papers (1) Y. Guan, S. Ahmed and G.L. Nemhauser. "Cutting planes for multi-stage stochastic integer programs," Operations Research, vol.57, pp.287-298, 2009 (2) Y. Guan, S. Ahmed and G. L. Nemhauser. "Sequential pairing of mixed integer inequalities," Discrete Optimization, vol.4, pp.21-39, 2007 This is a joint DOS/ACO seminar.