CMPSCI 891M: The UMass CMPSCI Theory Seminar

(18 Apr) Note further schedule changes -- next talk is 29 April.

The Theory Seminar is a weekly series of talks of general interest to researchers and students of theoretical computer science.

It is also a one-credit UMass graduate course, in which each participating student will give one of the presentations. Students planning to take the course for credit should email Prof. Barrington with their plans as to when to talk.

The current schedule is as follows. (Links, where available, lead to abstracts of the talks.)

• 28 Jan 2003: NO MEETING

• 4 Feb 2003: Jamieson Cobleigh, Learning Assumptions for Compositional Verification

• 11 Feb 2003: Bill Hesse, Dynamic Computational Complexity

• 18 Feb 2003: NO MEETING (Monday schedule at UMass)

• 25 Feb 2003: Micah Adler, A Stochastic Process on the Hypercube with Applications to Peer-to-Peer Networks

• 4 Mar 2003: David Mix Barrington, Constant-Depth Circuits and First-Order Logic

• 11 Mar 2003: NO MEETING (in deference to ECE seminar)

• 18 Mar 2003: NO MEETING (spring break)

• 25 Mar 2003: Arny Rosenberg, On Scheduling Collaborative Computations on the Internet: Mesh-Dags and Their Close Relatives

• 1 April 2003: NO MEETING (Amherst town elections)

• 8 Apr 2003: Neil Immerman, Dichotomy and Constraint Satisfaction Problems

• 15 Apr 2003: NO MEETING (faculty candidate seminar)

• 22 Apr 2003: NO MEETING (faculty candidate seminar)

• 29 Apr 2003: Louis Theran, Protocols for Asymmetric Communication Channels

• 6 May 2003: Matt Yurkewych, Pebbling and Input/Output Complexity

• 13 May 2003: Brent Heeringa, title/abstract TBA

• (plus two ad hoc sessions for Audrey Lee and Kazu Hirata)

The following papers were among those suggested as possible student topics by faculty (additions to this list are welcomed):

• Agrawal-Allender Datta, "On TC0, AC0, and Arithmetic Circuits", 12th IEEE Complexity, 1997. (Dave)
• Caussinus-McKenzie-Therien-Vollmer, "Nondeterministic NC1 Computation", 11th IEEE Complexity, 1996. (Dave)
• Etessami, "Counting Quantifiers, Successor Relations, and Logarithmic Space", 10th IEEE Complexity, 1995. (Dave)
• Jenner-McKenzie-Toran, "A Note on the Hardness of Tree Isomorphism", 13th IEEE Complexity, 1998. (Dave)
• Lange-McKenzie-Tapp, "Reversible Space Equals Deterministic Space", 12th IEEE Complexity, 1997. (Dave)

Here are links to the theory seminar talks from Fall 2002:

• 17 Sept 2002 Brent Heeringa, "Promise Pruning"

• 24 Sept 2002: David Mix Barrington, "Grid Graph Reachability"

• 1 Oct 2002: Bill Hesse, "Adding Shortcuts to Directed Graphs"

• 8 Oct 2002: Arny Rosenberg, "How to Exploit a Heterogenous Cluster of Workstations (Asymptotically) Optimally"

• 15 Oct 2002: Ying Gong, "Efficient Scattering of Variable-Length Messages in Heterogeneous Clusters"

• 22 Oct 2002: Neil Immerman, "Descriptive Complexity: Survey Plus New Directions"

• 29 Oct 2002: Kazu Hirata, "PRIMES is in P"

• 5 Nov 2002: Jody Fanto, "What's Wrong With Being Selfish?"

• 12 Nov 2002: Matt Yurkewych, "Monadic NP versus Monadic co-NP"

• 19 Nov 2002: Asa Ben-Hur, Stanford, "A Stability Based Method for Discovering Structure in Clustered Data"

• 26 Nov 2002: Audrey Lee, "Extracting Randomness: How and Why"

• 3 Dec 2002: Qunfeng Dong, "Efficient Schemes for Probabilistic Packet Marking"

• 10 Dec 2002: Sarah Weissman, "An Introduction to Zero-One Laws"