Discrete Math/Theory of Computing Seminar

Rutgers University, Piscataway, N.J.

Spring 2002

Organizers: Eric Allender and Michael Saks

Previous semesters

January 29
        Speaker:    Amihood Amir
        Title:           Approximate Pattern Matching - the Hamming Distance Case
        Time:         4:30-5:30
        Place:         CORE 431

February 5
        Speaker:    Mario Szegedy
        Title:           Introduction to quantum computing
        Time:         4:30-5:30
        Place:         CORE 431

February 12
        Speaker:    Reuven Kashi
        Title:           Analyzing Quantitative Databases: Image is Everything
        Time:         4:30-5:30
        Place:         CORE 431

February 19
        Speaker:    Andris Ambainis
        Title:           A New Protocol and Lower Bounds for Quantum Coin Flipping
        Time:         4:30-5:30
        Place:         CORE 431

February 26
        Speaker:    Pavan Aduri
        Title:           Cook vs Karp-Levin
        Time:         4:30-5:30
        Place:         CORE 431

March 5
        Speaker:    Vašek Chvátal
        Title:           TSP cuts that do not follow the template paradigm
        Time:         4:30-5:30
        Place:         CORE 431

March 12
        Speaker:    Avner Magen
        Title:           Girth and Euclidean Distortion
        Time:         4:30-5:30
        Place:         CORE 431

March 19
        NO SEMINAR: Spring Break

March 26
        Speaker:    Cliff Smyth
        Title:           Reimer's Inequality and Tardos' Conjecture
        Time:         4:30-5:30
        Place:         CORE 431

April 2
        Speaker:    Lance Fortnow
        Title:           Computational Depth
        Time:         4:30-5:30
        Place:         CORE 431

April 9
        Speaker:    Anna Gilbert
        Title:           Near-Optimal Sparse Fourier Representations via Sampling
        Time:         4:30-5:30
        Place:         Hill 705 (NOTE ROOM CHANGE!)

April 16
        Speaker:    Ronitt Rubinfeld
        Title:           Testing Properties of Distributions
        Time:         4:30-5:30
        Place:         CORE 431

April 23
        Speaker:    Martin J. Strauss
        Title:           Fast, Small-Space Algorithms for Approximate Histogram Maintenance
        Time:         4:30-5:30
        Place:         CORE 431

April 30
        Speaker:    S. Muthukrishnan
        Title:           Surfing Streams
        Time:         4:30-5:30
        Place:         CORE 431

May 7
        Speaker:    Manoj Prabhakaran
        Title:           Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models
        Time:         4:30-5:30
        Place:         CORE 431