# Theory Seminar 2012 Academic Year

October 9: Parinya Chalermsook (IDSIA), Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More.

October 16: Yuri Makarychev (TTIC), Approximation Algorithms for Semi-random Graph Partitioning Problems.

October 24: Nisheeth Vishnoy (Microsoft Research India), Approximating Fundamental Functions and their Applications. Note non-standard day

October 30: Nathan Srebro (TTIC), Using the Max-Norm for Matrix Reconstruction and Clustering.

November 6: Yi Wu (Purdue University), Approximability of Multiway Partitioning Problems.

November 13: Daniele Micciancio (University of California at San Diego), Algorithms for the Densest Sub-Lattice Problem.

November 27: Pratik Worah (University of Chicago), The Complexity of Somewhat Approximation Resistant Predicates.

December 4: Christopher Beck (Princeton University and University of Chicago), Large Deviations Bounds for Decision Forests and Sampling Lower Bounds for AC0 Circuits.

January 9: Yuval Rabani (Hebrew University), Learning Mixtures of Arbitrary Distributions over Large Discrete Domains. Note non-standard day

January 15: Rusins Freivalds (University of Latvia), Ultrametric automata and Turing machines.

January 22: Benjamin Moseley (TTIC), Online Scheduling with General Cost Functions.

January 29: Siu-On Chan (University of California at Berkeley), Approximation Resistance from Pairwise Independent Subgroups.

February 5: Andrew Goldberg (Microsoft Research Silicon Valley), Highway Dimension: From Practice to Theory and Back.

February 12: James Lee (University of Washington), Multi-way spectral partitioning and higher-order Cheeger inequalities.

February 19: Denis Pankratov (University of Chicago), From Information to Exact Communication.

March 12: Sourav Chakraborty (Chennai Mathematical Institute), Testing of Boolean Function Isomorphism.

April 2: Vladimir Temlyakov (University of South Carolina), Greedy algorithms in compressed sensing.

April 9: Klim Efremenko (IAS), From Irreducible Representations to Locally Decodable Codes.

April 16: Subhash Khot (New York University and University of Chicago), Some open problems in hardness of approximation.

April 23: Gabor Lippner (Harvard University), Bounded degree parameter testing via measurable graphs.

April 30: Dhruv Mubayi (University of Illinois at Chicago), Quasirandom Hypergraphs.

May 7: Elena Grigorescu (Purdue University), Lower bounds for statistical algorithms.

May 14: Van Vu (Yale University), Anti-concentration results and applications.

May 21: Pooya Hatami (University of Chicago), Algorithmic Regularity for Polynomials and Applications.

May 28: Vladimir Podolskii (Steklov Mathematical Institute), The complexity of tropical polynomials and mean payoff games.