What do you present in a 2-day course with an audience who is:
- really smart
- generally unaware of TCS, but willing to spend time listening to you
- half (non-theory) computer scientists and half hard-core theoretical mathematicians?
----- Day 1 -----
Nearest Neighbor in the Plane. Voronoi diagrams, point location with O(n) space and O(lg n) time via persistent data structures.
- historical references: the autoritative paper is [Driscoll, Sarnak, Sleator, Tarjan: Making Data Structures Persistent. JCSS 1989; STOC 1986]. The initial papers were [Sarnak, Tarjan: Planar Point Location Using Persistent Search Trees. CACM 1986]; [Cole: Searching and Storing Similar Lists. JALG 1986]
- today these results are described in many places. See for example these lecture notes from David Karger's Advanced Algorithms.
- my paper with Timothy Chan on sublogarithmic point location. Open problem: lower bound.
- my paper with Mikkel Thorup giving optimal lower bounds for predecessor search. (In particular, van Emde Boas is optimal for near-linear space.)
- my favorite algorithm for sorting in o(nlg n) time is signature sort, which sorts in O(n) time when the word is w = Ω(lg2+ε n). See for example these lecture notes from our Advanced Data Structures course.
- if my presentation of van Emde Boas managed to confuse you, check out one of the many expositions, such as these lecture notes from our course.
- this is mostly from [Chan: Closest-point problems simplified on the RAM. SODA 2002]. Paper here.
- I blogged about this a while ago.
- there are many expositions of JL. For some very complete proofs, see these lecture notes from Michel Goemans' class.
- the latest LSH paper, with a good bibliography, is [Andoni, Indyk: Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions, CACM 2008]. You can see it on the new and nifty CACM webpage (click the Contents button, then it's on page 117).
- our lower bounds on JL-based algorithms.
- the original paper, now with a Goedel award: [Alon, Matias, Szegedy: The Space Complexity of Approximating the Frequency Moments. JCSS 1999, STOC 1996]
- I believe the latest paper is [Indyk, Woodruff: Optimal Approximations of the Frequency Moments of Data Streams, STOC2005]
- for a nice description of norm estimation, and a whole lot more about streaming algorithms, see Piotr's class
----- Day 2 -----
Define graph sparsity. Examples; handwave about planar separators and algorithmic applications. [What is a good citation for this topic?]
Expander graphs. Handwave about explicit constructions. 2-minute overview of pseudorandomness. Randomness-efficient amplification via random walks on expanders.
- An excellent introduction to pseudorandomness is Salil Vadhan's course. If I got you confused, lecture 8 concerns error reduction by expander walks.
- a whole course on metric embeddings, by Michel Goemans.
- CRC bookchapter by Piotr Indyk and Jiri Matousek.
- there is a ton of recent work (particularly lower bounds = nonembeddability) that I cannot hope to link to here.
- the famous paper that first used embeddings for sparsest cut is [Linial, London, Rabinovich: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica 1995, FOCS 1994]
- the sqrt(lg n) paper is [Arora, Rao, Vazirani: Expander Flows, Geometric Embeddings, and Graph Partitionings. STOC 2004]. See here.
- a lot of recent (and not so recent) research has been done about this problem. A personal favorite here is [Spielman, Teng: Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, STOC 2004]