DIMACS Seminar on Theoretical Computer Science
Spectral Techniques for Proving Lower Bounds in Computational Geometry
- Bernard Chazelle
- Princeton University
- DIMACS Seminar Room, CoRE Building, Room 431
- Busch Campus, Rutgers University
- 10:00 AM
- Wednesday, April 19, 1995
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
Document last modified on April 11, 1995