Uncategorized

Date: 18 June 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Karen Azari
Title: On the Provable Security of Prefix-constrained Pseudorandom Functions

Abstract:
In the field of cryptography, we propose protocols that provide strong provable security guarantees, that is, one can mathematically prove that attacks against the scheme are impossible, or at least as hard to achieve as solving a computational problem that mathematicians failed to solve despite extensive research. When analyzing a more involved scheme that is based on several simpler cryptographic primitives, we prove that any attack against the scheme implies an attack against one of the underlying building blocks, where security of the building blocks in turn is based on mathematical hardness assumptions. In this talk, I will discuss the difficulty of proving security of so-called constrained pseudorandom functions (CPRFs).

A CPRF is a PRF with the following additional functionality: Given the secret key and a constraint, one can generate a constrained key which allows to evaluate the PRF on all inputs satisfying the constraint. For security, one requires that the function output on inputs not satisfying the constraint should remain pseudorandom. A prominent example of a CPRF is the construction of Goldreich, Goldwasser and Micali [GGM84], which supports prefix constraints and is based on pseudorandom generators. While selective security, where the adversary has to commit to its choices in the beginning of the security experiment, is relatively easy to prove for the GGM CPRF, it remained open for a long time to prove the stronger notion of adaptive security, where the adversary is allowed to make its choices on-the-fly, depending on what they learn during the game. I will discuss the difficulty of proving adaptive security of the GGM PRF and provide a brief intuition on how we could finally solve the problem using a new rewinding proof technique.

Date: 22 May 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Martin Costa
Title: Vizing’s Theorem in Near-Linear Time

Abstract:
Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(mn^(1/2)) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Very recently, this runtime bound was further improved to Õ(n^2) by [Assadi et al., 2024] and Õ(mn^(1/4)) by [Bhattacharya et al., 2024].

In this talk, I will present a randomized algorithm that computes a (Δ + 1)-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem.

Date: 08 May 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Martin Schirneck
Title: Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks

Abstract:
This talk is about the design of fault-tolerant data structures that can report graph parameters like distances or connectivity even after some edges of the underlying graph G have failed. An important tool in the area are (L,f)-replacement path coverings (RPCs). These are families of subgraphs of G that guarantee the following property for every set F of at most f edge failures and every pair of vertices s and t: If there is a shortest s-t-path in the graph G-F that has at most L edges, then at least one subgraph in the RPC contains no edge of F but all edges of this replacement path. We present a new construction of (L,f)-replacement path coverings whose parameters improve over previous works by Weimann and Yuster [FOCS 2010] as well as Karthik and Parter [SODA 2021]. We then briefly discuss how this can be used to construct fault-tolerant data structures for shortest paths and even for NP-hard problems like k-Path and k-Clique.

The talk is based on joined work with Davide Bilò, Keerti Choudhary, Sarel Cohen, and Tobias Friedrich that appeared at AAAI 2025.

Date: 10 April 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Maximilian Vötsch
Title: The Power of Random Projections

Abstract:
Many of the optimization problems computer scientists care about can be formulated as a matrix problem of the form min_X ||AX – B|| or min_X,Y ||XY – B|| where constraints on the matrices X and Y encode our problem’s specific structure. In some cases these problems are easy and have analytic solutions, in other cases they are hard and solving the problem exactly involves trying all possible matrices.
What if there was a tool that lets us speed up solving such problems by reducing the search space for “free”? I will talk about one of the most fundamental Lemmas (according to some) in CS, the Johnson-Lindenstrauss lemma and more recent developments in JL-flavored methods, as well as as many applications as we can fit into 60 minutes to give you an idea when to use these techniques in your own research.

Date: 27 March 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: A. R. Sricharan
Title: How to Concentrate If You Must

Abstract:
Random events happen a lot, generating random variables in their wake. Chernoff’s bound says that you can be pretty sure that these random variables are very close to where you expect them to be. One does not think twice about when to apply a Chernoff bound, but one (yours truly) does indeed think multiple times and gets oneself mightily confused on how to go about doing this.

I tried a month ago to get to the bottom of this, and I have a few observations and many many more questions to share. It is related to, among other things,

1. Legendre transforms in physics,
2. Not wanting to solve integrals,
3. Strong convexity, and who would have guessed,
4. The Multiplicative Weights Update method.