From the Simons institute

Last year I had a great sabbatical at Harvard university, and this semester, thanks to the flexibility of the NEU administration, I am at the Simons institute in Berkeley for their program on fine-grained algorithms and complexity. The institute is amazing, and there is an avalanche of interesting talks which is overwhelming, even by Boston standards.

As with all great things, one can wonder if the institute could be made even better. Here are two small thoughts about this. The first is about housing. I think it would be nice to have a block of houses managed by the institute. And I think I would think so even if my experience with finding housing hadn’t been what it has been. The starting point is that I could not find anything that suited me. Whatever the reason for this, it was definitely *not* because of lack of support from the institute. At some point a good listing did come out, and I immediately grabbed it, but after a long exchange the landlord changed their mind. By that time it was very late in the game, and it was harder to find anything. Since I was about to spend more time looking for an apartment than actually living there, I decided to go all-out and pay a rent that is ridiculous even for someone who rented in New York city. Naturally, I ended up in a terrible place. For one thing, I happen to disagree with the landlord’s calculation that a human being needs less than 100 square feet to survive. Shame on me for not inquiring about the size of the unit. So, even if the market looked completely hopeless, I had to get back into it. Here again the institute’s staff was extremely supportive, and in a reversal of fortune they spotted an ad for a place which turned out to be fantastic.

The second is equipment. I was given a nice corner office, substantial financial support, a bike, a keyboard/mouse set, and a monitor, but not a computer. Admittedly, this is not a great loss, because setting up a new machine is almost as much hassle as bringing your own. This brings me to a point which has nothing to do with the institute, but which I’ll make here. What I would like are machines where you just need to push a button to have your exact workbench appear. This would be great even if it took a little installation time, as long as everything was automated, because you could just push that button ahead of time. Of course we do have Chromebooks, rollApp, Remote Desktop, et cetera, but none of this comes close to having your own settings. Indeed, today’s solution to the problem amounts to travelling with your own laptop — something which brings to my mind the expression “downfall of mankind.”

I am reminded of a Java project that I did during my undergraduate at La Sapienza. We had to program an application at home, and then show it to the professors in the department. My group was perhaps the only one which did not drag their own desktop computer to run the application. So much for Java. We were quite proud of showing up with just a floppy disk, until our application did in a few minutes something that had never done in days of intense domestic beta-testing.

Going back to the talks that we had, Zuckerman gave a talk about his impressive 2-source extractor with Eshan Chattopadhyay. One component of their construction is an extractor for n-bit sources where n-n0.99 bits are polylog(n)-wise independent, and the other n0.99 are an arbitrary function of the former, which answers a question raised in a paper of mine. Alexander Kulikov spoke about his better-than-3n lower bound for the circuit complexity of an explicit function, with Magnus Gausdal Find, Alexander Golovnev, and Edward Hirsch. Their strongest lower bounds are for computing extractors for degree-2 GF(2) polynomials, an object that is not currently available. And I talked about the Local Reductions developed with Jahanjou and Miles.

Communication Complexity in Banff

I am back from the first ever workshop on communication complexity, held in Banff.  As if to prove the great unifying perspective of communication complexity, the workshop had talks on a wide variety of topics, from data structures to circuit lower bounds, and to streaming algorithms.

On the first day Larsen gave a survey talk on static data structures.  I hadn’t realized that it is still open to prove a superlogarithmic lower bound for any explicit problem — with polynomially many queries and linear space.  Larsen mentioned a sampling technique which he refined to obtain such logarithmic bounds, and which he patiently reexplained to me after his talk and even after the workshop.

So consider the problem of storing a polynomial of degree d over a finite field F of size |F| = d^2 such that you can answer evaluations by only probing t cells, possibly adaptively.  All these bounds are in the cell-probe model, with cells of log|F| = 2 log d bits.  We will show that an efficient data structure using linear space S = O(d) implies an encoding of the polynomial with length less than (d+1) log |F| bits, which is impossible.

The idea for the encoding is simply to select from the S cells of the data structure a uniform set of pS cells, and to write them down together with their indexes.  (Note that adding the index at most doubles the number of cells, because you start with S cells and a cell has 2 log d bits.)  The length 2 pS log |F| of this encoding will be less than (d+1) log |F| as soon as p is a small enough constant.  To see that this is sufficient to reconstruct a polynomial, fix one.  For every query that the data structure makes, you will have in the encoding all the t cells needed to answer it with probability (S – t choose pS – t) / (S choose pS) = Omega(p^t).  There are |F| queries, which means you expect to be able to answer |F| p^t queries, which in turn means that there exists a set which allows you to answer that many.  If t = o(log d), the quantity |F| p^t is > d, and you get your polynomial back by simple interpolation.

This can be extended to boolean queries by considering the d^4 queries (x,a) with meaning: does the polynomial evaluated at x equal a?  One can run the same argument as above but only focusing on the queries whose answers is “yes.”

Beating this logarithmic bound strikes me as a fundamental question. Though after being in Banff the real question is why isn’t life one very long Banff workshop, where you have an endless stream of interesting talks and amazing companions for hikes, and the cafeteria serves an uncommon variety of foods — always including a choice of plain vegetables and starch with absolutely no seasoning — to consume within glass walls overlooking the rocky mountains.

Weinstein gave a survey talk about information complexity, which was followed by a great talk on the very recent work by Ganor, Kol, and Raz showing a separation between information and communication.  I hadn’t thought much about information complexity, so I can’t say I am surprised by this result, but I heard there were some researchers who believed that information equals communication.  This result has the nice philosophical interpretation that sometimes long conversations in which little information is exchanged — an experience which may be common — are necessary.

Yehudayoff gave a nice presentation about the communication complexity of disjointness, covering his simplification with Rao of a recent lower bound by Sherstov.  Sherstov’s argument first bounds the correlation of c-communication protocols with the parity of m disjoint copies of k-party disjointness on l bits, by 2^c (4^k/l)^m.  This step is similar to the classical Babai-Nisan-Szegedy lower bound for parity of ands, and although it requires a bit of extra work, it is as expected.

From this, an n/4^k lower bound for deterministic protocols follows immediately, because a protocol for disjointness implies one with correlation 2^{-m} with the above parity.  (Just set l = 10 x 4^k and note this yields the lower bound c > m = Omega(n / 4^k), for else the bound in the previous paragraph would be a lot less than the bias 2^{-m}.)

The bound for randomized protocols is more involved.  Roughly, the next step is to infer from the above bound various bounds on the correlation conditioned on the number of copies of disjointness being one.  For this, Sherstov defines and makes use of a distribution on each copy that is rerandomizable: given an instance, the players can sample fresh instances with the same value.  This step is also not too hard to grasp.  What appears to be very ingenious is the last step where you relate these bounds to disjointness itself, by showing that these protocols can be turned into a good, low-degree approximation for the and function on n bits, in the infinity norm, which is known to be impossible.  I understand it is this last step where the bulk of the simplification lies; Sherstov’s argument is replaced with a reportedly more direct argument which is basically just an appropriate linear transformation.

McGregor presented a surprising result.  Suppose n players correspond to the n nodes of a graph, and player i knows the nodes adjacent to i but does not know anything else in the graph.  It is possible for each player to send polylog(n) information to a referee who will then determine if the graph is connected (with a small error probability, taken over public coins).  The proof is just as neat as the result.  They use a classical algorithm for deciding connectivity which goes by growing a forest: at each of O(log n) rounds, each (super)node selects arbitrarily a neighbor, thus forming supernodes and shrinking the graph.  They then show how this algorithm can be run with only sketches of the neighborhoods; for this they need sketches that are linear and from which an element in the support of the original vector can be determined, which were already obtained.

Chattopadhyay spoke about his work with Edmonds, Ellen, and Pitassi on a conjecture by Patrascu.  Patrascu considered a 3-party number-on-forehead model where Alice holds k n-bit strings x_1, …, x_k, Bob holds one n-bit string y, and Charlie holds an index i <= k.  The goal is to determine f(x_i, y) for a boolean function f, with the restriction that Charlie sends an o(k)-bit private message to Alice alone, who then exclusively talks to Bob.  An inspiring connection by Patrascu shows that strong bounds in this model for functions f such as disjointness would result in breakthrough lower bounds for dynamic data structures.  Patrascu made a bold conjecture that if the communication complexity of f is high, the communication for the above task remains high.

Not only was I also thinking about this conjecture and only had made negligible headway so far, but I did not even know of their beautiful paper which disproves it in a very strong way: they exhibit a function f which requires linear randomized communication, but that can be solved with polylogarithmic communication in Patrascu’s model.  But it is still open whether strong enough bounds hold for, say, disjointness, which would be sufficient for Patrascu’s intended application to data structures.  (For deterministic protocols it is quite easy to show a strong separation for equality — you may want to try that for fun.)

And I talked about the communication complexity of addition.  Suppose each of k = O(1)  players holds an n-bit integer, and they want to know if their integers sum to 0.  Nisan lets each player send an O(log n)-bit hash of its integer, obtained by taking the remainder modulo a random prime.  This yields a protocol with O(log n) communication, whose correctness relies on the linearity of the hashing.

We obtain an O(1)-communication protocol using a different hash function which is almost linear.  This improvement is useful for other problems such as deciding if the sum is bigger than 0 or evaluating polynomial threshold functions.