### Quantum Cryptanalysis (Dagstuhl Seminar 19421)

Michele Mosca, Maria Naya-Plasencia & Rainer Steinwandt
This seminar report documents the program and the outcomes of Dagstuhl Seminar 19421 "Quantum Cryptanalysis", which took place in October 2019. After outlining the motivation and organizational aspects of this particular seminar, abstracts of presentations that were given by participants are provided.

### Algorithms and Complexity in Phylogenetics (Dagstuhl Seminar 19443)

Magnus Bordewich, Britta Dorn, Simone Linz & Rolf Niedermeier
Phylogenetics is the study of ancestral relationships between species. Its central goal is the reconstruction and analysis of phylogenetic trees and networks. Even though research in phylogenetics is motivated by biological questions and applications, it heavily relies on mathematics and computer science. Dagstuhl Seminar 19443 on Algorithms and Complexity in Phylogenetics aimed at bringing together researchers from phylogenetics and theoretical computer science to enable an exchange of expertise, facilitate interactions across both research areas, and...

### Programming Languages for Distributed Systems and Distributed Data Management (Dagstuhl Seminar 19442)

Carla Ferreira, Philipp Haller & Guido Salvaneschi
Programming language advances have played an important role in various areas of distributed systems research, including consistency, communication, and fault tolerance, enabling automated reasoning and performance optimization. However, over the last few years, researchers focusing on this area have been scattered across different communities such as language design and implementation, (distributed) databases, Big Data processing and IoT/edge computing -- resulting in limited interaction. The goal of this seminar is to build a community of researchers...

### Analysis of Autonomous Mobile Collectives in Complex Physical Environments (Dagstuhl Seminar 19432)

Mario Gleirscher, Anne E. Haxthausen, Martin Leucker & Sven Linker
This report documents the program and the outcomes of Dagstuhl Seminar 19432 "Analysis of Autonomous Mobile Collectives in Complex Physical Environments". Our working hypothesis for this seminar was that for systems of such complexity and criticality, the trustworthy certification and the successful operation in society will strongly benefit from the coordinated application of several rigorous engineering methods and formal analysis techniques. In this context, we discussed the state-of-the-art based on the working example of a...

### Theory of Randomized Optimization Heuristics (Dagstuhl Reports 19431)

Carola Doerr, Carlos M. Fonseca, Tobias Friedrich & Xin Yao
This report documents the activities of Dagstuhl Seminar 19431 on Theory of Randomized Optimization Heuristics. 46 researchers from Europe, Australia, Asia, and North America have come together to discuss ongoing research. This tenth edition of the seminar series had three focus topics: (1) relation between optimal control and heuristic optimization, (2) benchmarking optimization heuristics, and (3) the interfaces between continuous and discrete optimization. Several breakout sessions have provided ample opportunity to brainstorm on recent developments...

### Social Agents for Teamwork and Group Interactions (Dagstuhl Seminar 19411)

Elisabeth André, Ana Paiva, Julie Shah & Abanovic, Selma
This report documents the program and the outcomes of Dagstuhl Seminar 19411 "Social Agents for Teamwork and Group Interactions". It summarises the three talks that were held during the seminar on three different perspectives: the impact of robots in human teamwork, mechanisms to support group interactions in virtual settings, and affect analysis in human-robot group settings. It also details the considerations of six working groups covering the following topics: datasets, design, team dynamics, social cognition,...

### Comparative Theory for Graph Polynomials (Dagstuhl Seminar 19401)

Jo Ellis-Monaghan, Andrew Goodall, Iain Moffatt & Kerri Morgan
This report documents the programme and outcomes of Dagstuhl Seminar 19401 Comparative Theory for Graph Polynomials''. The study of graph polynomials has become increasingly active, with new applications and new graph polynomials being discovered each year. The genera of graph polynomials are diverse, and their interconnections are rich. Experts in the field are finding that proof techniques and results established in one area can be successfully extended to others. From this a general theory is...

### Data Ecosystems: Sovereign Data Exchange among Organizations (Dagstuhl Seminar 19391)

Cinzia Capiello, Avigdor Gal, Matthias Jarke & Jakob Rehof
This report documents the program and the outcomes of Dagstuhl Seminar 19391 Data Ecosystems: Sovereign Data Exchange among Organizations''. The goal of the seminar was to bring together people from different disciplines (also outside the computer science area), in order to identify (i) a set of research challenges for the future development of data ecosystems and a catalogue of major approaches relevant to the field and (ii) a set of developed use cases of particular...

### Deduction Beyond Satisfiability (Dagstuhl Seminar 19371)

Carsten Fuhs, Philipp Rümmer, Renate Schmidt & Cesare Tinelli
Research in automated deduction is traditionally focused on the problem of determining the satisfiability of formulas or, more generally, on solving logical problems with yes/no answers. Thanks to recent advances that have dramatically increased the power of automated deduction tools, there is now a growing interest in extending deduction techniques to attack logical problems with more complex answers. These include both problems with a long history, such as quantifier elimination, which are now being revisited...

### Application-Oriented Computational Social Choice (Dagstuhl Seminar 19381)

Umberto Grandi, Stefan Napel, Rolf Niedermeier & Kristen Brent Venable
This report documents the program and the outcomes of Dagstuhl Seminar 19381 Application-Oriented Computational Social Choice''. The seminar was organised around four focus topics: group recommender systems, fair allocation, electoral systems, and interactive democracy. For each topic, an invited survey was given by one of the participants. 26 participants presented their research in a regular talk, and two rump sessions allowed other participants to present their ongoing work and open problems in short talks. A...

### Logic and Learning (Dagstuhl Seminar 19361)

Michael Benedikt, Kristian Kersting, Phokion G. Kolaitis & Daniel Neider
The goal of building truly intelligent systems has forever been a central problem in computer science. While logic-based approaches of yore have had their successes and failures, the era of machine learning, specifically deep learning is also coming upon significant challenges. There is a growing consensus that the inductive reasoning and complex, high-dimensional pattern recognition capabilities of deep learning models need to be combined with symbolic (even programmatic), deductive capabilities traditionally developed in the logic...

Michael Wagner

Michael Wagner

### Notional Machines and Programming Language Semantics in Education (Dagstuhl Seminar 19281)

Mark Guzdial, Shriram Krishnamurthi, Juha Sorva & Jan Vahrenhold
A formal semantics of a language serves many purposes. It can help debug the language's design, be used to prove type soundness, and guide optimizers to confirm that their work is correctness-preserving. Formal semantics are evaluated by several criteria: full abstraction, adequacy, soundness and completeness, faithfulness to an underlying implementation, and so on. Unfortunately, we know relatively little about how non-experts, such as students, actually employ a semantics. Which models are they able to grasp?...

### OASIcs, Volume 73, CERTS'19, Complete Volume

Mikael Asplund & Michael Paulitsch
OASIcs, Volume 73, CERTS'19, Complete Volume

Michael Wagner

### Massively Parallel Approximate Distance Sketches

Michael Dinitz & Yasamin Nazari
Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. We initiate their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. We provide efficient constructions in both of these models, but our core results are for MPC. In MPC we...

### Sparse Hopsets in Congested Clique

Yasamin Nazari
We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph G=(V,E), a (?,?)-hopset H with "hopbound" ?, is a set of edges added to G such that for any pair of nodes u and v in G there is a path with at most ? hops in G ? H with length within (1+?) of the shortest path between u and v in G....

### Equivalence Classes and Conditional Hardness in Massively Parallel Computations

Danupon Nanongkai & Michele Scquizzato
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or...

### Towards Distributed Two-Stage Stochastic Optimization

Yuval Emek, Noga Harlev & Taisuke Izumi
The weighted vertex cover problem is concerned with selecting a subset of the vertices that covers a target set of edges with the objective of minimizing the total cost of the selected vertices. We consider a variant of this classic combinatorial optimization problem where the target edge set is not fully known; rather, it is characterized by a probability distribution. Adhering to the model of two-stage stochastic optimization, the execution is divided into two stages...

### Reconfigurable Lattice Agreement and Applications

Petr Kuznetsov, Thibault Rieutord & Sara Tucci-Piergiovanni
Reconfiguration is one of the central mechanisms in distributed systems. Due to failures and connectivity disruptions, the very set of service replicas (or servers) and their roles in the computation may have to be reconfigured over time. To provide the desired level of consistency and availability to applications running on top of these servers, the clients of the service should be able to reach some form of agreement on the system configuration. We observe that...

### Exact Byzantine Consensus on Arbitrary Directed Graphs Under Local Broadcast Model

Muhammad Samir Khan, Lewis Tseng & Nitin H. Vaidya
We consider Byzantine consensus in a synchronous system where nodes are connected by a network modeled as a directed graph, i.e., communication links between neighboring nodes are not necessarily bi-directional. The directed graph model is motivated by wireless networks wherein asymmetric communication links can occur. In the classical point-to-point communication model, a message sent on a communication link is private between the two nodes on the link. This allows a Byzantine faulty node to equivocate,...

### Linearizable Replicated State Machines With Lattice Agreement

Xiong Zheng, Vijay K. Garg & John Kaippallimalil
This paper studies the lattice agreement problem in asynchronous systems and explores its application to building a linearizable replicated state machine (RSM). First, we propose an algorithm to solve the lattice agreement problem in O(log f) asynchronous rounds, where f is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best upper bound of O(f). Second, Faleiro et al have shown in [Faleiro et al. PODC,...

### Optimal Register Construction in M&M Systems

Vassos Hadzilacos, Xing Hu & Sam Toueg
Motivated by recent distributed systems technology, Aguilera et al. introduced a hybrid model of distributed computing, called message-and-memory model or m&m model for short [Marcos K. Aguilera et al., 2018]. In this model, processes can communicate by message passing and also by accessing some shared memory. We consider the basic problem of implementing an atomic single-writer multi-reader (SWMR) register shared by all the processes in m&m systems. Specifically, we give an algorithm that implements such...

### Gathering on Rings for Myopic Asynchronous Robots With Lights

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil & Koichi Wada
We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: M_{init}, which denotes the number of...

• 2009
134
• 2010
453
• 2011
366
• 2012
447
• 2013
462
• 2014
432
• 2015
732
• 2016
1,178
• 2017
1,326
• 2018
1,649
• 2019
1,497
• 2020
187

• Text
8,763
• Software
100