# 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.