Georgia Institute of Technology College of Sciences

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.

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.

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.

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!