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

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.

Series: ACO Student Seminar

In the first part of the talk, I am going to give an introduction and overview of linear and semidefinite programming hierarchies. I will mostly review known integrality gaps for such programs and try to give an intuition of why we currently lack strong techniques for designing rounding algorithms. In the second part of the talk I will focus on the stronger SDP Lasserre hierarchy. In contrast with the previous LP and SDP hierarchies, very few examples of integrality gap instances are known to date. I will present a recent technique for designing such instances and discuss open problems in the area.

Series: ACO Student Seminar

We will survey some old, some new, and some open problems in the area of efficient sampling. We will focus on sampling combinatorial structures (such as perfect matchings and independent sets) on regular lattices. These problems arise in statistical physics, where sampling objects on lattices can be used to determine many thermodynamic properties of simple physical systems. For example, perfect matchings on the Cartesian lattice, more commonly referred to as domino tilings of the chessboard, correspond to systems of diatomic molecules. But most importantly they are just cool problems with some beautiful solutions and a surprising number of unsolved challenges!

Series: ACO Student Seminar

Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking stable solutions. However, the complexity of the computational version of Scarf's lemma (Scarf) remained open. In this talk, I will prove that Scarf is complete for the complexity class PPAD. This shows that Scarf is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for Scarf unless PPAD \subseteq P. I will also talk about fractional stable paths problem, finding fractional kernels in digraphs, finding fractional stable matching in hypergraphic preference systems and finding core in an N-person balanced game with non-transferable utilities. I will show the connection between these problems through Scarf's lemma and address the complexity of these problems.