PICS 2024 Speakers

On the many crucial roles played by randomness in cryptography

Virtually no cryptographic primitive or protocol can be secure without making use of randomness, and hence tools from probability and information theory are essential for analysing them. We will cover a number of interesting examples of this, including the foundations of secure encryption, secret sharing and secure computation.

Causality, Explanation, and Harm

What does it mean that an event C “actually caused” event E? The philosophy literature has been struggling with the problem of defining causality since the days of Hume, in the 1700s. Many of the definitions have been couched in terms of counterfactuals. (C is a cause of E if, had C not happened, then E would not have happened.) In 2001, Judea Pearl and I introduced a new definition of actual cause using causal models, where structural equations model counterfactuals. I will discuss the definition, and then show how causal models can be used to model responsibility, blame, explanation, and harm (among other things) in addition to causality, with a focus on explanation ad harm.

Probabilistic Numerics — Computation as Inference

Numerical computation is the foundation of scientific computing and AI. We will discover that elementary numerical algorithms are extracting information — learning — about mathematical quantities from computations, and that it is possible to quantify uncertainty about this process along the way in a tractable fashion, as probability measures. We will beginn with basic numerical linear algebra, and extend from there to simulation methods for differential equations, and deep learning. The result is a universal framework the quantification of computational uncertainty that natively interacts with the conceptual frameworks of Bayesian machine learning.

Probabilistic verification for neural networks

This course will provide an overview of formal verification for neural networks, which can be used to certify that the networks are robust to adversarial perturbations. Given a set of inputs I and outputs O under some restrictions, checking whether all x points in I map to O can be approximated by bounding f(x) over I, which can be achieved by convex relaxation and propagating the bounds forward through the network. It is also helpful to approximate the set of inputs I’ that are mapped to O, which can be achieved by propagating the bounds backwards. Finally, a probabilistic variant of neural networks, called Bayesian neural networks, will be introduced. Bayesian neural networks return a probability distribution on outputs, so their verification draws on bound propagation and involves bounding the posterior probability.

Probabilistic Network verification

Kleene algebra with tests is an algebraic framework that can be used to reason about imperative programs. It has been applied across a wide variety of areas including program transformations, concurrency control, compiler optimizations, cache control, networking, and more. In these lectures, we will provide an overview of Probabilistic NetKAT, a domain specific language based on Kleene Algebra with Tests. We will illustrate how it can be used as a core framework for probabilistic network verification, including properties like congestion and fault-tolerance.

Information Theory for Relational Query Processing

Conjunctive Query evaluation lies at the core of any modern database management system. This course will cover the use of information theory to answer some fundamental questions in query processing. How large can the output to a query be? How efficiently can we evaluate a query? Is one query always faster than another? These questions can be answered using a fascinating tool: entropic vectors and information inequalities. The lectures contain a gentle introduction to conjunctive queries, then to entropic inequalities, and finally describe their applications to query evaluation.

Hash functions bridging the gap from theory to practice

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical.

Hash functions are used everywhere in computing, e.g., hash tables, sketching, dimensionality reduction, sampling, and estimation. Abstractly, we like to think of hashing as fully-random hashing, assigning independent hash values to every possible key, but essentially this requires us to store the hash values for all keys, which is unrealistic for most key universes, e.g., 64-bit keys.

In practice we have to settle for implementable hash functions, and often practitioners settle for implementations that are too simple in that the algorithms ends up working only for sufficiently random input. However, the real world is full of structured/non-random input.

The issue is severe, for simple hash functions will often work very well in tests with random input. Moreover, the issue is often that error events that should never happen in practice, happen with way too high probability. This does not show in a few tests, but will show up over time when you put the system in production.

Over the last decade there has been major developments in simple tabulation based hash functions offering strong theoretical guarantees, so as to support fundamental properties such as Chernoff bounds, Sparse Johnson-Lindenstrauss transforms, succinct hash tables, fully-random hashing on a given set w.h.p., etc.

I will discuss some of the principles of these developments and offer insights on how far we can bridge from theory (assuming fully-random hash functions) to practice (needing something that can actually implemented efficiently).

Probabilistic circuits: from tractable probabilistic inference to reliable neuro-symbolic AI

Guaranteeing the safety and reliability of deep learning models is of crucial importance, especially in many high-stake application scenarios. In these lectures, I will focus on the key challenge of designing probabilistic deep learning models that are reliable and yet efficient by design. I will do so within the framework of probabilistic circuits: overparametrized and computational graphs that are just neural networks with lots of structure, enough to guarantee the tractable computation of the probabilistic reasoning scenarios of interest, while not compromising their expressiveness. Second, I will discuss how we can use circuits to build a reliable foundation for neuro-symbolic AI. That is, for example, to provably satisfy certain constraints we can express in propositional logic in neural networks as to increase their performance and robustness. These models can be thought as being ``verified by design’’ and I will showcase some recent applications of this constraint satisfaction by design e.g., scaling link prediction in graphs with millions of nodes.