Workshops

Nine workshops will happen on the fourth of July.

The workshops happen in the Saint Père site of the Université Paris Cité (this is not the same place as the main part of the conference):

45, rue des Saints-Pères, 75006 Paris.

For onsite participation, registration through ICALP2022 web’site is necessary: https://icalp2022.dakini-pco.com/registration-76.php

1: Parameterized Approximation Algorithms Workshop
Two standard approaches to handle hard (typically NP-hard) optimization problems are to develop approximation and parameterized algorithms. For the former, the runtime should be polynomial in the input size, but the computed solution may deviate from the optimum. For the latter, the optimum solution should be computed, but any super-polynomial runtime should be isolated to some parameter of the input. Some problems however are hard to approximate on one hand, and on the other it is also hard to obtain parameterized algorithms for some given parameter. In this case one may still hope to obtain parameterized approximation algorithms, which combine the two paradigms, i.e. the computed solution may deviate from the optimum and the runtime should have super-polynomial dependence only in some given parameter. Recently there has been a great deal of development in proving the existence or non-existence of parameterized approximation algorithms, and the aim of this workshop is to bring together active researchers of this emerging field, so that they may share their results and insights.
Organizers:
Andreas Emil Feldmann (Charles University in Prague)
Michail Lampis (Universite Paris Dauphine)

2: Combinatorial Reconfiguration
Combinatorial Reconfiguration studies reachability and related questions over combinatorial structures. A typical example asks if the solution space of a Boolean formula is connected with respect to the Boolean cube topology, formed by flipping one bit at the time. Although there is now a wealth of publications on many aspects of Combinatorial Reconfiguration, many questions remain open. This workshop aims at strengthening relations among researchers in various fields of theoretical computer science and mathematics, and broadening interest in Combinatorial Reconfiguration to a wider audience. The workshop will consist of a few invited talks and shorter contributed talks.
Organizers:
Takehiro Ito (Tohoku University)
Jun Kawahara (Kyoto University)
Yoshio Okamoto (The University of Electro-Communications)
Akira Suzuki (Tohoku University)

3: Recent Advances on Total Search Problems
The Recent Advances on Total Search Problems workshop aims at highlighting the most significant recent results related to total search problems. The inherent characteristic of these problems is that every instance has a solution. Yet, a growing body of evidence suggests that finding this solution is sometimes intractable. This phenomenon has fascinated complexity theorists since the 1980’s. Over the last few decades, it has also been tied to an increasingly diverse list of applications from areas such as Economics and Game Theory, Fair Division, Cryptography, Combinatorics and Topology, Query and Communication Complexity, Graph Theory.
The goal of the workshop is twofold. Firstly, it aims to introduce the broad Theoretical Computer Science community to total functions and the connections to various subfields, as well as promote new connections. Secondly, it aims to advertise some of the recent breakthroughs, and shine the spotlight on some of the core open problems.
Organizers:
Argyrios Deligkas (Royal Holloway University of London)
Aris Filos-Ratsikas (University of Liverpool)
Alexandros Hollender (University of Oxford)
Manolis Zampetakis (UC Berkeley)

4: LearnAut: 4th edition of the Learning and Automata workshop
Grammatical Inference (GI) studies machine learning algorithms for models defining recursive computations like automata and grammars. The expressive power of these models and the complexity of associated problems are a major research topic within the ICALP community. Historically, there has been little interaction between the GI and ICALP communities, though in recent years we have seen some important results starting to bridge the gap, including applications of learning to formal verification and model checking, (co-)algebraic formulations of automata and grammar learning algorithms and theoretical foundations of learning. This workshop aims to bring together experts on language theory that could benefit from grammatical inference tools, and researchers in grammatical inference who could find new insights for their methods in theoretical computer Science. The workshop will include talks by renowned invited speakers and from researchers selected after a submission process.
Organizers:
Rémi Eyraud (University of Saint-Etienne)
Tobias Kappé ( ILLC, University of Amsterdam)
Guillaume Rabusseau (Université de Montréal; Mila)
Matteo Sammartino (Royal Holloway, University of London; University College London)

5: Algorithmic Aspects of Temporal Graphs V
In modern systems the classical modeling paradigm using static graphs may be restrictive or oversimplifying, as the interactions among the elementary system units usually change over time in a highly dynamic manner. The common characteristic in all these application areas is that the system structure, i.e. graph topology, is subject to discrete changes over time. In such dynamically changing graphs the notion of vertex adjacency needs to be revisited and various graph concepts, e.g. reachability and connectedness, now crucially depend on the exact temporal ordering of the edges’ presence. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented, as well as some of the key challenges will be highlighted. As this research area grows and broadens, our aim is to bring together people from theoretical and practical communities of temporal graphs in order to establish new and strengthen existing links between these communities.
Organizers:
Eleni C. Akrida (Durham University)
George B. Mertzios (Durham University)
Paul G. Spirakis (University of Liverpool and University of Patras)
Viktor Zamaraev (University of Liverpool)

6: Trends in Arithmetic Theories
Logical theories of arithmetic such as Presburger arithmetic play an important role in a variety of different areas of computer science and have been studied since the early days of the field. The recent years have seen a lot of progress on all aspects of such theories, ranging from new foundational results, algorithmic advances, more performant decision procedures to novel application domains. This progress has largely been obtained independently without much interaction between researchers working on different aspects of this field. The goal of this workshop is to bring together researchers working in the field to exchange latest trends, understand currently existing challenges and to initiate new collaborations.
Organizers:
Dmitry Chistikov (University of Warwick)
Christoph Haase (University of Oxford)

​7: Structure Meets Power 2022
There is a remarkable divide in the field of logic in Computer Science, between two distinct strands: one focusing on semantics and compositionality (“Structure”), the other on expressiveness and complexity (“Power”). It is remarkable because these two fundamental aspects of our field are studied using almost disjoint technical languages and methods, by almost disjoint research communities. We believe that bridging this divide is a major issue in Computer Science, and may hold the key to fundamental advances in the field. The aim of the Structure meets Power workshop is to cultivate interaction between researchers who are interested in combining ideas from these two strands.
Organizers:
Samson Abramsky (University College London)
Anuj Dawar (University of Cambridge)
Tomáš Jakl​ (​University of Cambridge)
Dan Marsden (University of Oxford)

8: Straight-Line Programs, Word Equations and their Interplay
Straight-line programs, i.e., context free grammars that produce a unique string, have been studied intensively in data compression, information theory and stringology and found numerous in such areas like computational group theory, computational topology, program analysis, and verification. Plandowski and Rytter recognized in the late 1990’s their importance for the solution of word equations. Since then, the connection between straight-line programs and word equations turned out to be fruitful. The goal oft he workshop is to disseminate recent results on straight-line programs and word equations, and help to gain a new perspective on them, thereby finding possible connections or avenues for new applications of techniques. For researchers not working in the field, the workshop will give a good summary on recent progress in this active field.
Organizers:
Artur Jeż (University of Wrocław)
​Markus Lohrey (University of Siegen)

9: Graph Width Parameters: from Structure to Algorithms
Most optimization problems defined on graphs are computationally hard. For such problems it is natural to restrict the input and ask: for which graph classes does the problem become efficiently solvable and for which graph classes does it stay hard?  Knowing that a graph has small « width » (for example, treewidth, clique-width, mim-width) has proven to be highly useful for designing efficient algorithms for many well-known problems, such as Feedback Vertex Set, Graph Colouring and Independent Set.  That is, boundedness of width enables the application of a problem-specific dynamic programming algorithm or a meta-theorem to solve a certain problem.  However, for many graph classes it is not known if the class has small width for some appropriate width parameter.  This has resulted in ad-hoc efficient algorithms for special graph classes that may unknowingly make use of the fact that the graph classes under consideration have small width.  More generally speaking, rather than solving problems one by one and graph-class by graph-class, the focus of our satellite workshop is: discovering general properties of graph classes from which we can determine the tractability or hardness of graph problems, and discovering which graph problems can be solved efficiently on graph classes of bounded width. For this purpose we aim to bring together researchers from Discrete Mathematics (structure) and Theoretical Computer Science (algorithms).
Organizers:
Flavia Bonomo (University of Buenos Aires)
Nick Brettell (Victoria University of Wellington)
Andrea Munaro (Queen’s University Belfast)
Daniel Paulusma (Durham University)

IMPORTANT DATES

The workshop proposal submission is now closed.

Workshop proposal deadline Friday 19 November 2021, 23:59 AoE
Workshop notification Friday 10 December 2021
Workshops Monday 4 July 2022

We strongly suggest that prospective workshop organizers contact the workshop selection committee before submitting a proposal.

WORKSHOP PROPOSAL GUIDELINES

Proposals should be submitted no later than Friday 19 November 2021 by sending an email to the workshop selection committee, see below. You should expect notification on the acceptance of your proposal by 10 December 2021.

A workshop proposal submission should consist of the following:
A short scientific justification of the proposed topic, its significance, and the particular benefits of the workshop to the community.
An organisational part including:
– workshop’s name and URL (if already available);
– contact information for the workshop organizers (including their webpages);
– expected number of participants (if available, please include the data of previous years);
– proposed format and agenda (e.g. paper presentations, tutorials, see below for more details);
– potential invited speakers;
– plans for dissemination, if any (e.g. a journal special issue);
– planned format of the event (see below for mode details);- virtual/hybrid backup plans (including platform preference).

WORKSHOP FORMAT

A standard option is a full one-day workshop consisting of invited talks by leading experts and of shorter contributed talks, either directly invited by the organizers or selected among presentation submissions.
Deviations from this standard are also welcome, including open problem sessions, discussion panels, or working sessions. If you plan to have invited speakers, please specify their expected number and, if possible, tentative names. If you plan a call for contributed talks (or papers) followed by a selection procedure, the submission date should be scheduled after ICALP 2022 notification (11 April 2022), while the notification should take place before the early registration deadline.
In your submission please include details on the schedule, planned procedure of selecting contributed talks (or papers). If you plan to have published proceedings of your workshop, please provide the name of the publisher.

Note that ICALP 2022 is not able to provide financial support for the organization of workshops. The conference can however provide a room, internet connection and help with some local organisation.  For workshops that are online or in hybrid mode, it is expected that the organizers provide the supporting technical infrastructure. 

 

Workshop Selection Committee

Co-organizers

Sponsors

CONTACT US
icalp2022@irif.fr
@ICALPconf