Jeffrey D. Ullman
(Stanford University, USA), Abstractions in Computer Science Theory
The creative use of abstractions is central to computer science.
But not all abstractions address the same kinds of problems.
We identify four different reasons abstractions appear in computerscience
theory, and focus on the "declarative abstractions," whose purpose
is to raise the level at which we program. Important declarative
abstractions appear in the theory of compiling and the theory of databases.
We shall touch on the most important elements in those two fields.
David Eppstein
(University of California, Irvine, USA), The Complexity of Iterated Reversible Computation
Reversible computation has been studied for over 60 years as a way to evade fundamental physical limits on the power needed for irreversible computational steps, and because quantum computing circuits are necessarily reversible. We study a class of problems based on computing the iterated values of a reversible function. The story leads through Thomason's lollipop algorithm in graph theory, circuit complexity, and reversible cellular automata, to card shuffling, the reflections of light in jewels, and curves on topological surfaces, and involves both PSPACEhard problems and problems with unexpected polynomialtime algorithms.
Mauricio Osorio
(Universidad de las Américas, Puebla, México), A Graph Theoretic Approach for Resilient Distributed Algorithms
Following the immense recent advances in distributed networks, the explosive growth of the Internet, and our increased dependency on these infrastructures, guaranteeing the uninterrupted operation of communication networks has become a major objective in network algorithms. The modern instantiations of distributed networks, such as the Bitcoin network and cloud computing, introduce new security challenges that deserve urgent attention in both theory and practice.
In this talk, I will present a unified framework for obtaining fast, resilient and secure distributed algorithms for fundamental graph problems. Our approach is based on a graphtheoretic perspective in which common notions of resilient requirements are translated into suitably tailored combinatorial graph structures. We will discuss recent developments along the following two lines of research:
 Designing distributed algorithms that can handle various adversarial settings, such as, node crashes and Byzantine attacks. We will mainly provide general compilation schemes that are based on exploiting the highconnectivity of the graph. Our key focus will be on the efficiency of the resilient algorithms in terms of the number of communication rounds.
 Initiating and establishing the theoretical exploration of security in distributed graph algorithms. Such a notion has been addressed before mainly in the context of secure multiparty computation (MPC). The heart of our approach is to develop new graph theoretical infrastructures to provide graphical secure channels between nodes in a communication network of an arbitrary topology.
Finally, I will highlight future directions that call for strengthening the connections between the areas of fault tolerant network design, distributed graph algorithms and information theoretic security.
Merav Parter
(Weizmann Institute of Science, Tel Aviv, Israel), A Graph Theoretic Approach for Resilient Distributed Algorithms
Abstract: Following the immense recent advances in distributed
networks, the explosive growth of the Internet, and our increased
dependency on these infrastructures, guaranteeing the uninterrupted
operation of communication networks has become a major objective in
network algorithms. The modern instantiations of distributed networks,
such as the Bitcoin network and cloud computing, introduce new
security challenges that deserve urgent attention in both theory and
practice.
In this talk, I will present a unified framework for obtaining fast,
resilient and secure distributed algorithms for fundamental graph
pproblems. Our approach is based on a graphtheoretic perspective in
which common notions of resilient requirements are translated into
suitably tailored combinatorial graph structures. We will discuss
recent developments along the following two lines of research:
 Designing distributed algorithms that can handle various adversarial
settings, such as, node crashes and Byzantine attacks. We will mainly
provide general compilation schemes that are based on exploiting the
highconnectivity of the graph. Our key focus will be on the
efficiency of the resilient algorithms in terms of the number of
communication rounds.
 Initiating and establishing the theoretical exploration of security
in distributed graph algorithms. Such a notion has been addressed
before mainly in the context of secure multiparty computation (MPC).
The heart of our approach is to develop new graph theoretical
infrastructures to provide graphical secure channels between nodes in
a communication network of an arbitrary topology.
Finally, I will highlight future directions that call for
strengthening the connections between the areas of fault tolerant
network design, distributed graph algorithms and information theoretic
security.
