Talks I Missed

The Complexity conference comes to a close today and I head back to Chicago. I tend to go to few talks, preferring hallway conversations, but occasionally I hear about a few great talks that in retrospect I wish I attended.

The first STOC talk, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup. Simple hashing scheme that takes a random function of pieces of an input and XORs them together. Surprisingly this simple scheme is close to looking like a fully random hash function for a variety of purposes.

The last of Thursday's Complexity talks, Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef. An easy reduction from communication complexity to property testing gives a large number of new lower bounds for property testing based on known bounds for communication complexity.

Another FCRC comes to an end. Next year in New York (STOC) and Porto (Complexity).