CMPSCI 891M: The UMass CMPSCI Theory Seminar

The Theory Seminar is a weekly series of talks of general interest to researchers and students of theoretical computer science. It meets Tuesdays 4-5 p.m. in room 140 of the Computer Science Building, though occasional talks might occur at other times.

It is also a one-credit UMass graduate course, in which each participating student will give one of the presentations.

I am the coordinator for Fall 2009. Talks will be announced to the "seminars" list and will appear on the department's weekly schedule. The schedule below will be updated as needed throughout the term.

The seminar web page for Spring 2003, when I was last the coordinator, is here. It has links to the titles and abstracts of talks from that term.

Schedule for Fall 2009

• 8 September: No meeting, CNS convocation
• 15 September: Organizing meeting, no seminar
• 22 September: No seminar
• 29 September: David Mix Barrington, ACC⁰ versus CC⁰
• 6 October: Creidieki Crouch
• 13 October: no seminar, this is a Monday at UMass
• 20 October: Andrew McGregor
• 27 October: no seminar
• 3 November: Philipp Weis, The Power of One Star
• 10 November: Mark McCartin-Lim, Algorithms for Finding Low Distortion Bijections
• 16 November: Department seminar, Sergei Vassilvitskii, Yahoo Research, A Model of Computation for MapReduce
• 17 November: no regular seminar
• 24 November: Jon Machta, UMass Physics
• 1 December: Brandon McPhail
• 8 December: John Brattin

Suggested Seminar Topics:

Here are some recent papers that I think might make good talks:

• Mark Braverman, Poly-log Independence Fools AC⁰ Circuits, ECCC TR09-011,
• Kristoffer Arnsfelt Hansen and Michal Koucky, A New Characterization of ACC⁰ and probabilistic CC⁰ (PDF) (Dave's talk on 29 September),
• Cohn, Kleinberg, Szegedy, Umans, Group-Theoretic Algorithms for Matrix Multiplication (PDF), and
• Braverman, Cook, McKenzie, Santhanam, Wehr, Pebbles and Branching Programs for Tree Evaluation, (PDF).

Schedule for Spring 2009:

• 3 February: Louis Theran, Combinatorial Genericity and Minimal Rigidity
• 10 February: David Mix Barrington, Uniform Circuits for Integer Division
• 17 February: No seminar!
• 24 February: Andrew McGregor, Space-Passes Tradeoffs in Stream Complexity
• 3 March: Ileana Streinu, How Far Can You Reach? A Tale of Geometry, Robots, and Proteins (in room 151)
• 10 March: no seminar
• (spring break)
• 24 March: no seminar
• 31 March: no seminar
• 7 April: Alex Russell, UConn, Alex Russell, UConn, Approximating the Permanent via Nonabelian Determinants
• 14 April: TBA
• 21 April: no meeting, this is Monday at UMass
• 28 April: Ben Rossman, MIT, Ehrenfeucht-Fraisse Games
• 4 May (Monday): Graham Cormode, AT&T, Finding Frequent Elements in Data Streams
• 5 May: Mike Sindelar, UMass, An Introduction to Mechanism Design
• 12 May: Brandon McPhail, UMass, Optimal Offline Power-Down Scheduling

Last modified 9 November 2009