DIMACS Theory of Computing Seminar
Spring 2013

Place:                   CoRE 431
Time:                    Wednesdays 11:00 -- 12:00 Noon
Contacts:              Eric Allender and Swastik Kopparty    

See also the schedule for the MATH and CS seminar series. Data on previous semesters is also available.
NOTE to external speakers: Please see the DIMACS webpage for directions.

For those arriving by train to New Brunswick station, the best way to get to the seminar room is by Rutgers bus. The directions are available here: Bus Route.
For those driving in, the best strategy is to park in lot 64 and pre-arrange to pick up a parking tag from one of the organizers upon arrival. For directions to Lot 64, click on this link and enter "Lot 64" in the search box.

TITLE (link to abstracts)
January 23
Raghu Meka
A PTAS for Computing the Supremum of Gaussian Processes

January 30
Stefan Langerman
A Center Transversal Theorem for Hyperplanes Arrangements

February 6
Krysztof Onak
Superlinear lower bounds for multipass graph processing

February 13
Ilya Volkovich
Black-Box Identity Testing Of Depth-4 Multilinear Circuits

February 20
Or Meir
IP = PSPACE via error correcting codes
Seminar will be held in CORE 301(CORE A)
February 27

No seminar
(Organizers are Unavailable)

March 6
Mikkel Thorup
The Power of Tabulation Hashing

March 13
Sushant Sachdeva
Near-linear time algorithms for Balanced Separator by simulating random walks
March 20

No seminar (Spring Break)
March 27
Jing Chen
Leveraging Higher-Order Beliefs in Mechanism Design

April 3
Bahman Kalantari
An Algorithmic Separating Hyperplane Theorem and Its Applications

April 10
Ravishankar Krishnaswamy
Improved approximation algorithms for broadcast scheduling

April 17
Oded Regev
Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication

April 24
Shi Li
Approximating k-Median via Pseudo-Approximation

May 1
Ali Kemal Sinop
Towards a better approximation for Sparsest Cut?

June 27
Hubie Chen
The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space Complexity
Seminar will be held in CoRE 431 at 2:30PM
July 10
Michael Elberfeld
On the Complexity of Monadic Second-Order Logic and its Applications
Seminar will be held in CoRE 431 at 11:00AM