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

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

Shrouded in mystery and kept hidden for decades, Richard Lipton's vault of open problems will be revealed...