Organizer: Neil Immerman

The theory seminar is a weekly meeting in which topics of interest in the theory of computation -- broadly construed -- are presented. This is sometimes new research by visitors or by local people. It is sometimes work in progress, and it is sometimes recent or classic material of others that some of us present in order to learn and share.

The goal of all talks in this seminar is to encourage understanding and participation. We would like as many attendees as possible to get a sense of the relevant ideas being discussed, including their context and significance.

Please email me if you would like to give a talk, or if you would like to suggest/invite/volunteer someone else; or a paper or topic that you would like to see covered.

This is a one-credit seminar which may be taken repeatedly for credit. (Students taking the Theory Seminar for credit are usually theory Ph.D. students. They are expected to attend essentially all of the talks, trying to understand and participate; and to give at least one of the talks.)

Schedule, Fall, 2017:

9/5	brief organizational meeting	Please come and help us get organized. Whether or not you can come, please email me with times that you can/would-like-to speak.
9/19	Sam McGuire	Some Problems in Dynamic Descriptive Complexity Theory
10/3	Cameron Musco	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
10/17	Srinivasan Iyengar	Improving Solar Energy Penetration with Lagrange Multipliers
10/24	Gautam Kamath	Statistical Hypothesis Testing in the Modern Age
11/3, 11 - noon, CS 142	Amit Chakrabarti	Time-Space Tradeoffs for the Memory Game
11/7	David Tench	Algorithms on Graphs of Bounded Clique-Width
11/8: DLS talk, 4 p.m., 151	Muriel Medard	Network coding - a Personal Account of Combining Theory and Practice
Fri, 11/10, 10:30 a.m., CS142 special Distinguished Theory Colloquium	Sofya Raskhodnikova	Sublinear-Time Algorithms
11/14	Sophie Koffler	One Step Closer to P
11/16: DLS talk, 4 p.m., 151	Ronitt Rubinfeld	Local Computation Algorithms
11/28	Stefan Grosser	The Polynomial Method: Algebraic Applications in Combinatorics
12/5	William Toohey	Nonuniform ACC Circuit Lower Bounds
Mon, 12/11, 4 p.m., CS142 special Distinguished Theory Colloquium	Ryan Williams	Thinking Algorithmically About Impossibility
12/12	Sam Schlesinger	The Sensitivity of a Function