MSR/MIT Theory Reading Group

	Hypercontractivity made easy, and sharp threshold theorems : Lecture 2 Tuesday, August 6, 2013 - 3:00pm to 6:00pm This lecture will further develop the randomization/symmetrization technique in the setting of functions on general product probability spaces. Our motivation will be the desire to prove "sharp threshold
	Hypercontractivity made easy, and sharp threshold theorems: Lecture 1 Tuesday, July 30, 2013 - 3:00pm to 6:00pm In this lecture I'll introduce the "Hypercontractivity Theorem" for real-valued functions on the boolean cube, f : {-1,1}^n -> R and explain how you can view it as either: . a natural strengthening of Holder's inequality;
	Understanding Incentives: Reducing Mechanism- to Algorithm-Design Friday, July 12, 2013 - 12:45pm to 3:45pm In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output.
	Green-Tao, Szemerédi, and transference Friday, June 28, 2013 - 12:45pm to 3:30pm The celebrated Green-Tao theorem states that the primes contain arbitrarily long arithmetic progressions. In this talk, I will give some background and explain the ideas of proof, including some recent simplifications due to Conlon, Fox, and myself.
	Association Schemes, Non-Commutative Polynomials and Lasserre Lower Bounds for Planted Clique Friday, June 21, 2013 - 12:45pm to 3:45pm Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design.
	Hypercontractivity of spherical averages in Hamming space Friday, June 14, 2013 - 12:45pm to 3:45pm Certain conditional expectation operators (stochastic matrices) have the property, called hypercontractivity (HC), that their Lp->Lq norm is 1 for p < q.
	Indistinguishability Obfuscation and Functional Encryption for all circuits Friday, July 26, 2013 - 12:45pm to 3:45pm The goal of secure program obfuscation is to make a program ``unintelligible'' while preserving functionality. Unfortunately, 12 years ago, Barak et al. showed that the most natural simulation-based formulation of this problem is impossible to achieve. However, Barak et al.
	Finding Needles in Exponential Haystacks Friday, July 19, 2013 - 12:45pm to 3:45pm http://people.csail.mit.edu/madhu/reading-group/
	Unique games, the Lasserre hierarchy and monogamy of entanglement Friday, May 24, 2013 - 12:45pm to 3:45pm In this talk, I'll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem.
	Sanjeev Khanna - TBD Friday, May 17, 2013 - 12:45pm to 3:45pm http://people.csail.mit.edu/madhu/reading-group/

Pages