(Amit apologizes for not actually posting this while at FOCS)
Today there were no streaming papers per se, but we did see some neat work on communication complexity, a topic that looms large in streaming lower bounds. The specific results I’ll talk about don’t have streaming implications I know of, but they all involve polylogs, which I think makes them on topic for this blog. :)
- Paul Beame spoke about work with his student Trinh Huynh on lower bounds on multiparty communication complexity (in the number on the forehead model). I can’t do justice to this lovely and challenging topic here. Let me just say that a nontrivial lower bound for any explicit function with players remains open. The paper’s result is a nontrivial bound on an function that holds for up to players. The -ness is the crucial new part; the now-classic result of Babai-Nissan-Szegedy was for a function involving PARITY.
- Eyal Kushilevitz spoke about joint work with his postdoc Enav Weinreb on DISJOINTNESS with -sized subsets of the universe , with a promise that the intersection size is at most 1. Clearly, the communication complexity of this problem is at most , but is it in fact that high? A randomized protocol can achieve communication, by a neat idea due to Hastad and Wigderson. The authors here show that the deterministic complexity is . This has some connections to some long-standing open problems such as CLIQUE-vs-IND-SET (see Kushilevitz-Nisan for more on that).
- Arkadev Chattopadhyay didn’t talk about communication complexity per se, but about work, joint with Avi Wigderson, motivated by the quest for lower bounds against , a goal shared by a well-known line of work in communication complexity. They gave the first exponential size lower bound for certain depth-3 circuits allowing gates, with a product of two distinct primes. To cut a long story short, the reason gates make things challenging is that the integers modulo do not form a field.
On the non-technical front, lunch was on the top (25th) floor of the hotel, in a room affording nice panoramic views of the city. Breakfast, however, left much to be desired, being comprised of just coffee and cupcakes. Thankfully, I had had a sumptuous meal the previous night, at Mary Mac’s.