DIMACS Seminar on Theoretical Computer Science

Title:

Spectral Techniques for Proving Lower Bounds in Computational Geometry

Speaker:

Bernard Chazelle

Princeton University

Place:

DIMACS Seminar Room, CoRE Building, Room 431

Busch Campus, Rutgers University

Time:

10:00 AM

Wednesday, April 19, 1995

Abstract:

Given n points and n regions (simplices or boxes) in R^d count how many points lie in each region. This problem, motivated by computer graphics applications, has been the subject of intense scrutiny in computational geometry. If subtractions are disallowed (the monotone case), then the problem is basically solved. The non-monotone case, however, like most questions in non-monotone circuit complexity, is still wide open. We report some partial progress on this problem, based on the twin use of spectral techniques in circuit complexity and geometric discrepancy theory.

Schedule for the Spring Semester

Jan. 25: Sridhar Rajagopalan: On the value of Planning and Capital
Feb. 1: Neal Young: Randomized Rounding Without Solving the Linear Program
Feb. 8: Richard Lipton: Speeding Up Computations via Molecular Biology
Feb. 15: no meeting; but note the DIMACS Complexity day, Feb. 17
Feb. 22: Shiyu Zhou: Explicit Dispersers with Polylog Degree
Mar. 1: Bhaskar DasGupta: Analog versus Discrete Neural Networks
Mar. 8: no meeting
Mar. 22: Eric Allender: Sparse Hard Sets for P Give Space-Efficient Algorithms
Mar. 29: Robert Beals: Symmetric Logspace is Closed Under Complement
Apr. 5: no meeting; but note Columbia University's Theory Day, April 7
Apr. 12: Kathleen Romanik: A 3-Dimensional Visibility Representation for Graphs
Apr. 19: Bernard Chazelle: Spectral Techniques for Proving Lower Bounds
Apr. 26: Sanjeev Arora
May 3: Phillip M. Long
May 10: Rajeev Alur: Timed Automata
May 17: Mikkel Thorup: An O(log log n) Priority Queue