DATE
|
SPEAKER
|
TITLE
(link to
abstracts)
|
Notes
|
Sept 6
|
Adi Avidor
|
Rounding two and three dimensional solutions
of the SDP relaxation of MAX CUT
|
|
Sept 13
|
Ilan Newman
|
Testing Orientations
|
|
Sept 20
|
Mario Szegedy
|
The quantum adversary method and classical formula size lower bounds
|
|
Sept 27
|
Joel Ratsaby
|
Information and Learning
|
|
Oct 4
|
Henning Schnoor
|
Generalized Modal Satisfiability
|
|
|
Oct 11
|
Saugata Basu
|
Efficient Algorithms for Computing the Betti
Numbers of Semi-algebraic Sets
|
|
Oct 18
|
Pierre McKenzie
|
Incremental branching programs
|
|
Oct 25
|
|
|
No talk because of FOCS
|
Nov 1
|
Andrej Bogdanov
|
Pseudorandom generators for low degree polynomials
|
|
Nov 8
|
Dror Weitz
|
Glauber dynamics on trees: Boundary conditions and mixing time
|
Talk will be held in CoRE 301 (Conference room A); regular DIMACS seminar room is unavailable
|
Nov 15
|
James R. Lee
|
Trees and Markov convexity
|
|
Nov 22
|
Sambuddha Roy
|
The directed planar reachability problem
|
|
Nov 29
|
Rohan Fernandes
|
Upper and Lower Bounds in Sensor Network Bootstrapping
|
|
Dec 6
|
Joe Kilian
|
Combining Cryptographic Primitives
|
|
Dec 13
|
Eric Allender
|
On the Complexity of Numerical Analysis
|
|
Dec 20
|
Dieter van Melkebeek
|
A Generic Time Hierarchy for Semantic Models With One Bit of Advice
|
Last Seminar for Fall 05
|