Comp Sci 891M Theory Seminar Fall, 2017

Meeting Time: Tue. 4 - 5, CS 140

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