B.A.M. 2

The Berkeley Algorithmists' Meeting will continue on Tuesday at 3:30pm.

Scheduling. There have been enough calls to change the time that I will do a recount of the votes and probably change it starting next week. If you would like to come and have not sent me your time constraints, please send them ASAP to mip@alum-mit-edu

Lecture notes. There are definite plans to post lecture notes here, though scheduling constraints will delay this for another week or so.

New topic: Orthogonal Range Queries

I want to spend a couple of meeting talking about range queries, a hugely important topic (in my opinion) that we don't teach too much of. The theory that has developed around this topic is one of the deepest examples of a coherent theory in TCS (maybe close to PCPs, depending on your subjective perception of depth).

Some ideas we will discuss, in an order TBD:

• persistence
  
• predecessor search (especially van Emde Boas)
• buffer trees
• RMQ
• the 3D structure of Nekrich
• rank/select
• lower bounds