DIMACS/CS Light Seminar: Theoretical Computer Science
Fall 2008

Place:                   CoRE 431
Time:                   Wednesdays 11:00 -- 12:00 Noon
Contacts:               Mario Szegedy and Eric Allender
Index number:     
198:500:02  (07898)

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

TITLE (link to abstracts)
September 3

No Seminar This Week
September 10
Kazuo Iwama

Competitive Auctions with Collusion

September 17
Zeev Dvir
The finite field Kakeya conjecture and applications to the construction of mergers and extractors

September 24
Anup Rao
Parallel Repetition: Theorems and Counterexamples

October 1
Amir Yehudayoff
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

October 8
Timothy Y. Chow
Almost-Natural Proofs

October 15
Dana Moshkovitz
Two Query PCP with Sub-Constant Error
CoRE 301
October 22
Arkadev Chattopadhyay
Properly 2-Colouring Linear Hypergraphs

October 29
Adi Akavia
Locally & Universally Finding Significant Fourier Coefficients

November 5
Ryan Williams
Applying Practice to Theory: Time-Space Lower Bounds for SAT

November 12
Martin Farach-Colton
How to commercialize theoretical research.
And also some interesting math about memory hierarchies

November 19
Gabor Kun
Derandomizing Feder-Vardi
CoRE 301
November 26
Xi Chen
Graph Homomorphisms with Complex Values: A Dichotomy Theorem

December 3
Bhaskar DasGupta
Transitive reductions, Horn formula optimizations and Parallel repetition theorem

December 10
Alantha Newman
Real complex semidefinite programming and its application to circular arrangements
CoRE 301