Month: July 2017

STOC/FOCS PC meetings: Does nature of decisions justify cost?

I am just back from the FOCS 2017 program committee (PC) meeting. This is my second time attending a physical PC meeting, both times for FOCS. In the past I was sorry that I had to decline some invitations for personal reasons. Just like the previous instance, I was impressed with the depth and thoroughness of the discussion. I also had a great time sitting in the same room with so many esteemed colleagues, chatting about what’s cool in the new research papers, and cracking nerdy jokes. It is also a privilege for me to hear what everyone has to say about what is going on. I even managed to have some quick research meetings here and there. During the flight I even proved a great theorem watched Trainspotting 2. And I had never been to Caltech: it is a great place with a moving history as told by the book in the drawer next to my bed in the Athenaeum.

However in the rest of the post I want to address the title. Throughout, by “PC meetings”, I mean “physical” meetings as opposed to “virtual.” Before I start, I want to stress two things. First, what I am about to say has absolutely nothing to do with this or any specific STOC/FOCS PC meeting, rather it is aimed to PC meetings in general. Second, I am not saying that the decisions made are “bad.” Indeed I don’t think a substantially better way to make decisions exists (here and in many other cases).

First, the experiment. As mentioned in a previous post, this time around I ran a little experiment: Right before the meeting started, I saved the ranking of the papers, based on the reviews and the offline discussion, weighted by confidence. Then I compared it with the final decisions at the end of the meeting (with the knowledge of the total number of papers accepted). There is a handful of papers that I have a conflict with and so I don’t know about. Those I know about number 88. The two lists of 88 papers have edit distance 19, meaning that you need to change 19 papers in one list to get the other list. This is a 0.216 fraction of the papers. I consider this number negligible. Note that it is based on information that was entered in expectation of resolving many things during the meeting: extra rounds of offline discussion would have probably calibrated this much better. Think also how this compares with the NIPS experiment. In that case, the two lists of 37 papers have edit distance 21 (plus or minus one), which is a lot larger than the above. However STOC/FOCS decisions may be more “stable” than NIPS (would be fun to have any data on this).

A common experience is also that a large fraction of papers is a clear reject, a small fraction is a clear accept, and the rest are more or less rated like novels or movies; and I am not aware of a better rating scheme.

Second, how the decisions are made. I am not sure that decisions made during the meeting are significantly better than decisions made offline (I will use the word “offline” to mean “not in a physical meeting”). A meeting can start at 8:30AM and go past 6PM, with total break time about 1 hour. Many people are also jet lagged or exhausted. Working offline may be better. Sure, in a physical meeting you can literally grab someone by the arm and ask: Do you really think X should be accepted given Y? But in general there is very little time for this. On the other hand, in an offline discussion you can say: OK, we need a little extra expertise on papers x, y, z: reviewer w, please dig into it and report (happened to me). This supposedly should also take place before the physical meeting, but I think it’s done less than it should be, because the feeling is that we are going to have a meeting anyway so we might as well resolve this then. Instead what happens at times during the meeting is that expertise is missing, and there’s just no time to remedy. Sometimes, the in-person decision process can be rather chaotic. I want to stress again that I am not saying that *any* PC is not run well. My point is that this is the nature of the hard decisions that we need to make. Of course, email conversations can get very tedious. And you can also say that if there’s no threat of a physical meeting people feel less pressure to write good reviews and make good decisions, though that’s not my experience from SODA/CCC program committees. A good model could be to have a virtual meeting, with all the participants present at the same time. This could be done early on, and in fact having two such meetings could be the best thing. At my institutions we have many, many meetings virtually. During such meetings, you can still stare at someone in the camera and ask: Do you really think X should be accepted given Y?

There are many venues where decisions are made offline, such as CCC/CRYPTO/SODA/JACM/SICOMP. One can say that STOC/FOCS are more important than CCC/CRYPTO/SODA, but it’s hard to say that they are more important than say JACM. An argument is then that journal decisions are different because they involve a lot more time and care. I tend to disagree with this last point. My impression is that journal and conference reviews are rather indistinguishable when it comes to computing the accept/reject bit. The difference is only in the second-order term: journals can spend more time on details and style.

Third, the location. This meeting was held at Caltech. The Theory festival at Montreal ended with a full day of amazing tutorials on friday. The festival is promoted as a “must-attend” event. So what we are telling the program committee is this: “Look, you really gotta attend the theory festival. If you need to attend anything at all this year, that’s the meeting! Oh, and right after that (4PM) please catch a red-eye Montreal-LAX, and be ready to start at 8:30 AM on Saturday.” Personally, I wanted to attend the theory fest, but I just couldn’t to the above. So I skipped it in favor of the PC meeting.

If we really need to have physical meetings, I think we should combine them with some other popular event, or at least put them where the center of mass is. Typically, none of this happens, and the tradition seems to be that the meeting is held where the PC chair works, which may not even be where the conference is. I am not the only one who feels so, by the way, about this point and the others. In particular a past program committee in an act of rebelion organized a conference for themselves and co-located it with the PC meeting. But that’s unusual, and it’s clearly better to co-locate with the existing events, since attendance is already an issue. One argument is that the PC chair can offer a nice room with lots of support, which is hard to find elsewhere. I think this argument does not stand. The “support” consists in everybody bringing their laptops (an example of “downfall of mankind” discussed earlier), and wireless. I don’t think it’s so hard to get a room with a table and wireless in a hotel or another university. Finally, I think these meetings favor the United States even more disproportionately so than the conference itself. Indeed, STOC/FOCS are at least once in a while held elsewhere (one was in Rome, for example — I didn’t go). I’ve never heard of a meeting done abroad, would be curious to know.

I am told that this year TCC has a physical meeting (not always the case) but that it is co-located with CRYPTO, a conference typically attended by most of the crypto community. This makes sense to me.

Look at some recent STOC/FOCS PC, and think of the cost of flying everybody to the meeting, and think of the result.

Fourth, the time. As discussed earlier, do we really have to hold such meetings during week-ends? Especially in the summer, I don’t know of a reason for this. Why not Tuesday to Thursday? People don’t teach, departments are empty, and flying is less chaotic. Plus maybe you want to spend your summer week-ends going to the beach instead of being shut in a windowless room with dozens of laptops? An argument is that international flights are sometimes cheaper if you stay during the week-end. I am not sure this really makes a difference, for a number of reasons (including: not so many people from abroad, and they typically stay extra days anyway).

Synthesis.

My impression is that things are done this way mostly because of inertia: This is how it’s been done, and now good luck changing it. Also, being a STOC/FOCS chair is (or is close to) a once-in-a-lifetime appointment, which clearly one doesn’t want to screw up. Another argument I heard is that physical meetings are a better way to preserve tradition. That is, a young member of the PC learns better the trade through physical interaction.

If you put all the above things together, my impression is that the answer to the title is “no.” The resources are probably enough for at least a fraction of a postdoc, or they could be used to allow more people to actually attend the conference. My concrete proposal is to have the next meeting offline, with a mixture of desynchronized discussion and virtual synchronized meetings. At least, we should try.

Bounded independence fools And

One of the earliest (and coolest) results in pseudorandomness is the following theorem that shows that k-wise independence “fools” the And function.

Theorem 1. [1] Let x_{1},x_{2},\ldots ,x_{n} be k-wise independent distributions over \{0,1\}. Then

\begin{aligned} |\mathbb {E}[\prod _{i\le n}x_{i}]-\prod _{i\le n}\mathbb{E} [x_{i}]|\le 2^{-\Omega (k)}. \end{aligned}

Proof. First recall that the inclusion-exclusion principle shows that for any random variables y_{1},y_{2},\ldots ,y_{n} jointly distributed over \{0,1\}^{n} according to a distribution D we have (write Or_{i} for the Or function on i bits);

\begin{aligned} \mathbb{E} \prod _{i\le n}y_{i} & =1-\mathbb{E} \text {Or\ensuremath {_{i}}}(1-y_{i})\nonumber \\ & =1-\sum _{j=1}^{n}T_{j}~~~~(1) \end{aligned}

where

\begin{aligned} T_{j}=(-1)^{j}\sum _{S\subseteq [n],|S|=j}\mathbb{E} \prod _{i\in S}1-y_{i}. \end{aligned}

Moreover, if we truncate the sum in Equation (1) to the first t terms, it gives either a lower bound or an upper bound depending on whether t is odd or even.

Because this holds under any distribution, if we show that the right-hand side of Equation (1) is approximately the same if the y_{i} are n-wise independent and k-wise, then the left-hand sides of that equation will also be approximately the same in the two scenarios, giving the result. (Note that \prod _{i\le n}\mathbb{E} [x_{i}] equals the expectation of the product of the x_{i} if the latter are n-wise independent.)

Now, since the terms T_{j} only involve expectations of the product of at most j variables, we have that they are the same under n-wise and k-wise independence up to j=k. This would conclude the argument if we can show that |T_{k}| is 2^{-\Omega (k)} (since this is the quantity that you need to add to go from a lower/upper bound to an upper/lower bound). This is indeed the case if \sum _{i\le n}\mathbb{E} [1-x_{i}]\le k/2e because then by McLaurin’s inequality we have

\begin{aligned} |T_{k}|=\sum _{S\subseteq [n],|S|=k}\prod _{i\in S}\mathbb{E} [1-x_{i}]\le (e/k)^{k}(\sum _{i\le n}\mathbb{E} [1-x_{i}])^{k}\le 2^{-k} \end{aligned}

where the first equality holds because the x_{i} are k-wise independent.

There remains to handle the case where \sum _{i\le n}\mathbb{E} [1-x_{i}]>k/2e. In this case, the expectations are so small that even running the above argument over a subset of the random variables is enough. Specifically, let n' be such that \sum _{i\le n}\mathbb{E} [1-x_{i}]=k/2e (more formally you can find an n' such that this holds up to an additive 1, which is enough for the argument; but I will ignore this for simplicity). Then the above argument still applies to the first n' variables. Moreover, the expectation of the product of just these n' variables is already fairly small. Specifically, because the geometric mean is always less than the arithmetic mean (a fact which is closely related to McLaurin’s inequality), we have:

\begin{aligned} \prod _{i\le n'}\mathbb{E} [x_{i}]\le (\frac {1}{n'}\sum _{i\le n'}\mathbb{E} [x_{i}])^{n'}\le (\frac {1}{n'}(n'-k/2e))^{n'}\le (1-k/2en')^{n'}\le 2^{-\Omega (k)}. \end{aligned}

Since under any distribution the expectation of the product of the first n variables is at most the expectation of the product of the first n', the result follows. \square

An interesting fact is that this theorem is completely false if the variables are over \{-1,1\} instead of \{0,1\}, even if the independence is n-1. The counterexample is well-known: parity. Specifically, take uniform variables and let x_{n}=\prod _{i<n}x_{i}. What may be slightly less known is that this parity counterexample also shows that the error term in the theorem is tight up to the constant in the \Omega . This is because you can write any function on t bits as the disjoint union of 2^{t} rectangles.

A side aim of this post is to try a new system I put together to put math on wordpress. I’ll test it some more and then post about it later, comparing it with the alternatives. Hopefully, my thinking that it was the lack of this system that prevented me from writing math-heavier posts was not just an excuse to procrastinate.

References

[1]   Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, and Boban Velickovic. Approximations of general independent distributions. In ACM Symp. on the Theory of Computing (STOC), pages 10–16, 1992.