Yesterday, I defended my non-existent thesis, apparently with success. (The thesis itself will be done on August 29, at or around 2:58pm. There are plans to make it readable.)
Here are the slides from the defense in PPTX (also saved as PPT with minor screw-ups). Sorry, no reasonable PDF. Due to lack of time in making the slides, a lot of the presentation was verbal commentary, but hopefully the slides also have some value.
In other news, I am once again fed up with Powerpoint, and I will be switching back to LaTeX/Beamer. Last time I quit Beamer because xfig sucked, but in the mean time I discovered TikZ and it is impressive.
By the way, when discussing the history of cell-probe lower bounds, it occurred to me that the two major foundational papers that really started the whole field were:
- [Ajtai 88], published in Combinatorica, but proving a false result.
- [Fredman, Saks 89], published in STOC, containing tons of claims without proofs, and not followed by any journal version.
[[ *Though paper is an almost perfect solution to preserving your ideas into cold immortality, some care must be exercised. To prevent ware and tare, it is recommended that your piece of absolute truth does not motivate any reckless readers to actually open the journal at the pages of your paper. ]]
Incidentally, these two papers are also the "second paper" in the field (after Andy Yao defined the model a decade earlier). This reminded me of Luca's very sensible "second paper" observation.