(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. :)

  1. 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 \omega(\log n) players remains open. The paper’s result is a nontrivial bound on an AC^0 function that holds for up to O(\log n) players. The AC^0-ness is the crucial new part; the now-classic result of Babai-Nissan-Szegedy was for a function involving PARITY.
  2. Eyal Kushilevitz spoke about joint work with his postdoc Enav Weinreb on DISJOINTNESS with O(\log n)-sized subsets of the universe \{1,\ldots,n\}, with a promise that the intersection size is at most 1. Clearly, the communication complexity of this problem is at most O(\log^2 n), but is it in fact that high? A randomized protocol can achieve O(\log n) communication, by a neat idea due to Hastad and Wigderson. The authors here show that the deterministic complexity is \Omega(\log^2 n / \log\log n). This has some connections to some long-standing open problems such as CLIQUE-vs-IND-SET (see Kushilevitz-Nisan for more on that).
  3. 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 ACC^0, 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 MOD_m gates, with m a product of two distinct primes. To cut a long story short, the reason MOD_m gates make things challenging is that the integers modulo m 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.