There will be three invited talks at IWOCA 2020. The invited speakers are:

Dan Alistarh is currently an Assistant Professor at IST Austria. Previously, he
was affiliated with ETH Zurich, Microsoft Research, and MIT. He received his PhD
from the EPFL, under the guidance of Prof. Rachid Guerraoui. His research
focuses on distributed algorithms and concurrent data structures, and spans from
algorithms and lower bounds to practical implementations. He is the recipient of
an ERC Starting Grant with a focus on distributed machine learning.

Optimization by population: large-scale distributed optimization via population protocols

The population model is a standard way to represent large-scale decentralized distributed systems, in which agents with limited computational power interact in randomly chosen pairs, in order to collectively solve global computational tasks.
In contrast with synchronous gossip models, nodes are anonymous, lack a common notion of time, and have no control over their scheduling.
In this talk, I will describe recent work examining whether large-scale distributed optimization can be performed in this extremely restrictive setting.

I will introduce and analyze natural decentralized variants of the classical stochastic gradient descent (SGD) procedure, in which every node maintains a local estimate of the optimal set of parameters, and is able to compute stochastic gradients with respect to this parameter.
Every pair-wise node interaction performs a stochastic gradient step at each agent, followed by averaging of the two models.
I will show that, under standard assumptions, SGD can converge even in this extremely loose, decentralized setting. Moreover, surprisingly, the algorithm can achieve linear speedup in the number of nodes n.
In addition, I will show experimental results showing that PopSGD can achieve convergence and speedup for large-scale distributed learning tasks in a supercomputing environment.

Sándor Fekete holds the chair for Algorithmics in the Department of Computer Science at the Braunschweig University of Technology in Germany. From 2011-2019 he was also director of the interdisciplinary Research Center for Informatics, Information Technologies and Digitalization (TUBS.digital). Having received his Ph.D. in mathematics from the University of Waterloo in Canada, he has held positions at the University of Cologne, SUNY Stony Brook and TU Berlin. His research
interests range all the way from theoretical foundations of algorithms and optimization (with a focus on geometric and distributed methods) to applications areas such as practical computer science,
electrical engineering, economics, biology and physics, leading to about 250 peer-reviewed
publications with about 250 different coauthors.

Coordinating swarms of objects at extreme dimensions

Coordinating and reconfiguring arrangements of objects poses important questions
at various dimensions, ranging from tiny particles all the way to far-away satellite swarms.
Ironically, systems of these very small and very large distances share a fundamental property:
It becomes difficult to use „external“ computation, in which a powerful central computing device
is provided with input about the system, and output is fed back into the system. Instead, it
becomes important to consider „internal“ computation, in which algorithms and execution
remain within the system itself, even if that comes at the expense of processing power.
Additional challenges arise from coordinating the parallel motion of larger and larger sets of
objects in a globally efficient manner.

This talk will describe a variety of algorithmic approaches to coordination and reconfiguration.
These are based on the work of our group and include algorithmic aspects of “programmable matter”,
i.e., algorithmic methods for controlling structures that can change their physical properties
(shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion and
optimization methods for coordinated motion planning, in which a large swarm of objects needs
to be reorganized in a minimum amount of time.

Tatiana Starikovskaya is an Assistant Professor at the Computer Science Department of École normale supérieure, Paris, France. Her research interests include algorithms on strings, small-space algorithms and data structures, streaming algorithms, and property testing algorithms. Tatiana Starikovskaya obtained her PhD from Lomonosov Moscow State University in 2013. Prior to joining ENS, she worked as an Associate Professor at the Department of Computer Science at Higher School of Economics in Moscow (2013-2015), as a Research Associate at the University of Bristol (2015-2016), and as a Postdoc at Université Paris-Diderot (2016-2017).

Algorithms for string processing in restricted-access models of computation

Many classical algorithms for string processing assume random access to the data, which poses a serious limitation in the modern era of data deluge. In this talk, we will consider two novel models of computation that avoid this assumption: streaming and property testing.


In the streaming model of computation, we assume that the input arrives as a stream, one data item at a time, which captures a situation when the data are sequential measurements or an output of an algorithm. In this model, the space complexity is defined as all the space used, including the space used to store (some) information about the input. In the property testing model, we assume that the data is stored on a remote machine, making random access to it extremely expensive. We must decide whether the input has a particular property while accessing as few data items as possible. In this model, the time complexity is defined as the number of accessed data items.



In this talk, we will discuss recent developments related to these two models and will show that they allow developing ultra-efficient approaches to string processing.