Theory Seminar
Our seminar is intended to be broad and will (hopefully) cover not only what is traditionally referred to as "core theory", but also many topics at least distantly related to it. And when we are really interested in a result and/or a speaker, the employed notion of distance will be understood rather liberally!
Logistically, our normal meeting time and place is:
Tuesday, 3pm
Ryerson 251
(refreshments are served before the seminar). But, as a courtesy to our out-of-town speakers, we expect to meet occasionally on a different day, read the announcements carefully (and sign to our mailing list if you want to receive them on a regular basis).
Current Year's Program
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)
May 29: Tamir Hazan (TTIC), Weighted Counting using the Heaviest Element and Their Role in Machine Learning.
June 5: Mark Braverman (Princeton University)