FOCS 2022

I am on the FOCS 2022 Program Committee, and I am overjoyed that the PC meeting will be virtual. Hopefully, the days are over when the program chair can brush aside all cost-benefit considerations, impose their backyard on far-away scholars who need service items, and then splash their offspring at the welcome party.

I am also overjoyed that we will be implementing double-blind reviews. This issue has been discussed and ridiculed at length. Admittedly, it makes it harder to adhere to Leonid Levin’s 1995 influential STOC Criteria. For example, if a reviewer wanted to trash a paper based on the fact that the authors are not in the position to judge their own work, now they’ll have to check online for talks or preprints to know who the authors are. Given the volume of reviews, it’s reasonable to expect that in some cases the reviewer won’t be able to conclusively exclude that a letter-writer is among the authors. In such a situation they can resort to writing a very long, thorough, and competent review whose most significant digit is the STOC/FOCS death sentence: weak accept.

No, I actually do have something more constructive to say about this. I was — as they say — privileged to serve on many NSF panels. As an aside, it’s interesting that there the track-record of the investigators is a key factor in the decision; in fact, according to many including myself, it should carry even more weight, rather than forcing investigators to fill pages with made-up directions most of which won’t pan out. But that’s another story; what is relevant for this post is that each panel begins with a quick “de-biasing” briefing, which I actually enjoy and from which I learnt something. For example, there’s a classic experiment where the ratio of females hired as musicians increases if auditions hide the performer behind a tent and make them walk in on carpet so you can’t tell what shoes they are wearing. Similar experiments exist that hide names from the folders of applicants, etc. What I propose is to do a similar thing when reviewing papers. That is, start with a de-biasing briefing: tell reviewers to ask themselves whether their attitude towards a paper would be different if:

  1. The authors of this paper/previous relevant work were ultra-big shots, or
  2. The authors of this paper/previous relevant work were hapless nobodies, or
  3. The proofs in this paper could be simplified dramatically to the point that even I understand them, or
  4. This result came with a super-complicated proof which I can’t even begin to follow, or

What other questions would be good to ask?

Terrible things about conferences, ICALP 2022 requiring submissions in LIPIcs style, more terrible things about conferences, and a new life

I’m on the ICALP 2022 program committee (PC) and was apparently the first to complain when I saw the draft call for papers, and I asked that the requirement that submissions must be in LIPIcs style be put to a vote. Despite substantial support among the PC for not requiring the majority of authors to squander their time formatting in an exotic style submissions that will be rejected, the Supreme Court blocked the vote. Their main rationale seems to be ensuring correspondence between submissions and proceedings. Ironically, at the same time other conferences are allowing authors to publish in proceedings an abridged version of the (accepted) submission, to make it easier to publish the paper in a journal (which may not want to have a full version already in a conference). We are at the nadir in history where human effort is systematically wasted to produce versions that do not even pretend to be useful for readers — only to check boxes.

When I was at the IAS and was briefed about logistics, I was stunned when they asked me if I type my own papers, or if I needed help with that. I guess the next level will be if you need help with formatting your submissions.

Picture a 100-year old retired scientist who followed the field for 75 years, and who wants to make one more contribution. Even though they are no match for the raw power of a 15-year old, their ability to draw connections almost makes up for it, and their perspective is invaluable to the community. This scientist, whose equipment consists of a desktop from two human generations ago, miraculously held together and kept working through sheer love and intimate knowledge, is now being asked to format their paper in LIPIcs style… or to ask someone else to do it for them (talk about fostering collaboration).

Here’s a non-exclusive list of true, terrible things about conferences, most of which were discussed earlier on this blog (see tag utopia-tcs):

  1. Requiring submissions in proceedings format.
  2. Pre-registering papers by a deadline different than the submission deadline.
  3. Requiring authors to submit a separate 2-page summary of the paper.
  4. Ultra-strict page limits, summary rejection for any deviation.
  5. Suddenly being forced on a short notice to submit a dummy .pdf so that PC assignments can be made.
  6. Extending the list of topics two days before the deadline.
  7. Moving deadlines.
  8. Forcing authors to check multiple times the call for papers and/or constantly monitor email for any of these last-minute changes.
  9. In the lucky case of acceptance, following up with a barrage of emails involving minutiae such as underfull \hbox.
  10. Writing “this only takes 60 seconds.” For me (and, apparently, many others — otherwise why delay answering emails that take 10 seconds to answer?) attending to any task, following any instruction, even “blink” or “say yes” has a huge fix cost, maybe 30 minutes. So I translate 60 seconds to 31 minutes.
  11. Hosting the conference in places which are inconvenient, for the attendees and planet earth.
  12. Hosting the conference at times which are inconvenient for the attendees.
  13. Requiring in-person PC meetings whose outcome does not justify the costs.

As usual, people in a position of power do not have much incentive to fight to change the very practices that put them in that position in the first place. But even this cynical remark doesn’t tell the whole story, since the practices got worse with time, unlike the case of journals. One impression I have is that people have gotten so used to buggy software, constant updates, and general techno slavery that they just accept all of this as another inevitable misery in life… and by far not the worst! This last point is important, as I think a seeping philosophy that permeates much of the discussion and the decisions is that much more important things are at stake, so who cares about this? If you really want to spend cycles fixing something, then what about X? (It’s fun to think where you end up if you stretch this point.) But another life is possible.

One day, I will throw in my two cents and launch a new journal. Besides being electronic and free (like ToC) it will have the following features.

  1. Papers, if accepted, will appear in the authors’ chosen format. No conversion, and no additional effort, will be required for publication. All the effort will be exclusively directed at improving the content of the paper.
  2. Submissions can be by pdf attachment or by overlay, but not only to arxiv: to *any* repository. In particular, authors will not be required to get their paper to compile on the arxiv.
  3. The identities of the reviewers will be made public (in case of acceptance). This I am still debating, but so far I am leaning towards it. The problem that this is trying to address is that while you get reputation points for being on a program committee or on an editorial board, you don’t get many for being an unknown journal referee who is actually supposedly doing the hard work or finally really checking the proofs. Instead with public identities people can show off the hard work and their role in the community, as happens on more recent platforms like say stackexchange.
  4. Authors will be free to submit anonymously, or not. This choice will be made by the authors, not dictated by a committee.
  5. And perhaps the most consequential thing that I am still debating, should all submissions be public? (Maybe not.)

To finish on a high note, a great thing about conferences is the fast turn-around. It is really depressing — in other fields — to have to wait so long for any quantifiable feedback on your work, and this is definitely something which I liked about the TCS community. But, to come back to the mood of the post, this good aspect (and others) of conferences can probably be kept while rethinking the not so good. (For example, there could be a journal with deadlines similar to conferences, which is also what happens for grant proposals etc.)

Submitting to ICALP 2021

I am taking advantage of the pandemic to participate in conferences where it’s usually hard for me to participate because they require intercontinental travel. I have a paper in CSR 2021, and now am submitting a paper to ICALP 2021 (I count submission as participation, even in case the paper gets rejected). The latter requires submissions to be formatted in a specific way, a topic discussed at length on this blog.

Begin 12:48

Download the LIPICs package.

Try to compile their sample paper.

Get error message: ! LaTeX Error: File `l3backend-dvips.def’ not found.

Google solution. Says to install packages.

Unfortunately, I am using windows but I only have LyX, and the solution expects MixTeX.

Google how to install packages in LyX.

Can’t find anything simple.

Create a new document on overleaf.

Copy all the LIPIcs files there.

Try to compile their sample.

It works!

Paste my latex.

Usual avalanche of problems to be fixed at the speed of light.

Add dummy section “Introduction” which wasn’t in my paper, otherwise theorem numbers look weird.

Numbers still look weird. Something’s wrong with theorem statements.

Replace {thm} with {theorem}

Looks better. Still some wrong stuff all around, however.

No it wasn’t that. Remove the dummy section. It seems their “paragraph” environment puts strange numbers like

Replace \paragaph with \paragaph* everywhere

Actually, looks weird the way they put the ack– put back the dummy Introduction section.

Check page limit: no more than 12 pages, excluding references

I’m a little over. Does this really matter? Apparently, it does! Move last proof to the appendix. Actually, last proof is kind of short, I should move the penultimate proof. Update paper organization (next time I shouldn’t put it).

Final look. Fix a few indentations.

OK, time to actually submit. Go to the easychair website. They want me to re-enter all the information!? Why, after forcing me to enter title, keywords, etc. in their format, are they asking me to do this again? Can’t we just send the .tex file and extract it from there?

Oh come one, it’s just a few seconds of copy-paste.

OK, done, paper submitted.

End: 3:05

Well, next time it will be easier. Perhaps easier, but not easy because as the reader knows there will be another missing package, another incompatible system, etc. And of course, if the paper is rejected, then I won’t even save the time to convert it into camera-ready format. On the other hand, the benefit is non-existent. It would be better for everyone if in order to submit a paper you have to complete a random 1-hour task on Amazon mechanical Turk and donate the profit to charity.

Et Al. II

From Thoughts, :

The et al. citation style favors scholars whose last name comes early in the dictionary. For example, other things equal, a last name like Aaron would circulate a lot more than Zuck. This problem is compounded by the existence of highly-cited papers which deviate from alphabetical ordering of authors. They carry the message: order matters, and some of you can’t use this trick, vae victis!

My suggestion is to avoid et al. and instead spell out every name (as in Aaron and Zuck) or every initial (as in AZ). It isn’t perfect, but improvements like randomly permuting the order still aren’t easy to implement. The suggestion actually cannot be implemented in journals like computational complexity which punish the authors into using an idiosyncratic style which has et al. But it doesn’t matter too much; nobody reads papers in those formats anyway, as we discussed several times.

From the STOC 2021 call for papers:

Authors are asked to avoid “et al.” in citations in favor of an equal mention of all authors’ surnames (unless the number of authors is very large, and if it is large, consider just using \cite{} with no “et al.”). When not listing authors’ names, citations should preferably include the first letters of the authors’ surnames (or at least the first three followed by a +, and possibly the year of publication). If using BibTeX, this can be accomplished by using \bibliographystyle{alpha}.

Previous vs. concurrent/independent work

Should Paper X cite Paper Y as previous or concurrent/independent work? This is sometimes tricky: maybe Paper Y circulated privately before Paper X, maybe the authors of Paper X knew about Paper Y maybe not — nobody can know for sure. One can say that the authors of Paper Y should have posted Paper Y online earlier to prevent this issue, but that is not standard practice and might lead to other problems, including Paper Y never getting published!

I propose the following guiding principle:

“If a different accept/reject outcome would have forced paper X to cite paper Y as previous work, then paper X should cite paper Y as previous work.”

The reasons behind my principle seem to me especially valid in the fast-moving theoretical computer science community, where papers are typically sent to conferences and thus seen by the entire program committee plus around 3 external referees, who are typically experts — only to be rejected. Moreover, the progress is extremely fast, with the next conference cycle making obsolete a number of papers in just the previous cycle.

Conferences in an Era of Expensive Carbon

At least there’s that: I live in a world where some people care about it and publish their viewpoint in the latest CACM. Read it on your next flight. Some interesting things that won’t shock anyone:

There’s a nice picture with different environmental costs based on the location of the conference. It also shows that people like to go to nearby conferences, one of the reasons why “The impulse to ignore the issue is entirely understandable.” For more perspective see some of our earlier posts for example here and here.

The viewpoint also reports on a recent switch from in-person to online program committees for flagship conferences (POPL and ICFP), following a recent trend. For starters we continue to suggest that STOC and FOCS do the same, because the nature of decisions does not justify the cost. The latter post also includes hard numbers on the added value of a physical meeting (with respect to accept/reject decisions — of course one can value at infinity meeting in person luminaries in your field, but that can be done in other ways and should not be tied to PC meetings).

Publish and perish

Moshe Vardi’s latest insight in the Communications of the ACM (whose title we adopt for this post) agrees with our previous post “Because of pollution, conferences should be virtual.” Vardi calls for “sweeping policy change […] requiring that authors of accepted papers that must fly to participate in a conference may opt out from in-person involvement and contribute instead by video.” Vardi gives some indication of the environmental impact of the travel-based system, and further suspects that in-person conference participation is “much less valuable than we would like to believe.”

These issues are closely related to the decades-old discussion of journals vs. conferences. Several older posts on this blog were devoted to that. Lance Fortnow, back in 2009, wrote that it’s Time for computer science to grow up. The full text of this article is premium content, but you can read a pre-publication version here. Basically, he argues in favor of a journal-based publication system.

Apparently in response, judging from the title, Boaz Barak wrote a piece titled Computer science should stay young. I can’t quickly find a link to the whole thing, but his bottom line is online “I disagree with the conclusion that we should transition to a classical journal-based model similar to that of other fields. I believe conferences offer a number of unique advantages that have helped make computer science dynamic and successful, and can continue to do so in the future.”

I disagree that conferences are young. They belong to the BI (before internet) era, and so look rather anchored in the past to me. Historically, I also suppose in-person discussion predates writing, though this is irrelevant. What is young is the health impact of pollution (Fortnow and Barak’s pieces don’t touch on health issues). (By health impact I include climate change, but I prefer not to use that term for various reasons.)

And what is young and cool is arxiv overlay journals, TCS+ talks, videoconferences, ECCC, etc.

Instead, we impose on our community most inconvenient transoceanic flights. To end I’ll quote from Oded Goldreich’s my choices:

Phoenix in June: […] One must be out of their mind to hold a conference under such weather conditions. I guess humans can endure such weather conditions and even worse ones, but why choose to do so? Why call upon people from all over the world to travel to one of the least comfortable locations (per the timing)?

Because of pollution, conferences should be virtual

Perhaps conferences made sense fifty years ago. We did not have internet, and the pollution was not as bad. Today, we can have effective virtual meetings, while the pollution has reached a level of crisis, see this moving talk by Greta_Thunberg. Moving to a system of virtual conferences is I believe a duty of every scientist. Doing so will cut the significant air travel emissions that come from shipping scientists across the world. To attend a climate summit in the USofA, Greta will sail across the Atlantic ocean on a zero emission boat.

We can keep everything the way it is, but simply give the talks online. This change doesn’t involve anybody higher up in the political ladder. It only involves us, the program chairs, the steering committees.

While we wait for that, we can begin by virtualizing the physical STOC/FOCS PC meetings, whose added value over a virtual meeting, if any, does not justify the cost; and by holding conferences where the center of mass is, instead of exotic places where one can combine the trip with a vacation at the expense of tax payers’ money and everybody’s health. And that is also why I put a bid to hold the 2021 Conference on Computational Complexity in Boston.

NSF panels, making decisions worth millions, routinely have virtual panelists (I was the last few times). So why do we insist on shipping scientists across the globe multiple times a year to give 15-minute talks which to most people are less useful than spending 20 minutes reading the paper on the arxiv?

Child Care at STOC 2018

The organizers asked me to advertise this and I sympathize:

We are pleased to announce that we will provide pooled, subsidized child care at STOC 2018. The cost will be $40 per day per child for regular conference attendees, and $20 per day per child for students.
For more detailed information, including how to register for STOC 2018 childcare, see

Ilias Diakonikolas and David Kempe (local arrangements chairs)

Et al.

The et al. citation style favors scholars whose last name comes early in the dictionary. For example, other things equal, a last name like Aaron would circulate a lot more than Zuck. This problem is compounded by the existence of highly-cited papers which deviate from alphabetical ordering of authors. They carry the message: order matters, and some of you can’t use this trick, vae victis!

My suggestion is to avoid et al. and instead spell out every name (as in Aaron and Zuck) or every initial (as in AZ). It isn’t perfect, but improvements like randomly permuting the order still aren’t easy to implement. The suggestion actually cannot be implemented in journals like computational complexity which punish the authors into using an idiosyncratic style which has et al. But it doesn’t matter too much; nobody reads papers in those formats anyway, as we discussed several times.