Some people have asked me to post my survey/talk at ESA on Open Problems in Cuckoo Hashing. Now that the talk is over, here they are! Here's the paper, and here's the slides (ppt). I apologize in advance for any typos.
One open question that was "solved" between the time from the paper to the talk is that a group of us now have tight bounds on the "thresholds" for cuckoo hashing in the case of 3 or more choices, with 1 bucket per bin. Hopefully we'll have a writeup available soon, but I guess I'm "annoucning" the result.