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