- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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).

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

In 1969, Gomory introduced the master group polyhedron for pure integer programs and derives the mixed integer cut (MIC) as a facet of a special family of these polyhedra. We study the MIC in this framework, characterizing both its facets and extreme points; next, we extend our results under mappings between group polyhedra; and finally, we conclude with related open problems. No prior knowledge of algebra or the group relaxation is assumed. Terminology will be introduced as needed. Joint work with Ellis Johnson.

Series: ACO Student Seminar

Sum-Product inequalities originated in the early 80's
with the work of Erdos and Szemeredi, who showed that there exists
a constant c such that if A is a set of n integers, n sufficiently
large, then either the sumset A+A = {a+b : a,b in A} or the product
set A.A = {ab : a,b in A}, must exceed n^(1+c) in size. Since that
time the subject has exploded with a vast number of generalizations
and extensions of the basic result, which has led to many
very interesting unsolved problems (that would make great thesis
topics). In this talk I will survey some of the developments in this
fast-growing area.

Series: ACO Student Seminar

A central question in the theory of card shuffling is how quickly a deck of
cards becomes 'well-shuffled' given a shuffling rule. In this talk, I will
discuss a probabilistic card shuffling model known as the 'interchange
process'. A
conjecture from 1992 about this model has recently been resolved
and I will address how my work has been involved with this conjecture. I
will also discuss other card shuffling models.

Series: ACO Student Seminar

We construct efficient and natural encryption schemes that remain
secure (in the standard model) even when used to encrypt messages that
may depend upon their secret keys. Our schemes are based on
well-studied "noisy learning" problems. In particular, we design
1) A symmetric-key cryptosystem based on the "learning parity with
noise" (LPN) problem, and
2) A public-key cryptosystem based on the "learning with errors"
(LWE) problem, a generalization of LPN that is at least as hard as
certain worst-case lattice problems (Regev, STOC 2005; Peikert, STOC
2009).
Remarkably, our constructions are close (but non-trivial) relatives of
prior schemes based on the same assumptions --- which were proved
secure only in the usual key-independent sense --- and are nearly as
efficient. For example, our most efficient public-key scheme encrypts
and decrypts in amortized O-tilde(n) time per message bit, and has
only a constant ciphertext expansion factor. This stands in contrast
to the only other known standard-model schemes with provable security
for key-dependent messages (Boneh et al., CRYPTO 2008), which incur a
significant extra cost over other semantically secure schemes based on
the same assumption. Our constructions and security proofs are simple
and quite natural, and use new techniques that may be of independent
interest.
This is joint work with Chris Peikert and Amit Sahai.

Series: ACO Student Seminar

Grotzsch's Theorem states that every triangle-free planar graph is
3-colorable.
Thomassen conjectured that every triangle-free planar graph has
exponentially many distinct 3-colorings. He proved that it has at least
2^{n^{1/12}/20000} distinct 3-colorings where n is the number of vertices.
We show that it has at least 2^{\sqrt{n/600}} distinct 3-colorings.
Joint work with Arash Asadi and Robin Thomas.

Series: ACO Student Seminar

This short introduction to the principles of Quantum Computation will give hints upon why quantum computers, if they are built, will revolutionize the realm of information technology. If Physicists and Engineers can produce such machines, all the security protocoles used today will become obsolete and complex computations called NP will become easy. From the example of trapped ion computation, the talk will explain how Quantum Mechanics helps encoding information. The notion of quantum gate, the elementary brick of computation, will be introduced and some example of elementary program will be described. Comments about the Fourier transformalgorithm, its potential speed and its application to code breaking will end this talk.