MSR/MIT Theory Reading Group

	Udi Weider - TBD Friday, May 10, 2013 - 12:45pm to 3:45pm TBD http://people.csail.mit.edu/madhu/reading-group/
	The Correct Exponent for the Gotsman-Linial Conjecture Friday, May 3, 2013 - 12:45pm to 3:45pm A (degree-d) polynomial threshold function is a function of the form f(x) = sgn(p(x)) for some (degree-d) polynomial d. The noise sensitivity of a boolean function is the probability that a small change in the input will lead to a change in the output.
	Analytical approach to parallel repetition Friday, April 26, 2013 - 12:45pm to 3:45pm We propose an "analytical" framework for studying parallel repetitions of one-round two-prover games. We define a new relaxation of the value of a game, val+, and prove that it is both multiplicative and a good approximation for the true value of the game.
	Constant rate PCPs for circuit-SAT with sublinear query complexity Monday, April 29, 2013 - 4:00pm to 7:00pm The PCP theorem says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP.
	Efficient interactive coding against adversarial noise Friday, April 12, 2013 - 12:45pm to 3:45pm In this talk we will study the problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and
	Low-degree testing over small fields Friday, April 5, 2013 - 12:30pm to 3:30pm Let F_q be the field with q elements. We will consider the task of testing if a m-variate function f over F_q is close to being a polynomial of degree at most d. This task was originally considered in the setting where d was small compared to q and
	Why Laplacian Linear Systems Are Hard, and an Easy Way to Solve Them Quickly Friday, March 22, 2013 - 1:00pm to 4:15pm Fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among
	The Sum of Squares Algorithm: applications, connections, and questions Friday, March 15, 2013 - 1:15pm to 4:15pm The Sum of Squares (SoS) algorithm (Parrilo '00, Lasserre '01) is a semidefinite programming relaxation that has been proposed in various communities under varying names.

Pages