The New Journal

Seminar src

Paul Beame is a Professor in the Department of Computer Science and Engineering at the University of Washington. He is known for work in logical complexity and lower bounds—in proving, for example, time-space tradeoffs. He is also interested in the practical applications of symbolic model checking for the verification of software specifications.

Today we are glad to convey the announcement he forwarded of the creation of a new open-access journal dedicated to Theoretical Computer Science.

The new journal is called TheoretiCS and lists the following distinguished endorsers who are top leaders in all of theory:

• Noga Alon

• Shafi Goldwasser

• Donald Knuth

• Robert Tarjan

• Leslie Valiant

• Moshe Vardi

• Andrew Yao

They have just thrown their page open for business today, December 1.

There used to be an independent self-publishing fair held every year in London called “Publish and Be Damned.” The association of TheoretiCS with the computing section of ArXiv might smack of self-publishing but this journal is in every further respect the opposite:

• It uses the overlay journal platform Episciences, whose mission is to “add value to these archives by attaching a scientific caution to the validated papers.”

• It has a large and capable board of editors who will work the way the other major established print and online journals do.

The Editors

Paul wrote us a direct e-mail and emphasized two points at the start (with our light editing):

1. The aim of TheoretiCS to publish articles of a very high quality, to become a reference journal on par with the leading journals in all of Theoretical Computer Science, and

2. The [internationally] inclusive view of Theoretical Computer Science that this journal represents, which is evident in the choice of two excellent co-editors-in-chief and an outstanding inaugural editorial board.

He adds that it was thanks to the leadership of Thomas Schwentick and others, including helping to gain sponsorship, and the hard work of the co-editors-in-chief, managing editors, and the rest of the Advisory Board, that this new journal launch was made possible.

The Chief Editors are:

• Javier Esparza, Technische Universität München

• Uri Zwick, Tel Aviv University.

The editorial board is:

• Martin Abadi, Google (Alphabet), USA

• Andris Ambainis, U. of Latvia

• Albert Atserias, UPC, Barcelona

• Haris Aziz, UNSW, Sydney

• David Basin, ETH, Zurich

• Patricia Bouyer, CNRS, Paris-Saclay

• Nicolo Cesa-Bianchi, Universitá di Milano

• Anuj Dawar, Cambridge University

• Luc Devroye, McGill University, Montreal

• Jacob Fox, Stanford University

• Mohsen Ghaffari, ETH, Zurich

• Georg Gottlob, Oxford University

• Anupam Gupta, Carnegie-Mellon University

• Venkatesan Guruswami, Carnegie-Mellon University

• Johan Håstad, KTH, Stockholm

• Ravi Kannan, Microsoft Research India, Bengaluru

• Anna Karlin, University of Washington, Seattle

• Ken-ichi Kawarabayashi, National Institute of Informatics, Tokyo

• Valerie King, University of Victoria

• Robert Kleinberg, Cornell University

• Naoki Kobayashi, University of Tokyo

• Elias Koutsoupias, Oxford University

• Xavier Leroy, College de France

• Katrina Ligett, Hebrew University

• Rupak Majumdar, MPI-SWS, Kaiserslautern

• Joseph Mitchell, Stony Brook University

• Mehryar Mohri, Google and New York University

• David Mount, University of Maryland

• Anca Muscholl, Université de Bordeaux

• Danupon Nanongkai, University of Copenhagen

• Moni Naor, Weizmann Institute, Rehovot

• Catuscia Palamidessi, Inria Palaiseau

• Michal Pilipczuk, University of Warsaw

• Jean-Francois Raskin, Université Libre de Bruxelles

• Peter Sanders, KIT, Karlsruhe

• Davide Sangiorgi, Universitá di Bologna

• Nitin Saxena, IIT Kanpur

• Alistair Sinclair, UC Berkeley

• Ola Svensson, EPF Lausanne

• Gregory Valiant, Stanford University

• Stephanie Weirich, University of Pennsylvania

• Virginia V. Williams, Massachusetts Institute of Technology

• James Worrell, Oxford University

• Mihalis Yannakakis, Columbia University

Why A New Journal?

Indeed. The announcement adds:

– We believe that our field (and science in general) needs more ‘virtuous’ open-access journals, a whole eco-system of them, with various levels of specialization and of selectivity. We also believe that, along with the structuring role played by conferences in theoretical computer science, we collectively need to re-develop the practice of journal publications.

There is a long, historical, good point here. Thirty years ago, David S. Johnson moved personal mountains to compile the STOC/FOCS Bibliography, whose essential subtitle (preliminary version) spoke a truth expanded in the blurb by Michael Loui:

“Many computer scientists believe, erroneously, that it is sufficient to publish their papers in conferences, particularly prestigious conferences such as STOC and FOCS—and neglect to publish them in journals. In contrast, this bibliography emphasizes the benefits of archival publication in rigorously refereed journals. Often, the journal version corrects errors, provides more details, and extends the results of the conference paper.”

ArXiv, however, has put more weight in the other end of this boat. It is the easy end to step into and ride; your humble bloggers confess a few instances ourselves. After noting he’d already used the STOC/FOCS Bibliography to locate journal versions of papers, Michael—again, writing in 1991—finished by saying,

“Compiling and maintaining [this and other similar] bibliographies would require the continual cooperation of many authors and journal editors, but the results would be worth the effort.”

We interpret what Paul is saying along these lines. It may not be a completely new kind of journal—it goes for continuity with the kind we know—or a completely new mission for a journal. But it is responding to new contexts and environments for journals, like watercraft in a 007 movie.

More Aims

The announcement also declares these purposes:

• The scope of TheoretiCS is the whole of Theoretical Computer Science, understood in an inclusive meaning (concretely: including, but not restricted to, the Theory of Computing and the Theory of Programming; or equivalently, the so-called TCS-A and TCS-B, reminiscent of Jan van Leeuwen et al.’s Handbook of Theoretical Computer Science).

• Our aim is to rapidly become a reference journal and to contribute to the unity of the Theoretical Computer Science global community. In particular, we will seek to publish only papers that make a very significant contribution to their respective fields, that strive to be accessible to a wider audience within theoretical computer science, and that are, generally, of a quality on par with the very best journals in the field.

• TheoretiCS adheres to the principles of ‘virtuous’ open-access: there is no charge to read the journal, nor to publish in it. The copyright of the papers will remain with the authors, under a Creative Commons license.

Some further points and history are given in full in the posting on Lance and Bill’s blog.

Open Problems

We are excited by the creation of TheoretiCS. We especially like the ability to freely read articles and also to freely submit articles. We look forward to see the articles that will appear in the journal. Please submit some of your new results. Good luck.

We certainly hope to see some of the following in the journal soon:

• A Super Linear Lower Bound on the Circuit Size for 3-SAT.

• A Simple Quantum Algorithm for Almost All Cases of the Halting Problem.

• Graph Isomorphism is in Polynomial Time.

What do you hope to see soon in TheoretiCS?

[Further information about principals added; less emphasis on Beame]