Palo Alto Talks

Last week was a whirl of talks.

• Bob Tarjan started his lectures on algorithms+data structures with amortized analysis. The simple example of counting the number of bit operations needed to increment n times, led to potential function based analysis and nice exercises of getting worst case bounds (via redundant codes, still with O(log n) bits). Qiqi Yan asked if there was a way to appeal to LP Duality to get worst case bounds in general. Then, Bob introduced different "heap" representations from the standard to tournament (n values are leaves of a tournament), half full (replace winners by empty slots), right full (make all empties the left branch), compressed (keep links to successive winners), and finally to half ordered representation by linking the siblings. Those who know Bob or read his monograph know, he is superbly efficient with his words. I mentored myself from his monograph when I was a graduate student, and this is now an in-person treat!
• Vijay Vazirani spoke about markets. He started with the Arrow-Debreu (AD) model that shows that there are prices for a supply that will satisfy every demand and clear the market precisely. This result has many implications and issues (not unique even beyond scaling, pareto optimality, every pareto optimal allocation comes from equilibrium after redistribution of wealth, dynamics? etc). Vijay spoke about his joint work with Kamal Jain on studying this problem with digital goods with no cost to infinite supplies and challenge is to envision a nontrivial market that doesn't allow equilibriums when everyone gets every copy of the digital good. He proposed a model that involved grouping items into semantic categories with full substitutability within each for uniform prices, and a rich context with cardinal and ordinal preferences. Now supply/demand constraints become more intricate, some bundles are forbidden, and the entire edifice of AD has to be reconstructed. This is a grand problem where Vijay's natural ebullience keeps the audience engaged through the myraid details of formulations. He left open even grander problems of pricing items like theorems, financial advice and innovations.

Talks are one-sided. I managed to have two-sided conversations not only with Bob and Vijay, but also Ashish and Tim over dinner. Tim is going through energy spins, waxing and waning with the weekly cycles of his teaching, and he shared a key insight (or two! :)): some textbooks are for professors and others are for students. In Algorithms, we know which is which. My favorite professors' text is the monograph by Dexter Kozen, The Design and Analysis of Algorithms. Ashish, who can quietly float to the top of any topic, described the excitement of molecular machines which can trot along biological material and repair strands.