In memory of Mihai Pătraşcu. Continuing the spirit of the previous post, in this post I will describe a specific technique for proving lower bounds for (static) data structures, when the space is (near) linear. This technique was introduced in the paper by Mihai and Mikkel Thorup, called "HIGHER lower Bounds for Near-Neighbor and F … Continue reading Higher Lower Bounds: Just Ask for More!
Month: June 2012
The Art of Reductions
In memory of Mihai Pătraşcu Written by Rasmus Pagh, Rina Panigrahy, Kunal Talwar and Udi Wieder Reductions are arguably at the heart of complexity theory. They show that one problem is at least as hard as another. Finding reductions often requires creativity and considerable technical skill; some reductions seem as if they were pulled from thin air. The most difficult … Continue reading The Art of Reductions
Balls and Bins on Graphs
"Balls and Bins?", you ask, "Is there anything left to prove there?" Surprisingly, there are really natural questions that are open. Today I want to talk about one such question. First a quick primer. Balls and Bins processes model randomized allocations processes, used in hashing or more general load balancing schemes. Suppose that I have … Continue reading Balls and Bins on Graphs
“Just a Spoonful of Sugar …”
Tim Roughgarden sent me the following email. I found this idea so refreshing that I thought I should share more widely. Well done PC! -------------------------------------------------------------------------------- PC meetings are typically all work and no play. But the FOCS '12 PC, in an act of rebellion, has decided to spend a day disucssing their own results, before … Continue reading “Just a Spoonful of Sugar …”
Windows On Theory 