Events

Abstract: We are going to talk about approximating graphic TSP, which is a variant of TSP where the distances come from shortest paths between vertices of an undirected graph. We will talk about Mömke and Svensson’s approach, which used matchings to improve the approximation ratio, and also our recent generalization that uses b-matchings. This is joint work with Levent Tunçel and Swati Gupta.

Abstract: The study of combinatorial designs includes some of the oldest questions at the heart of combinatorics. In a breakthrough result of 2014, Keevash proved the longstanding Existence Conjecture by showing the existence of (n,q,r)-Steiner systems (equivalently K_q^r-decompositions of K_n^r) for all large enough n satisfying the necessary divisibility conditions. Meanwhile, in recent decades, incremental progress has been made on the celebrated Nash-Williams' Conjecture of 1970, which posits that any large enough, triangle-divisible graph on n vertices with minimum degree at least 3n/4 admits a triangle decomposition. In 2021, Glock, Kühn, and Osthus proposed a generalization of these results by conjecturing a hypergraph version of the Nash-Williams' Conjecture, where their proposed minimum degree K_q^r-decomposition threshold is motivated by hypergraph Turán theory. By using the recently developed method of refined absorption and establishing a non-uniform Turán theory, we tie the K_q^r-decomposition threshold to its fractional relaxation. Combined with the best-known fractional decomposition threshold from Delcourt, Lesgourgues, and Postle, this dramatically closes the gap between what was known and the above conjecture. This talk is based on joint work with Luke Postle.

Abstract: A lot of classical constructions are proven secure the random oracle model. With quantum adversaries, it is necessary to consider a quantum-accessible model allowing the adversary to query the oracle with quantum states. In this talk, we define such an oracle and show its implications on classical security proofs. We will present an example separating the classical and quantum-accessible random oracle models using a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when they can make quantum oracle queries. We further define history-free reductions and show that there is a general lifting result allowing to argue security in the quantum random oracle model when there is a reduction in the classical setting. As an example for this technique we will show how to prove the security of signatures following the Full Domain Hash paradigm.

Abstract: A 1976 theorem of Nesetril and Rodl proves that the class of k-clique-free finite graphs has the ordering property. In this talk, we will define the ordering property and give a probabilistic argument that it holds. We then discuss how a 2005 paper of Kechris, Pestov, and Todorcevic applies the ordering property to topological dynamics.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract: Ramsey's celebrated theorem has two forms — an infinite version and a finite one. A natural way to try to generalize the theorem is to color substructures of a given structure, rather than just subsets of a given set. A 1977 theorem of Nesetril and Rodl provides a sweeping generalization of the finite version of Ramsey's theorem to all relational free-amalgamation classes of finite structures. For the infinite version, things get much more complicated. While a 2022 theorem of mine proves a generalization of the infinite version for finitely-constrained binary free-amalgamation classes, the result in full generality is false dropping either the finite-constraint assumption or the binary assumption. Time permitting, I will discuss joint work with Joey Lakerdas-Gayle discussing some of the strange things that can happen for infinitely-constrained binary free-amalgamation classes.   

Abstract: In 2023 Signal deployed PQXDH, a small change to the handshake that protects new conversations against adversaries who record traffic today and decrypt it with a future quantum computer. Two gaps remain: post-compromise security in the ratchet and authentication in the handshake both still rely on elliptic curves. This talk describes how we closed the first and how we plan to close the second.

In the first part, we look at the challenge of building a post-quantum ratcheted messaging protocol in a bandwidth-constrained setting, and build up Signal’s Sparse Post-Quantum Ratchet, deployed in 2025, step by step through a series of simpler protocols.

In the second part, we look ahead to a new handshake that completes the transition of Signal’s 1:1 messaging with hybrid, deniable authentication. While the post-quantum ratchet feels like an engineering variation on the classical one, the post-quantum key agreement takes a very different shape. Our need to save bandwidth still drives plenty of engineering, including Merkle trees, Falcon signature recovery modes, and context-specific optimizations.

I’ll close with open questions and a brief look at what it will take to make the rest of the Signal app quantum safe.