Friday, May 06, 2022

HALG 2022: Call for participation

I am posting this call for participation on behalf of Keren Censor-Hillel, PC chair for HALG 2022. I expect that many colleagues from the Track A community will attend that event and enjoy its mouth-watering scientific programme.

 

7th Highlights of Algorithms conference (HALG 2022)
The London School of Economics and Political Science, June 1-3, 2022
https://www.lse.ac.uk/HALG-2022


The Highlights of Algorithms conference is a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of invited talks, as well as the possibility for all researchers and students to present their recent results through a series of short talks and poster presentations. Attending the Highlights of Algorithms conference will also be an opportunity for networking and meeting leading researchers in algorithms.

For local information, visa information, or information about registration, please contact Tugkan Batu t.batu@lse.ac.uk.—
 

PROGRAM

A detailed schedule and a list of all accepted short contributions is available at https://www.lse.ac.uk/HALG-2022/programme/Programme

REGISTRATION

https://www.lse.ac.uk/HALG-2022/registration/Registration

Early registration (by 20th May 2022)

Students: £100
Non-students: £150

Late registration (from 21st May 2022)
Students: £175
Non-students: £225

Registration includes the lunches provided, coffee breaks, and the conference reception.

There are some funds from conference sponsors to subsidise student registration fees. Students can apply for a fee waiver by sending an email to Enfale Farooq (e.farooq@lse.ac.uk) by 15th May 2022. Those students presenting a contributed talk will be given priority in allocation of these funds. The applicants will be notified of the outcome by 17th May 2022.

INVITED SPEAKERS

Survey speakers:

Amir Abboud (Weizmann Institute of Science) 
Julia Chuzhoy (Toyota Technological Institute at Chicago)
Martin Grohe (RWTH Aachen University)
Anna Karlin (University of Washington)
Richard Peng (Georgia Institute of Technology)
Thatchaphol Saranurak (University of Michigan)

Invited talks:

Peyman Afshani (Aarhus University)  
Soheil Behnezhad (Stanford University)  
Sayan Bhattacharya (University of Warwick)
Guy Blelloch (Carnegie Mellon University)
Greg Bodwin (University of Michigan)
Mahsa Eftekhari (University of California, Davis)
John Kallaugher (Sandia National Laboratories)
William Kuszmaul (Massachusetts Institute of Technology)
Jason Li (Carnegie Mellon University)
Joseph Mitchell (SUNY, Stony Brook)
Shay Moran (Technion)
Merav Parter (Weizmann Institute of Science)
Aviad Rubinstein (Stanford University)
Rahul Savani (University of Liverpool)
Mehtaab Sawhney (Massachusetts Institute of Technology)
Jakub Tetek (University of Copenhagen)
Vera Traub (ETH Zurich)
Jan Vondrak (Stanford University)
Yelena Yuditsky (Université Libre de Bruxelles) 

Saturday, March 12, 2022

FOCS 2021 Test-of-Time Award winners (and one deserving paper that missed out)

As members of the TCS community will most likely know, FOCS established Test-of-Time Awards from its 2021 edition to celebrate contributions published at that conference 30, 20 and 10 years before. The first list of selected winners is, as one might have expected, stellar:

  • Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
    Approximating Clique is Almost NP-Complete.
    FOCS 1991
  • David Zuckerman:
    Simulating BPP Using a General Weak Random Source.
    FOCS 1991
  • Serge A. Plotkin, David B. Shmoys, Éva Tardos:
    Fast Approximation Algorithms for Fractional Packing and Covering Problems.
    FOCS 1991
  • Ran Canetti:
    Universally Composable Security: A New Paradigm for Cryptographic Protocols.
    FOCS 2001
  • Boaz Barak:
    How to Go Beyond the Black-Box Simulation Barrier.
    FOCS 2001
  • Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao:
    Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.
    FOCS 2001
  • Zvika Brakerski, Vinod Vaikuntanathan:
    Efficient Fully Homomorphic Encryption from (Standard) LWE.
    FOCS 2011

FWIW, I offer my belated congratulations to all the award recipients, whose work has had, and continues to have, a profound influence on the "Volume A" TCS community. 

Apart from celebrating their achievement, the purpose of this post is to highlight a paper from FOCS 1991 that missed out on the Test-of-Time Award, but that, IMHO, would have fully deserved it. 

I am fully aware that the number of deserving papers/scientists is typically larger, if not much larger, than the number of available awards. Awards are a scarce resource! My goal with this post is simply to remind our community (and especially its younger members) of a seminal contribution that they might want to read or re-read.

The paper in question is "Tree automata, mu-calculus and determinacy" by Allen Emerson and Charanjit S. Jutla, which appeared at FOCS 1991. (Emerson shared the 2007 A.M. Turing Award for the invention of model checking and Jutla went on to doing path-breaking work in cryptography.) That paper is absolutely fundamental for the mu-calculus, but also for automata theory, and verification in general. It introduced many ideas and results that became the basis for extensive research.

As a first contribution, the article introduced parity games and proved their fundamental properties. The parity condition was a missing link in automata theory on infinite objects. It made the whole theory much simpler than that proposed in earlier work. Technically, the parity condition is both universal and positional. Universal means that tree automata with parity conditions are as expressive as those with Rabin or Muller conditions. Positional means that in the acceptance game if a player has a winning strategy then she has one depending only on the current position and not on the history of the play so far. This is a huge technical advance for all automata-theoretic constructions and for the analysis of infinite-duration games. It allows one, for instance, to avoid the complicated arguments of Gurevich and Harlington in their seminal STOC 1982 article, which were already a huge simplification of Rabin's original argument from 1969 proving the decidability of the monadic second-order theory of the infinite binary tree and much more. In passing, let me remark that Rabin has gone on record saying that "I consider this to be the most difficult research I have ever done." See this interview in CACM. 

The second main contribution of that paper is the discovery of the relation between parity games and the mu-calculus. The authors show how a mu-calculus model-checking problem can be reduced to solving a parity game, and conversely, how the set of winning positions in a parity game can be described by a mu-calculus formula. This result is the birth of the "model-checking via games" approach. It also shows that establishing a winner in parity games is contained both in NP and in co-NP. As a corollary, the model-checking problem is as complex as solving games. It is still not known if the problem is in PTIME. A recent advance from STOC'17 gives a quasi-polynomial-time algorithm. (See this blog post for a discussion of that result, which received the STOC 2017 best paper award and was immediately followed up by a flurry of related papers.) 

Finally, the paper also shows how to prove Rabin's complementation lemma, which is the most difficult step in his celebrated aforementioned decidability result, with the help of parity conditions. The proof is radically simpler than previous approaches. The paper puts this contribution most prominently, but actually the conceptual and technical contributions presented later in the paper turned out to be most important for the community. 

Overall, the above-mentioned paper by Emerson and Jutla is a truly seminal contribution that has stood the test of time, has sown the seeds for much research over the last thirty years (as partly witnessed by the over 1,130 citations it has received so far) and is still stimulating advances at the cutting edge of theoretical computer science that bridge the Volume A-Volume B divide. 

I encourage everyone to read it!

Acknowledgement: I have learnt much of the content of this post from Igor Walukiewicz. The responsibility for any infelicity is mine alone.

Sunday, March 06, 2022

HALG 2022: Call For Submissions of Short Contributed Presentations

On behalf of Keren Censor-Hillel, PC chair for HALG 2022, I am happy to post the call for submissions of short contributed presentations for that event. I encourage all members of the algorithms community to submit their contributed presentations. HALG has rapidly become a meeting point for that community in a relaxed workshop-style setting.

The 7th Highlights of Algorithms conference (HALG 2022) 

London, June 1-3, 2022 

https://www.lse.ac.uk/

HALG-2022 The Highlights of Algorithms conference is a forum for presenting the highlights of recent developments in algorithms and for discussing potential further advances in this area. The conference will provide a broad picture of the latest research in algorithms through a series of invited talks, as well as the possibility for all researchers and students to present their recent results through a series of short talks and poster presentations. Attending the Highlights of Algorithms conference will also be an opportunity for networking and meeting leading researchers in algorithms.  

Call For Submissions of Short Contributed Presentations: The HALG 2022 conference seeks submissions for contributed presentations. Each presentation is expected to consist of a poster and a short talk (serving as an invitation to the poster). There will be no conference proceedings, hence presenting work already published at a different venue or journal (or to be submitted there) is welcome. 

If you would like to present your results at HALG 2022, please submit their details: the abstract, the paper and the speaker of the talk via EasyChair: https://easychair.org/conferences/?conf=halg2022 

The abstract should include (when relevant) information where the results have been published/accepted (e.g., conference), and where they are publicly available (e.g., arXiv). All submissions will be reviewed by the program committee, giving priority to work accepted or published in 2021 or later. 

Submissions deadline: March 27, 2022. 

Acceptance/rejection notifications will be sent in early April.

Friday, March 04, 2022

Combinatorial Exploration: An algorithmic framework to automate the proof of results in combinatorics

Are you interested in combinatorial mathematics? If so, I am happy to welcome you to the future! 

I am proud to share with you a new, 99-page preprint by three colleagues from my department (Christian Bean, Émile Nadeau and Henning Ulfarsson) and three of their collaborators (Michael Albert, Anders Claesson and Jay Pantone) that is the result of years of work that led to the birth of Combinatorial Exploration. Combinatorial Exploration is an algorithmic framework that can prove results that so far have required the ingenuity of human combinatorialists. More specifically, it can study, at the press of a button, the structure of combinatorial objects and derive their counting sequences and generating functions. The applicability and power of Combinatorial Exploration are witnessed by the applications to the domain of permutation patterns given in the paper. My colleagues use it to re-derive hundreds of results in the literature in a uniform manner and prove many new ones. See the Permutation Pattern Avoidance Library (PermPAL) and Section 2.4 of the article for a more comprehensive list of notable results. The paper also gives three additional proofs-of-concept, showing examples of how Combinatorial Exploration can prove results in the domains of alternating sign matrices, polyominoes, and set partitions. Last, but by no means least, the github repository at https://github.com/PermutaTriangle/comb_spec_searcher contains the open-source python framework for Combinatorial Exploration, and the one at https://github.com/PermutaTriangle/Tilings contains the code needed to apply it to the field of permutation patterns. 

 "Det er svært at spå, især om fremtiden", as Niels Bohr and Piet Hein famously said. However, let me stick my neck out and predict that this work will have substantial impact and will be the basis for exciting future work. 

 Congratulations to my colleagues! With my department chair hat on, I am very proud to see work of this quality stem from my department and humbled by what my colleagues have achieved already. As an interested observer, I am very excited to see what their algorithms will be able to prove in the future. For the moment, let's all enjoy what they have done already.

Wednesday, December 15, 2021

Call for Invited Talk Nominations: 7th Highlights of Algorithms conference (HALG 2022)

On behalf of Keren Censor-Hillel, PC chair for HALG 2022, I am happy to post the call for invited talk nominations for that event. I encourage all members of the algorithms community to submit their nominations. HALG has rapidly become a meeting point for that community in a relaxed workshop-style setting. 

Call for Invited Talk Nominations
 
7th Highlights of Algorithms conference (HALG 2022)
 
LSE London, June 1-3, 2022


The HALG 2022 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research appearing in a paper in 2021 or later.
 
To nominate, please email halg2022nominations@gmail.com the following information in plaintext only:

  • Basic details: title of paper, authors, conference/arxiv links, suggested speaker.
  • Brief justification: Focus on the benefits to the audience, e.g., quality of results, importance/relevance of topic, clarity of talk, speaker’s presentation skills.


Nominations will be reviewed by the Program Committee to select speakers that will be invited to the conference.
Nomination deadline: January 14, 2022
 
Please go to https://highlightsofalgorithms.org/ for general information on HALG and for information about previous HALG meetings.
 
Keren Censor-Hillel
PC chair for HALG 2022



Tuesday, December 14, 2021

Faculty positions in Computer Science at Reykjavik University

The Department of Computer Science at Reykjavik University invites applications for full-time, permanent faculty positions at any rank in the fields of Software Engineering, and Design and Development of Computer Games. Outstanding candidates in other areas of Computer Science are encouraged to apply as well. 

We are looking for energetic, highly qualified academics with a proven international research record and excellent potential in their field of study. The primary evaluation criterion is scientific quality. We particularly welcome applications from researchers who have a strong network of research collaborators, can strengthen internal collaborations within the department, have the proclivity to improve their academic environment and its culture, and generally have potential to flourish in our environment.

Apart from developing their research career, the successful applicants will play a full part in the teaching and administrative activities of the department, teaching courses and supervising students at both graduate and undergraduate level. Applicants with a demonstrated history of excellence in teaching are preferred. Salary and rank are commensurate with experience. Among other benefits, Reykjavik University offers its research staff the option to take research semesters (sabbaticals) after three years of satisfactory teaching and research activity. The positions are open until filled, with intended starting date in August 2022. Later starting dates can be negotiated. 

The deadline for applications is January 30, 2022. The review of the applications will begin in late January 2022, and will continue until the positions are filled.

See here for full details and information on how to apply. 

Near-Optimal Distributed Degree+1 Colouring

If you are interested in graph colouring, and specifically in distributed algorithms for that classic problem, I strongly recommend the recent paper posted by Magnús M. Halldórsson, Fabian Kuhn, Alexandre Nolin and Tigran Tonoyan. (For the record, three of the authors work, or have worked, in my department at Reykjavik University, so I am biased.) 

The above-mentioned paper addresses the problem of finding a proper colouring of a graph when each node v has a palette of degree(v)+1 colours at its disposal. The paper resolves an open problem in distributed colouring and simplifies known results in doing so. As a byproduct of their results, the authors obtain improved streaming and sub-linear time algorithms. See the paper for much more information on the context for this result and the technical details. 

Congratulations to the authors!

Saturday, December 04, 2021

TheoretiCS: A new open-access journal in Theoretical Computer Science

I am delighted to share with all the readers of this blog the news of the launch of TheoretiCS, a new, top-quality, open-access journal dedicated to the whole of Theoretical Computer Science. The journey leading to the establishment of this new journal has been long and the fact that this path eventually reached its destination is due to the sterling efforts and foresight of a number of people within our community. The seeds of TheoretiCS were sown within the Council of the European Association for Theoretical Computer Science during my two terms as president of that association. At that time, Jos Baeten and Antonin Kucera worked hard to try and set up an open-access journal of the association. That journal never saw the light of day, but the process that eventually led to TheoretiCS was afoot. After some time, Thomas Schwentick took the baton in the relay race and took decisive steps in turning the establishment of this new journal into a true community effort. It is fair to say that the launch of this journal has involved an unprecedented level of cooperation amongst representatives of leading conferences from across the entire Theoretical Computer Science community. I am immensely grateful to everyone who participated in that work for the effort they put into making TheoretiCS a reality and apologise for not mentioning all the colleagues who contributed explicitly in this post. You can find more information on TheoretiCS in the text below, which I received from Jos Baeten, founding member-at-large of the Advisory Board of the Theoretics Foundation. 

So, what can you do to support this new journal? There are at least two things that each of us can do and that I believe are important. 

  1. Help TheoretiCS reach its quality objectives by submitting your best work to it and by encouraging your colleagues to do so too. TheoretiCS aims at publishing articles of a very high quality, and at becoming a reference journal on par with the leading journals in the area. To be accepted, a paper must make a significant contribution of lasting value to a relevant area of TCS, and its presentation must be of high quality. This is elaborated upon in the guiding principles spelled out below. I let you reach your own conclusions about the quality and the breadth of the editorial board of TheoretiCS, which is stellar IMHO.
  2. Spread the news of the launch of TheoretiCS within your networks. Despite its many years of existence and the role it plays within our community, I still meet colleagues (even in Theoretical Computer Science) who do not know that LIPIcs exists and who claim that publishing conference proceedings with commercial publishers is a sign of scientific quality. 

If you happen to be in a position to do so, you can support the TheoretiCS foundation, which is a German not-for-profit organization, by making a donation. 

I look forward to seeing the developments of TheoretiCS. Even though predicting the future is difficult, I have no doubt that the journal will become a coveted outlet, with the help of the community it aims to serve. Welcome to TheoretiCS and good luck!


=== Additional information about the journal ===

---  Guiding principles and objectives  ---

- 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.

- 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'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 remains with the authors, under a Creative Commons license.


---  Editorial Board  ---

The inaugural Editors-in-Chief are Javier Esparza (TU München) and Uri Zwick (Tel Aviv U.). The entire Editorial Board can be seen at https://theoretics-journal.org (see below as well).


---  Organization and a bit of history  ---

The project built on groundwork laid in the Council of the EATCS, and started in 2019 and underwent a long gestation. From the start, we wanted to have a thorough discussion with a wide representation of the community, on how to best implement the guiding principles sketched above. It was deemed essential to make sure that all fields of theoretical computer science would feel at home in this journal, and that it would be recognized as a valid venue for publication all over the world.

This resulted in the creation of an Advisory Board, composed of representatives of most of the main conferences in the field (currently APPROX, CCC, COLT, CONCUR, CSL, FOCS, FoSSaCS, FSCD, FSTTCS, ICALP, ICDT, ITCS, LICS, MFCS, PODC, SoCG, SODA, STACS, STOC, TCC) and of so-called members-at-large. The composition of this Advisory Board, which may still evolve, can be consulted at https://theoretics-journal.org.


---  Logistics and answers to some natural questions  ---

- The journal is published by the TheoretiCS Foundation, a non-profit foundation established under German law.

- TheoretiCS is based on the platform episciences.org, in the spirit of a so-called overlay journal.

- The Advisory Board, together with the Editors-in-Chief and the Managing Editors, devolved much of their efforts to designing and implementing an efficient 2-phase review system: efficient in terms of the added-value it brings to the published papers and their authors, and of the time it takes. Yet, as this review system relies in an essential fashion on the work and expertise of colleagues (like in all classical reputable journals), we cannot guarantee a fixed duration for the evaluation of the papers submitted to TheoretiCS.

- Being charge-free for authors and readers does not mean that there is no cost to publishing a journal. These costs are supported for the foreseeable future by academic institutions (at the moment, CNRS and Inria, in France; others may join).

- The journal will have an ISSN, and each paper will have a DOI. There will be no print edition.


---  Editorial Board  ---

Editors-in-Chief

    Javier Esparza (Technische Universität München, Munich)
    Uri Zwick (Tel Aviv University, Tel Aviv)

Managing  Editors

    Antoine Amarilli (Institut polytechnique de Paris, Télécom Paris)
    Nathanaël Fijalkow (CNRS, Bordeaux, and The Alan Turing Institute of Data Science, London)

Editors

    Martin Abadi, Google, USA
    Andris Ambainis, U. of Latvia
    Albert Atserias, UPC, Barcelona
    Haris Aziz, UNSW, Sydney
    David Basin, ETH Zürich
    Patricia Bouyer, CNRS, Paris-Saclay
    Nicolò Cesa-Bianchi, Università di Milano
    Anuj Dawar, Cambridge University
    Luc Devroye,  McGill University, Montreal
    Jacob Fox, Stanford University
    Mohsen Ghaffari, ETH Zürich
    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, Collège de France, Paris
    Katrina Ligett, Hebrew University, Jerusalem
    Rupak Majumdar, MPI-SWS, Kaiserslautern
    Joseph Mitchell, State University of New York at Stony Brook
    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
    Michał 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, New York