16th ICE-TCS Theory Day, 29th of April

16th ICE-TCS Theory Day

1st joint ICE-TCS/GSSI Theory Day

Where: https://meet.jit.si/ICE-TCS-TheoryDay2020

Schedule

14:30-14:40: Introduction (Magnus M. Halldorsson)
14:45-15:45: Mohsen Ghaffari (ETH Zurich) "Network Decomposition and Derandomization for Distributed Algorithms"

15:45-16:00: Break

16:00-17:00: Moshe Vardi (Rice University) "An Ethical Crisis in Computing?"17:00-17:05: Closing

----------- Abstracts of the talks ----------

Title: Network Decomposition and Derandomization for Distributed Algorithms

Speaker: Mohsen Ghaffari (ETH Zurich, CH)WWW: https://people.inf.ethz.ch/gmohsen/
Abstract: The gap between deterministic and randomized distributed graph algorithms remained one of the central open questions in the area for over three decades. In this talk, I explain a recent result
that settles this.

Concretely, I will describe an efficient deterministic distributed algorithm for network decomposition and explain how this implies a
general distributed derandomization theorem, proving that PLOCAL=P-RLOCAL. That is, informally, any efficient (i.e., polylogarithmic-time) randomized distributed algorithm for any locally checkable graph
problem can be derandomized to an efficient deterministic distributed algorithm. This leads to near-exponential improvements in deterministic and, perhaps surprisingly, randomized distributed
algorithms for numerous graph problems, as well as some improvements for massively parallel algorithms (i.e., MapReduce). These results resolve several decades-old and central open problems in distributed
graph algorithms, including Linial's well-known MIS question [FOCS'87], which had been called the most outstanding problem in the area. This is based on joint work with my student Vaclav Rozhon and appears at STOC 2020.

--------------------------------------------

Title: An Ethical Crisis in Computing?

Speaker: Moshe Y. Vardi, Rice University, WWW: https://www.cs.rice.edu/~vardi/Wikipedia: https://en.wikipedia.org/wiki/Moshe_Vardi

Computer scientists think often of "Ender's Game" these days. In this award-winning 1985 science-fiction novel by Orson Scott Card, Ender is being trained at Battle School, an institution designed to make young children into military commanders against an unspecified enemy. Ender's team engages in a series of computer-simulated battles, eventually destroying the enemy's planet, only to learn then that
the battles were very real and a real planet has been destroyed.

Many of us got involved in computing because programming was fun. The benefits of computing seemed intuitive to us. We truly believe that computing yields tremendous societal benefits; for example, the life-saving potential of driverless cars is enormous! Like Ender, however, we realized recently that computing is not a game--it is real--and it brings with it not only societal benefits, but also significant societal costs, such as labor polarization, disinformation, and smart-phone addiction.

The common reaction to this crisis is to label it as an "ethical crisis" and the proposed response is to add courses in ethics to the academic computing curriculum. I will argue that the ethical lense is too narrow. The real issue is how to deal with technology's impact on society. Technology is driving the future, but who is doing the steering?

Biographical sketch: Moshe Y. Vardi is a University Professor and the George Distinguished Service Professor in Computational Engineering at Rice University. He is the recipient of three IBM Outstanding Innovation Awards, the ACM SIGACT Goedel Prize, the ACM Kanellakis Award, the ACM SIGMOD Codd Award, the Blaise Pascal Medal, the IEEE Computer Society Goode Award, the EATCS Distinguished Achievements Award, the Southeastern Universities Research Association's Distinguished Scientist Award, and the ACM SIGLOG Church Award. He is the author and co-author of over 600 papers, as well as two books: Reasoning about Knowledge and Finite Model Theory and Its Applications. He is a Fellow of the American Association for the Advancement of Science, the American Mathematical Society the Association for Computing Machinery, the American Association for Artificial Intelligence, the European Association for Theoretical Computer Science, the Institute for Electrical and Electronic Engineers, and the Society for Industrial and Applied Mathematics. He is a member of the US National Academy of Engineering and National Academy of Science, the American Academy of Arts and Science, the European Academy of Science, and Academia Europaea. He holds six honorary doctorates. He is currently a Senior Editor of the Communications of the ACM, after having served for a decade as Editor-in-Chief.