Seminars and Colloquia by Series

Wednesday, August 26, 2009 - 14:00 , Location: SyE Executive Classroom , Ton Dieker , School of Industrial and Systems Engineering, Georgia Tech , Organizer: Annette Rohrs
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.
Wednesday, April 22, 2009 - 13:30 , Location: ISyE Executive Classroom , David Cash , Computer Science, Georgia Tech , Organizer: Annette Rohrs
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.
Wednesday, April 15, 2009 - 13:30 , Location: ISyE Executive Classroom , Luke Postle , School of Mathematics/ACO, Georgia Tech , Organizer: Annette Rohrs
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.
Wednesday, April 8, 2009 - 13:30 , Location: ISyE Executive Classroom , Jean Bellissard , Schools of Mathematics and Physics, Georgia Tech , Organizer: Annette Rohrs
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.
Thursday, April 2, 2009 - 13:30 , Location: Skiles 255 , Alexandra Kolla , UC Berkeley , Organizer: Annette Rohrs
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.
Wednesday, March 25, 2009 - 13:30 , Location: ISyE Executive Classroom , Dana Randall , Computer Science, Georgia Tech , Organizer: Annette Rohrs
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!
Wednesday, March 4, 2009 - 13:30 , Location: ISyE Executive Classroom , Shiva Kintali , CS, Georgia Tech , Organizer: Annette Rohrs
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.
Wednesday, February 25, 2009 - 13:30 , Location: Skiles 269 , Daniel Dadush , ISyE, Georgia Tech , Organizer: Annette Rohrs
In this talk, I will introduce the class of logconcave and s-concave functions, illustrate their properties, and explain their connections to convex geometry. I will present a simple and unified approach for proving probabilistic inequalities for logconcave and s-concave densities on the real line. Lastly I will use these techniques to prove two important theorems in convex geometry: Grunbaum's theorem, every halfspace cut through the centroid of a convex body contains at least a 1/e volume fraction of the body, and the Milman-Pajor inequality, a convex body in R^n is sandwiched between its inertial ellipsoid and a factor n scaling of it. Joint work with Santosh Vempala.
Wednesday, February 18, 2009 - 13:30 , Location: ISyE Executive Classroom , Linji Yang , CS, Georgia Tech , Organizer: Annette Rohrs
In this talk I will give an introduction of the Markov Chain Monte Carlo Method, which uses markov chains to sample interesting combinatorial objects such as proper colorings, independent sets and perfect matchings of a graph. I will introduce methods such as Couplings and Canonical Paths which have been widely used to analyze how many steps Markov Chains needs to go (mixing time) in order to get a sufficiently random combinatorial object. I will also give a brief survey of some recent results in the sampling of colorings.
Wednesday, February 4, 2009 - 13:30 , Location: ISyE Executive Classroom , Richard Lipton , College Computing, Georgia Tech , Organizer: Annette Rohrs
Shrouded in mystery and kept hidden for decades, Richard Lipton's vault of open problems will be revealed...