Accompanying the main conference, several satellite workshops will be organized.
All workshops will be held on Monday, July 10, 2023.
The workshops take place at:
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.
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).
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 in the recent years, our aim is to bring together people from theoretical and practical communities of temporal graphs in order to strengthen existing links and to establish new ones between these communities.
In recent years, the study of homomorphism counting resurged in various subfields within theoretical computer science. From a complexity theoretic point of view, it was shown that counting problems from different domains can be understood by expressing them as linear combinations of homomorphism counts. Such linear combinations enjoy the exceptional and very useful "monotonicity property" of being exactly as hard to compute as their hardest terms. Since the complexity of computing the individual terms, i.e., of counting homomorphisms, is reasonably well understood, this strategy allowed the community to make significant progress in the study of the complexity of various counting problems arising in database theory and network sciences.
From a more abstract perspective, the numbers of homomorphisms between graphs encode valuable information. For example, a classical result by Lovász shows that homomorphism counts from all graphs into a given graph G identify G up to isomorphism. Restricting the class of graphs from which homomorphisms are counted yields natural relaxations of graph isomorphism that have recently been connected to the expressiveness of logics. Furthermore, in pure mathematics, homomorphism counts enable a definition of convergent graph sequences that leads to so-called graph limits, which are an active area of study.
The purpose of this workshop is two-fold, namely,
Over the last decades, congestion games have played a staring role in the study of non-cooperative resource allocation. They are expressive enough to model many real-world applications where resources are scarse and there is competition for their use. For example, congestion games can be used to model the allocation of airport gates or highway lanes during peak travel times.
Congestion games shed light on the ways in which individuals make decisions in these situations. Understanding this behaviour allows policymakers and planners to make more informed decisions, e.g. by designing tools that improve efficiency. Congestion games also played a pivotal role for the algorithmic game theory community as many concepts such as the efficiency of equilibria, local search procedures, convergence of learning, or coordination mechanism to improve the quality of the equilibria were first studied for this class of games.
This workshop provides a forum for presenting and discussing recent advances and key challenges in congestion games and beyond. It will bring together researchers working on different aspects of congestion games and foster collaborations also with the wider TCS community.
Recursively defined sequences are foundational objects of study in the computational sciences; they arise naturally in areas such as: the analysis of algorithms, weighted automata, loop termination, and probabilistic models. Decision procedures for recursive sequences are of particular interest in automated verification and the wider formal methods community.
The aim of WORReLL'23 is to bring together researchers from the community as well as showcase cutting-edge research on computational aspects of dynamical systems, with applications to verification and program analysis. The one-day workshop will also celebrate the research contributions of Professor James Worrell (also known as Ben). For context, Ben is giving an invited talk at ICALP this year.
Online algorithms make irrevocable decisions for an initially unknown input that is revealed sequentially. The goal is to achieve a good competitive performance in comparison to an offline optimal algorithm that can access the entire input in advance. Online algorithms have been intensively studied in recent years and new breakthrough results have been achieved. Further, new models have been proposed that relax the overly pessimistic assumption of not having any prior knowledge about future requests in different ways. Such modern developments allow one to go beyond traditional worst-case competitive analysis and breach pathological impossibility results. Such new trends include (not exclusively):
Quantum Computation is an important field in computation, since it is a completely new paradigm, with the possibility to bring solutions to problems, which cannot be solved by classical computers.
We are not the only one thinking this, the Quantum Flagship program as a lot national and European initiatives, want to encourage Research in Quantum Computation with money and possible collaborations.
What we would like to show in this workshop are several things:
The aim of this 1-day satellite workshop is to initiate interactions and collaborations between the algebraic complexity theory community and the wider theoretical computer science community.
Algebraic Complexity Theory is a vibrant field that has seen a tremendous amount of activity in the recent years. Its classical questions have been interwoven with deep questions from algebraic geometry, invariant theory, and representation theory. Researchers study a wide range of interlinked topics: arithmetic circuit lower bounds, algorithmic algebra(ic geometry), algorithmic invariant theory, geometric complexity theory, tensor rank, polynomial identity testing, and polynomial reconstruction, to name a few.
The workshop will consist of a few invited talks and shorter contributed talks. The presentations are aimed at a general TCS audience.
Digital Computers naturally process discrete data, such as bits or integers or strings or graphs. From bits to advanced data structures, from a first semi-conducting transistor to billions in wafer-scale integration, from individual Boolean connectives to entire CPU circuits, from kB to TB memories, from 10 to 10^9 instructions per second, from punched cards to high-level programming languages:
the success story of digital computing arguably is due to (1) hierarchical layers of abstraction and (2) the ultimate reliability of each layer for the next one to build on ― for processing discrete data.
Continuous data on the other hand commonly arises in Physics, Engineering and Science: natura non facit saltus.
Such data mathematically corresponds to real numbers, smooth functions, bounded operators, or compact subsets of some abstract metric space.
The rise of digital (over analog) computers led a paralyzing blind spot in the realm of continuous (=non-discretized) data processing:
35 years after introduction and hardware standardization of IEEE 754 floating point numbers, mainstream Numerics is arguably still dominated by this forcible discretization of continuous data ― in spite of violating associative and distributive laws, breaking symmetries, introducing and propagating rounding errors, in addition to an involved (and incomplete) axiomatization including NaNs and denormalized numbers.
Deviations between mathematical structures and their hardware counterparts are common also in the discrete realm, such as the "integer" wraparound 255+1=0 occurring in bytes that led to the "Nuclear Gandhi" programming bug.
Similarly, deviations between exact and approximate continuous data underlie infamous failures such as the Ariane 501 flight V88 or the Sleipner-A oil platform.
Nowadays high-level programming languages (such as Java or Python) offer a user data type (called for example BigInt or mpz_t) that fully agrees with mathematical integers, simulated in software using a variable number of hardware bytes.
This additional layer of abstraction provides the reliability for advanced discrete data types (such as weighted or labelled graphs) to build on, as mentioned above.
We develop Computer Science for continuous data, to catch up with the discrete case: from foundations via practical implementation to commercial applications.
The International Colloquium on Automata, Languages and Programming (ICALP) is the main conference and annual meeting of the EATCS (European Association for Theoretical Computer Science). This is a call for workshops to be affiliated with ICALP 2023, to be held in Paderborn, Germany. We invite researchers to organize workshops on topics of interest to the ICALP community, in order to contribute to this year’s 50th annual edition of ICALP, which deserves celebration!
In-person. (In exceptional cases, there may be support for remotely presenting a talk.)
We recommend that prospective workshop organizers contact the workshop chair before submitting a proposal, though this is not strictly required.
Proposals should be submitted via email to the workshop chair,
Each submission should consist of the following:
As for the 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 half-day workshops, 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 2023 notification (21 April 2023), 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 2023 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 organization. Refreshments will be served.
Workshop Chair:
Workshop Selection Committee:
Contact - Privacy Protection Statement - Legal Notice
© 2022-2023 Paderborn University / Powered by ProcessWire CMS