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.