ICE-TCS seminar by Benjamin Moore on "Smoothed analysis for graph isomorphism"

Today, the ICE-TCS seminar series at Reykjavik University hosted a talk by Benjamin Moore (Institute of Science and Technology Austria) who is visiting our postdoctoral researcher Nicolaos Matsakis. 

Benjamin presented the main results in his paper "Smoothed analysis for graph isomorphism", coauthored with his ISTA colleagues Michael Anastos and Matthew Kwan. (In passing, I just saw that Matthew Kwan received the main prize of the Austrian Mathematical Society last year. Congratulations!) 

To my mind, Benjamin did an excellent job in presenting the context for their exciting (but very technical) contribution and the main ideas that underlie it. Kudos! The work by Benjamin and his collaborators provides another explanation of the effectiveness of the colour refinement algorithm (also known as the one-dimensional Weisfeiler-Leman algorithm) in checking whether two graphs are isomorphic. I encourage you to read at least the introduction of their paper, which will be presented at STOC 2025, and the ISTA news article here, which does a much better job at putting their work in context than an interested, but ignorant, observer like me ever could. FWIW, I find results like theirs, which offer some explanation as to why theoretically hard problems are seemingly easy in practice, fascinating and I feel like that paper might be a strong candidate for a best paper award. 

It was also fitting to see recent work on smoothed analysis being presented at our seminar series since Daniel Spielman and Shang-Hua Teng received the 2008 Gödel Prize at ICALP 2008, which was held at Reykjavik University. Time flies, but great work is timeless. 

Interview with Magnús Már Halldórsson on Reykjavik University's website

Magnús Már Halldórsson, the director of ICE-TCS, was interviewed by the Communication Department at Reykjavik University to mark the 20th anniversary of ICE-TCS on April 29, 2025. The interview appeared last Friday on the Reykjavik University web site. In my biased opinion,  Magnús hit all the right notes. I hope that some of our students and colleagues, as well as the staff at Icelandic funding agencies and politicians, read it. 

I am also pleased to see theoretical computer science at the Department of Computer Science at Reykjavik University get some visibility on the university's website after twenty years. It leave the job of determining the level of contribution and the visibility ICE-TCS has given to the department and to computer science research in Iceland to others. 

In case anyone is interested in having a look at them, our annual reports from June 2007 till the whole of 2024 are available here. (Thanks to Tarmo Uustalu for reviving the centre's website and for keeping up to data!)

Dagstuhl Publishing – Highlights of 2024

On behalf of Dagstuhl Publishing, Michael Wagner has posted the highlights for 2024. IMHO, the computer-science research community owes the team at Dagstuhl Publishing and Schloss Dagstuhl a lot for its sustained support of research and open-access publication activities. I encourage any readers I might have to read the highlights for 2024 and share them within their networks. This is the least we can do to thank everyone at Dagsthul for their work. 

If you are a PC chair or an SC member of a high-quality conference that publishes its proceedings with a commercial publisher, and you care about open-access publication of research results and artefacts, consider suggesting that your conference apply for publishing its proceedings in LIPIcs. 

Last, but not least, consider submitting some of your best work to the journal Transaction on Graph Data and Knowledge, if it is in the areas covered by that diamond-open-access journal!

27th Estonian Winter School in Computer Science, EWSCS 2025 Viinistu, Estonia, 3-6 March 2025

I received the following announcement from my colleague Tarmo Uustalu. Spread the news of this excellent winter school for young researchers!

The 2025 edition of the Estonian Winter School in Computer Science (EWSCS) will be held in Viinistu, Estonia, in the period 3-6 March 2025. Editions of EWSCS are general TCS schools with topics from both Theory A and B. EWSCS is a long-running series; the first school happened in 1996 and this is its 27th edition. The schools are mostly intended for PhD students as well as ambitious MSc and BSc students, but are open for anyone.

This year's programme features the following four courses on combinatorics, modern database theory, concurrency connected to topology, and provable cybersecurity.

• Anders Claesson, University of Iceland, Reykjavik. Combinatorial species. 
• Uli Fahrenberg, EPITA Rennes. Discrete and continuous models for concurrent systems: from Petri nets to directed spaces. 
• Miika Hannula, University of Tartu. Conjunctive query evaluation. 
• Marino Miculan, University of Udine. Provable security, ProVerif.

Check the school webpage for abstracts and the timetable. 

Participation fee is 490 EUR. Covered in the fee are accommodation for three nights in twin rooms, with full board, and transportation from Tallinn to the school venue and back.

Application deadline: 12 Feb 2025.

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 particular in the fields of data science, software engineering, theoretical computer science (see the ICE-TCS web page for information on our TCS group), as well as visual computing, games, and interactive media.

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

See https://jobs.50skills.com/ru/is/32303 for details on how to apply.

Nicola Cotumaccio receives Best Italian PhD Thesis Award in Theoretical Computer Science

At this time of the year, the Italian Chapter of the EATCS announces its awards. See here for the full list for 2024 and previous years. 

I am delighted to see that the selection committee for the Best Italian PhD Theses in Theoretical Computer Science 2024 has selected Nicola Cotumaccio (Gran Sasso Science Institute) for that award for his thesis "Data Compression Meets Automata Theory", which was supervised by Nicola Prezza, Travis Gagie and Catia Trubiani. Nicola received his Ph.D. in Computer Science in January 2024, as part of a joint agreement between the Gran Sasso Science Institute (Italy) and Dalhousie University (Canada). From February 2024, he is a postdoctoral researcher at the University of Helsinki in
Finland. His research can be placed in the interconnection between formal methods and algorithms, where he develops innovative techniques mainly in the fields of data compression and automata theory.

Nicola's thesis work introduces a new paradigm in graph compression and formal language theory, using some of the most important data structures for compressing and indexing strings, such as the suffix array, the Burrows-Wheeler Transform and the FM-index. Not only does the proposed paradigm provide a new approach to studying classic problems on finite automata and regular languages, but it also retrospectively explains the impact of the aforementioned data structures. I find it both refreshing and amazing that Nicola and his collaborators have been able to shed some new light on time-honoured constructions on automata, such as the subset construction, via the paradigm presented in his thesis. See, for instance, their JACM paper. 

I am also thrilled to see that Nicola shared the award with Francesca Randone (IMT School for Advanced Studies Lucca), who is recognised for her thesis "Efficient and Accurate Analysis of Two Classes of Transparent Generative Models", supervised by Mirco Tribastone and Luca Bortolussi.

I wish Francesca and Nicola good luck for their future careers!

Accepted papers for GandALF 2024 and SLSS 2024

The list of papers that were selected for presentation at GandALF 2024 is available at https://scool24.github.io/GandALF/ I am looking forward to listening to the presentations based on those articles and to the four invited talks by Bernd Finkbeiner (CISPA Helmholtz Center for Information Security), Kim Guldstrand Larsen (Aalborg University), Brigitte Pientka (McGill University) and Azalea Raad (Imperial College London). 

On behalf of the GandALF SC, I thank the GandALF 2024 PC co-chairs, Antonis Achilleos and Adrian Francalanza, and their PC for the efficient PC work. 

 In case you missed it, the list of selected contributions and invited talks at the co-located Twelfth Scandinavian Logic Symposium (SLSS 2024) is at https://scool24.github.io/SLSS/. SLSS will be held on 14-16 June and GandALF on 19-21 June. As part of the Reykjavik Summer of Cool Logic 2024 (SCooL 2024), we will also host the Fifth Nordic Logic Summer School (NLS 2024) on 10-13 June. 

Thanks to all my colleagues at ICE-TCS, Department of Computer Science at Reykjavik University, who are working very hard on the organisation of these three events back to back. 

I hope to see a good participation at those events.