Keynote Speakers
Unifying keynote speakers
Adi Shamir, Weizmann Institute of Science, Israel
Title: Error Resilient Space Partitioning
Abstract: In this talk I will describe a new type of space partitioning which bridges the gap between continuous and discrete spaces in an error resilient way. It is motivated by the problem of rounding noisy measurements from some continuous space such as Rd to a discrete subset of representative values, in which each tile in the partition is defined as the preimage of one of the output points. Standard rounding schemes seem to be inherently discontinuous across tile boundaries, but in this paper we show how to make it perfectly consistent (with error resilience ε) by guaranteeing that any pair of consecutive measurements X1 and X2 whose L2 distance is bounded by ε will be rounded to the same nearby representative point in the discrete output space. To achieve this resilience, we allow a few bits of information about the first measurement X1 to be unidirectionally communicated to and used by the rounding process of the second measurement X2. Minimizing this revealed information can be particularly important in privacy-sensitive applications such as COVID-19 contact tracing, in which we want to find out all the cases in which two persons were at roughly the same place at roughly the same time, by comparing cryptographically hashed versions of their itineraries in an error resilient way.
The main problem we consider in this paper is to characterize the achievable tradeoffs between the amount of information provided and the error resilience for various dimensions. We analyze the problem by considering the possible colored tilings of the space with k available colors, and use the color of the tile in which X1 resides as the side information. We obtain our upper and lower bounds with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Sperner’s lemma, and Cech cohomology. In particular, we show that when Xi ∈ Rd, communicating log2(d+1) bits of information is both sufficient and necessary (in the worst case) to achieve positive resilience, and when d=3 we obtain a tight upper and lower asymptotic bound of (0.561…)k1/3 on the achievable error resilience when we provide log2(k) bits of information about X1‘s color.
Bio: Adi Shamir is a Professor in the Faculty of Mathematics and Computer Science at the Weizmann Institute. He has made numerous contributions to the fields of cryptography and computer science, including co-inventing the Rivest–Shamir–Adleman (RSA) algorithm, the Feige–Fiat–Shamir identification scheme, and the technique of differential cryptanalysis. He has received many awards and prizes, including the ACM Turing Award in 2002 shared with Ron Rivest and Len Adleman.
Toniann Pitassi, University of Toronto, Canada
Title: Algebraic Proof Systems
Abstract: Given a set of polynomial equations over a field, how hard is it to prove that they are simultaneously unsolvable?
In the last twenty years, algebraic proof systems for refuting such systems of equations have been studied, revealing close connections to both upper bounds (connections between short refutations and efficient approximation algorithms) and lower bounds. In particular, the Ideal Proof System (IPS) is a simple yet powerful algebraic proof system introduced by Grochow and Pitassi, who proved that lower bounds for IPS imply that VP is not equal to VNP. Recently, connections in the other direction have been made, showing that circuit lower bounds imply IPS lower bounds.
In this talk I will survey the landscape of algebraic proof systems, focusing on their connections to complexity theory, derandomization, and propositional proof complexity. We will discuss the lower bounds to date, and some surprising upper bounds. Finally we end with open problems, including some progress towards proving superpolynomial lower bounds for bounded-depth algebraic proofs.
Bio: Toniann Pitassi is a Professor in the Department of Computer Science and the Department of Mathematics at the University of Toronto. Her field is computational complexity theory and in particular proof complexity, where she has made numerous research contributions to the theory of lower and upper bounds for computational and proof problems. She was elected an ACM Fellow in 2018.
Andrei Bulatov, Simon Fraser University, Canada
Title: Symmetries and Complexity
Abstract: The Constraint Satisfaction Problem (CSP) and a number of problems related to it has seen major advances during the past three decades. In many cases the leading driving force that made these advances possible has been the so-called algebraic approach that uses symmetries of constraint problems and tools from algebra to determine the complexity of problems and design solution algorithms. In this presentation we give a high level overview of the main ideas behind the algebraic approach illustrated by examples ranging from the regular CSP, to counting problems, to optimization and promise problems, to graph isomorphism.
Bio: Andrei A. Bulatov is a Professor in the School of Computing Science at Simon Fraser University. He received his PhD in 1995 and Habilitation in 2008 from the Ural State University. He joined Simon Fraser University in 2004 after working for several years at the Ural State University and then the University of Oxford. His main research interests are in the Constraint Satisfaction Problem, homomorphisms, and universal algebra.
Keynote speakers Track A (Algorithms, Complexity, and Games)
Keren Censor-Hillel, Technion, Israel
Title: Distributed Subgraph Finding: Progress and Challenges
Abstract: This talk surveys the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. I will discuss techniques and highlight some intriguing open problems.
Bio: Keren Censor-Hillel is an Associate Professor in the Department of Computer Science at the Technion. She completed her PhD thesis, for which she received the Principles of Distributed Computing Doctoral Dissertation Award, in 2010 and joined the Technion in 2013 after being a Simons Postdoctoral Fellow at MIT. Censor-Hillel received an Alon Fellowship, awarded by the Israeli Academy of Science, in 2013. She is a recipient of a 2016 Krill Prize given by The Wolf Foundation, a 2017 ERC Starting Grant by the European Commission and a 2018 Henry Taub Prize for Academic Excellence.
David Woodruff, Carnegie Mellon University, USA
Title: A Very Sketchy Talk
Abstract: We give an overview of dimensionality reduction methods, also referred to as “sketching”, for a number of problems in optimization, first surveying work using such methods for classical problems including regression, low rank approximation, and natural variants. We then survey recent work applying sketching to column subset selection, kernel methods, sublinear algorithms for structured matrices, tensors, trace estimation, and so on. The focus in the talk will be on fast algorithms.
Bio: David Woodruff joined the algorithms and complexity group at IBM Almaden in 2007, after completing his PhD at MIT in Theoretical Computer Science. He is currently an Associate Professor of Computer Science at Carnegie Mellon University. His interests are in compressed sensing, communication, numerical linear algebra, sketching, and streaming.
Keynote speaker Track B (Automata, Logic, Semantics, and Theory of Programming)
Christel Baier, Technical University of Dresden, Germany
Title: From verification to causality-based explications
Abstract: The early success story of the model checking approach relies fundamentally on two features. First, the algorithms provide a push-button technology: As soon as the model and specification have been generated, one obtains a result in a fully automated way. Second, if the algorithm terminates with a negative result, then it can infer counterexamples to the specification. Counterexamples are the first instances for what we use the term explication, which refers to a mathematical concept that in some way sheds light on why the model checker has returned the result. While counterexamples are single instances of execution traces violating the specification, they provide little insights in what causes the specification violation. To enhance the system transparency, more crisp explications for the satisfaction or violation of properties are demanded. The talk presents an overview of selected techniques that go in this direction by using formal notions of causality and responsibility to explicate verification results.
Bio: Christel Baier is a full professor and head of the chair for Algebraic and Logic Foundations of Computer Science at the Faculty of Computer Science of the Technische Universität Dresden since 2006. From the University of Mannheim she received her Diploma in Mathematics in 1990, her Ph.D. in Computer Science in 1994 and her Habilitation in 1999. She was an associate professor for Theoretical Computer Science at the University of Bonn from 1999 to 2006. She was member of the DFG (German Research Foundation) review board for computer science from 2012 to 2019, and is a member of the DFG senate commission on Research Training Groups since 2020. Since 2011 she is a member of Academia Europaea. Her research focuses on modeling, specification and verification of reactive systems, quantitative analysis of stochastic systems, probabilistic model checking, temporal and modal logics and automata theory.