Mary Cryan
Title: An asymptotically optimal mixing-time bound on the bases-exchange Markov chain for a matroid
We discuss recent progress on the problem of sampling bases of a matroid. In particular, we will discuss a modified log-Sobolev inequality for r-homogeneous strongly log-concave distributions. As a consequence, we obtain an asymptotically optimal mixing time bound for the bases-exchange chain and a concentration result for such distributions.
Joint work with Heng Guo and Giorgos Mousa.
​
Adria Gascon
Title: Summation and Amplification in the Shuffle Model
I will first introduce the recently proposed shuffle model of differential
privacy. Secondly, I will present our recent results in [1],
including (i) a method for private real-valued summation in the one message shuffle
model (where each party is limited to a single message), (ii) matching lower
bounds on achievable accuracy and (iii) a new amplification by shuffling
result for arbitrary local randomizers. Finally, I shall present results in [2]
on real summation in the many message shuffle model which follow from
previous work on secure summation from anonymity by Ishai et al. and how
to construct private summation from secure summation.
[1] The Privacy Blanket of the Shuffle Model: https://arxiv.org/abs/1903.02837
[2] Differentially Private Summation with Multi-Message Shuffling: https://arxiv.org/abs/1906.09116
Paul Goldberg
Title: The Computational Complexity of Consensus-Halving, Necklace-Splitting, and Ham Sandwich Bisection
We describe three problems that have a common theme of fair division. We present recent results showing that they are all PPA-complete (in the talk, I will explain the complexity class PPA, and how it indicates computational hardness). These are the first examples of "natural" computational problems that are known to be PPA-complete, where "natural" has two meanings: The problems were identified independently from the work on PPA and related complexity classes; also they do not have general boolean circuits (or equivalently, polynomial-time Turing machines) embedded explicitly in the problem definition.
Link for necklace-splitting and ham sandwich bisection: https://doi.org/10.1145/3313276.3316334
Link for consensus-halving:https://doi.org/10.1145/3188745.3188880
Christian Ikenmeyer
Title: Geometric Complexity Theory
Geometric complexity theory is an ambitious program initiated in 2001 by Ketan Mulmuley and Milind Sohoni towards solving the famous P vs NP problem (more specifically, Leslie Valiant's algebraic variant of it) by using methods from algebraic geometry and representation theory. During the last few years there has been a significant amount of research activity related to this program. In this talk I explain some basic ideas and recent developments.
Christian Konrad
Title: Randomized Greedy Matching in the Age of Massive Data Sets
Consider the following randomized algorithm for finding matchings in graphs: Iterate through the set of edges in uniform random order and add the current edge to an initially empty matching if possible. This simple algorithm, denoted the Randomized Greedy Matching (RGM) algorithm, has first been studied in the early '90s in a work by Dyer and Frieze who revealed many of its interesting properties. More recently, driven by research into massive data set algorithms, new properties of the RGM algorithm have been discovered and exploited, and many state-of-the-art streaming and distributed algorithms are built upon this algorithm.
In this talk, I will present the Randomized Greedy Matching algorithm, discuss some of its perhaps surprising properties, and give applications in the area of data streaming and distributed computing.
Svetla Nikova
Title: MPC meets the physical world: Threshold Cryptography against Combined Physical Attacks
Recent attacks show that there is a need for protecting implementations jointly against side-channel and fault attacks. Analogously, modern MPC protocols consider active security, i.e. against malicious parties which do not only passively eavesdrop but also actively deviate from the protocol. This provides an opportunity for the field of threshold implementations to evolve with MPC and achieve provable secure implementations against combined passive and active physical attacks.
In this talk we will discuss two recent proposals in this area: CAPA and M&M, which both start from passively secure threshold schemes and extend those with information-theoretic MAC tags for protection against active adversaries. While similar in their most basic structure, the two proposals explore very different adversary models and thus employ completely different implementation techniques. CAPA considers the field-probe-and-fault model, which is the embedded analogue of multiple parties jointly computing a function with at least one of the parties honest. Accordingly, CAPA is strongly based on the actively secure MPC protocol SPDZ and inherits its provable security properties in this model. Since this results in very expensive implementations, M&M works in a similar but more realistic adversary model and uses existing building blocks from previous passively secure implementations to build more efficient actively secure threshold cryptography.
​
Daniel Paulusma
Title: Graph Colouring for Hereditary Graph Classes and Beyond
The Graph Colouring problem is to label the vertices of a graph with the smallest possible number of colours in such a way that no two neighbouring vertices are identically coloured. Graph Colouring is a well-studied problem in Computer Science and Mathematics due to its many application areas. However, it is also well known that even deciding whether a graph can be coloured with at most three colours is NP-complete. We examine, in a systematic way, to what extent the computational complexity of the Graph Colouring problem may change if the input belongs to some restricted graph class. Initially, we restrict the input to hereditary graph classes, that is, classes of graphs closed under vertex deletion. We then consider further restrictions by bounding the diameter or girth as well. Besides surveying known results and techniques, we will point out a number of open problems in this area.
Thomas Sauerwald
Title: Random Walks on Dynamic Graphs: Mixing Times, HittingTimes, and Return Probabilities
We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allows us to capture the progress the random walk makes through t-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round. For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n^2), generalising a well-known result for static graphs. We also provide refined bounds depending on the isoperimetric dimension of the graph, matching again known results for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.
Adi Shamir
Title: A Simple Explanation for the Mysterious Existence of Adversarial Examples with Small Hamming Distance
The existence of adversarial examples in which tiny changes in the input can fool well trained neural networks has many applications and implications in object recognition, autonomous driving, cybersecurity, etc.
However, it is still far from being understood why such examples exist, and which parameters determine the number of input coordinates one has to change in order to mislead the network.
In this talk I will describe a simple mathematical framework which enables us to think about this problem from a fresh perspective, turning the existence of adversarial examples from a baffling phenomenon into a natural consequence of the geometry of R^n with the $L_0$ (Hamming) metric, which can be quantitatively analyzed. An interesting consequence of our analysis is to show that many proposed techniques to immunize deep neural networks against adversarial attacks are unlikely to succeed.
Madhu Sudan
Title: General Strong Polarization
In this talk, we will introduce and explain the "polarization of bounded martingales". This concept came to the fore in a brilliant invention from 2008 by Arikan, who build a powerful class of error-correcting codes called Polar codes, and whose analysis depended on the polarization of a specific bounded martingale. Sufficiently strong analysis of this martingale eventually led to a resolution, in 2013, of a fundamental algorithmic challenge arising from Shannon's seminal 1948 work.
In this talk I will introduce bounded martingales, define polarization and explain how polarization can be analyzed very generally, using elementary techniques. In the second half of the talk I will describe Arikan's polarization technique and the martingale that arises from it, and show how our analysis methods apply to his martingale. Together these results give a simple, complete and general proof of the resolution of the afore-mentioned algorithmic challenge.
Based on joint works with Jaroslaw Blasiok, Venkatesan Gurusawmi, Preetum Nakkiaran, and Atri Rudra (STOC 2018, RANDOM 2018, and ITCS 2019).