MSR/MIT Theory Reading Group
 |
Dana Moshkovitz: Candidate Lasserre Integrality Gap for Unique Games Friday, November 14, 2014 - 12:45pm to 3:45pm The Unique Games Conjecture of Khot is the basis of remarkable inapproximability results. In recent years, researchers have explored possible algorithms for refuting it based on the Lasserre (aka Sum of Squares) hierarchy of semidefinite programs. |
|
|
Aaron Potechin: Sum of Squares Lower Bounds for the Planted Clique Problem Friday, November 7, 2014 - 12:45pm to 3:45pm The planted clique problem asks whether or not we can find a k-clique which is planted in a random G(n,1/2) graph. |
|
|
Rakesh Vohra: Rounding in Matching Problems from Economics Friday, August 15, 2014 - 1:15pm to 4:15pm Matching problems in Economics, frequently differ from traditional matching problems in that the matching with desired properties one seeks is not the solution to linear optimization problem defined over the set of feasible matchings. The difference arises from the role of preferences. |
|
|
Aaron Sidford: Path Finding Methods for Linear Programming Tuesday, July 29, 2014 - 12:45pm to 3:45pm In this talk, I will present a new algorithm for solving linear programs. |
|
|
Bernhard Haeupler: How to Have a Conversation Despite Noise Friday, July 25, 2014 - 12:45pm to 3:45pm Error correcting codes have transformed the way we transfer information. In particular, they give computationally efficient ways to protect one-way communications against noise by adding minimal amounts of redundancy. |
|
|
Siu On Chan: Lower Bounds for Extended Formulations Friday, August 1, 2014 - 12:45pm to 3:45pm Linear and semidefinite programs can sometimes be rewritten to significantly reduce the number of inequalities in the programs. Such a rewriting is known as an extended formulation. |
|
|
Toward Better Formula Lower Bounds: An InformationOr Meir: Complexity Approach to the KRW Composition Conjecture Friday, May 2, 2014 - 12:45pm to 3:45pm One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,{P} otsubseteq mathbb{NC_1}$ ). |
|
|
Dana Moshkovitz: An Algebraic Parallel Petition Theorem Friday, March 28, 2014 - 12:45pm to 3:45pm A long line of work in Theoretical Computer Science shows that a function is close to a low degree polynomial iff it is close to a low degree polynomial "locally". This is known as "low degree testing", and is the core of the algebraic approach to construction of PCP.
|
|
|
Justin Thaler: Approximate Degree and the Method of Dual Polynomials Friday, February 14, 2014 - 12:45pm to 3:45pm The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. |
|
|
Venkatesan Guruswami: List Decoding by Evading Subspaces. Friday, February 21, 2014 - 12:45pm to 3:45pm A natural "folded" variant of the classical Reed-Solomon codes are known to be list-decodable with optimal redundancy (in particular, only epsilon higher than the worst-case error fraction, for any desired epsilon > 0). |
Pages
