Taking over from where Michael left off, here’s the summary of the third day of Random Graals 2010

Jeff Steif kicked off the day with a talk on the sensitivity of boolean functions. Here we’re thinking about a boolean function on n variables. We call the function sensitive if the value of the function after a small perturbation of the input is nearly independent of the value before the perturbation. The talk focused on the sensitivity of whether there’s a monochromatic horizontal crossing in a randomly colored hexagonal lattice. Following Jeff, Devavrat Shah offered us each a euro on the condition that not too many people asked for a euro, in which case nobody got anything. This served as an introduction to a nice blackboard talk on protocols for avoiding interference in wireless networks (rather than being a proposal for a new research funding model.) Last talk before lunch was Robin Moser who talked about recent work on Schoning’s randomized algorithm for solving SAT (pick unsatisfied clause, flip value of random variable in the clause, and repeat for a while). E.g., are there better rules for picking the next unsatisfied clause or does it make sense to flip more variables in each step?

After lunch, Seffi Naor talked about the paging problem when the cost of fetching a page into your cache is not uniform (as would be the case with web caching). He presented a new potential function based proof for a O(\log k) competitive algorithm when the size of the cache is k. Lastly, Flavio Chierichetti talked about the relationship between the time it takes for rumors to spread in social networks and the conductance of the relevant graph.

BONUS! A movie… I made the mistake of flying to Bologna, catching a train to Forli, and then taking a taxi to Bertinoro. In the past, the cool kids rode bikes…