The International Colloquium on Automata, Languages and Programming (ICALP) is one of the prime theory venues in Europe and the annual meeting of the European Association for Theoretical Computer Science (EATCS). The 2022 edition will be held in Paris, France on July 4-8. Authors of the Algorithm Engineering group contribute two papers.
The first paper with the title Social Distancing Network Creation is based on the master thesis of Hans Gawendowicz and presents a new network creation game model for explaining the formation of social networks under the influence of social distancing during a pandemic. In contrast to classic network creation game models, the utility function is inversed, i.e. edge formation is beneficial but agents maximize distances.
In the second paper, Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances, Sarel Cohen and Martin Schirneck and their co-authors introduce the first fault-tolerant eccentricity oracle for dual failures in subcubic space. They also derandomize constructions from the literature to create the first deterministic distance sensitivity oracle with subcubic preprocessing time.
