Polylogs seen at FOCS 2009 Day 1

(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 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.
2. 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).
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 , 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.

ICS accepts…

Anybody who hasn’t heard about the new theory conference Innovations in Computer Science (ICS 2010) has clearly been working too diligently and not reading their theory blogs (see here, there, this, that, those, and these.) Well, it seems like the PC have been busy: the accepted paper list and abstracts have just been posted.

Papers particularly relevant to this blog are:

• Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction [Gabizon, Hassidim]
• Space-Efficient Estimation of Robust Statistics and Distribution Testing [Chien, Ligett, McGregor]
• Pan-Private Streaming Algorithms [Dwork, Naor, Pitassi, Rothblum, Yekhanin]

Looks like privacy could be a hot topic in forthcoming data streams research (see also this recent post from Muthu.)

As before, if you spot a version of any of the above papers online, please send me a link so I can add it. Cheers.