Theory Seminar 2011 Academic Year
October 12, 3pm: Jaroslav Nesetril (Charles University), Degree of Freedom of Sparse Graphs. Note non-standard day
October 18: Madhu Sudan (Microsoft Research, Boston), Invariance in Property Testing.
October 20, 1:30pm: Julia Wolf (Ecole Politechnique), Quadratic pseudorandomness and decomposition theorems for bounded functions. Note non-standard time and day
October 20, 3pm: Satya V. Lokam (Microsoft Research, Bangalore), Efficient Reconstruction of Random Multilinear Formulas. Note non-standard day
October 25:
November 1:
November 8: Imre Risi Kondor (University of Chicago), Solving the Quadratic Assignment Problem in Fourier Space.
November 15: Siavosh Benabbas (University of Toronto), An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Bounded-degree Graphs.
November 22: Madhur Tulsiani (TTIC), Quadratic Goldreich-Levin Theorems.
November 29: Christopher Beck (Princeton University), Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space.
January 10: YouMing Qiao (Tsinghua University), Random Arithmetic Formulas can be Reconstructed Efficiently.
January 17: Shmuel Weinberger (University of Chicago, Department of Mathematics), Persistent homology of large networks.
January 31: John Lafferty (University of Chicago), Nonparametric Forest Density Estimation.
February 7: Lek-Heng Lim (University of Chicago, Department of Statistics), Numerical Computations Beyond Linear and Convex.
February 10: Erik Winfree (Cal Tech), Life at the interface of computer science and chemistry. Collocated with CS Dep. Colloquium; note non-standard day
February 21: Lance Fortnow (Northwestern University), Robust Simulations and Significant Separations.
March 1: Yuval Rabani (The Hebrew University of Jerusalem), A Constant Factor Approximation Algorithm for Reordering Buffer Management. Note non-standard day
March 6: Gyorgy Turan (University of Illinois at Chicago), Belief revision and commonsense knowledge bases.
March 13: Eli Ben-Sasson (Technion and Microsoft Research, Boston), An Additive Combinatorics Approach to the Log-Rank Conjecture in Communication Complexity.
March 28: Chandra Chekuri (University of Illinois at Urbana-Champaign), Multicommodity Flows and Cuts in Polymatroidal Networks. Note non-standard day
April 3: Preyas Popat (New York University and University of Chicago), Hardness of approximating the Closest Vector Problem with pre-processing.
April 10: Srikanth Srinivasan (IAS/Rutgers), Pseudorandom Generators for Read-Once ACC^0.
April 17: Gabor Kun (New York University), Constraint Satisfaction Problems and expander relational structures.
April 24: Nathan Srebro (TTIC), Fat Shattering, Learning, and Lower Bounds on Convex Optimization.
May 1: John Wilmes (University of Chicago), On the Banni-Ito conjecture on distance-regular graphs.
May 15: Alexandra Kolla (UIUC), Maximal Inequality for Spherical Means on the Hypercube.
May 16, 11:30am, Ry277: Ilias Diakonikolas (University of California at Berkeley), Reconstructing Boolean Threshold Functions from their Average Satisfying Assignment. Note non-standard day, time and place
May 22: David Schuster (University of Chicago), Progress in quantum computing using superconducting circuits.
May 29: Tamir Hazan (TTIC), Weighted Counting using the Heaviest Element and Their Role in Machine Learning.
June 5: Mark Braverman (Princeton University), Towards Coding for Maximum Errors in Interactive Communication.