Events

Title: Deterministic Algorithms and Faster Algorithms for Submodular Maximization subject to a Matroid Constraint

Abstract: Maximization of submodular functions under various constraints is a fundamental problem that has been studied extensively.

In this talk I will discuss submodular functions and interesting research questions in the field.

I will present several new techniques that lead to both deterministic algorithms and faster randomized algorithms for maximizing submodular functions.

In particular, for monotone submodular functions subject to a matroid constraint we design a deterministic non-oblivious local search algorithm that has an approximation guarantee of 1 - 1/e - \eps (for any \eps > 0), vastly improving over the previous state-of-the-art 0.5008-approximation.

For general (non-monotone) submodular functions we introduce a new tool, that we refer to as the extended multilinear extension, designed to derandomize submodular maximization algorithms that are based on the successful ``solve fractionally and then round'' approach.

Short bio: Niv Buchbinder is a professor in the department of Statistics and Operations Research at Tel Aviv university. He received his Ph.D. in Computer Science from the Technion, Israel in 2008, and then spent two years as a post-doctoral researcher at Microsoft Research, New England, MA. His primary research interests are algorithms for combinatorial optimization problems in offline and online settings.

Title: There are no good infinite families of toric codes

Abstract: : In this talk we'll give an overview of what toric codes are and what it means for a code to be "good". We'll explain why it is impossible to construct an infinite family of good toric codes, answering a question of Soprunov and Soprunova. This is joint work with Sean Monahan, Matt Satriano, Karen Situ, and Zheng Xie. 

Title: Centralizers in the Plactic Monoid

Abstract: Let u be a word over the positive integers. Motivated in part by a question of representation theory, we study the centralizer set C(u), which consists of words w for which wu and uw are Knuth-equivalent. In particular, we characterize C(u) when u has few letters or is a certain type of decreasing sequence, and we address related enumerative questions.

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

Title: On the Black-Box Complexity of Private-Key Inner-Product Functional Encryption

Abstract: Traditional encryption (secret key and public key encryption) has a very limited functionality. Namely, it allows encryption of data for a single recipient that can recover the entire data. This is typically sufficient for transmitting data over insecure channels, but insufficient for many modern applications, like end-to-end encrypted cloud storage, where partial access to the data might be needed.

Functional encryption (FE) is a cryptographic primitive that can solve this challenge by allowing to generate customized secret keys that are associated with a function f. Decrypting with such a secret key will reveal only f(m), where m is the encrypted message, and reveal nothing else about m. One of the most well studied variants of FE is inner-product functional encryption (IPFE), where the functions f are restricted to linear functions.

All known instantiations of IPFE, even of its secret-key version, require strong assumptions typically used for public-key encryption. In this talk I will give an insight on why this is the case: An impossibility result for black-box constructions of IPFE from secret-key assumptions (like one-way functions).

The core of our proof is based on a new result of extremal combinatorics, which we proof based on Fourier analysis or the Cauchy-Schwartz inequality.

The talk will first introduce the cryptographic background and give an overview about the cryptographic part of the proof. Then, the combinatorial problem we encountered and our solution will be discussed in more detail. The talk will not require any prior knowledge in cryptography.

The full version of the paper presented can be found here: https://eprint.iacr.org/2024/1877

Title: Approximation Algorithms for Flexible Graph Connectivity

Abstract: This is a "non specialist" talk on a couple of results from a long-running project in the area of capacitated network design. The key problem here is to find a sub-graph of minimum cost that satisfies a (global) edge connectivity requirement, where the input is a graph G that has a capacity u(e) and a cost c(e) for each edge e in E(G). (Note: The minimum spanning tree problem is the special case where the connectivity requirement is one and  all edge-capacities are one.)

The results in the talk are from joint work with Bansal, Grout, Ibrahimpur, Khanna, and Simmons.

Title: A Combinatorial Gateway to Calabi-Yau Toric Geometry

Abstract: The goal of this talk is to introduce Calabi-Yau toric geometry from a purely combinatorial perspective, through the rich structures carried by an embedded bipartite graph on a torus called a dimer model.

In the pre-talk, we will demonstrate how matchings, tilings, and quivers naturally encodes deep geometric and physical content. No background in algebraic geometry will be assumed; instead, we’ll build the story from the ground up, with an emphasis on visual intuition and discrete structures.

Next, I will discuss how dimer models simultaneously encode the data of a toric Calabi-Yau singularity and its mirror dual, unifying perspectives from the B-model and A-model of homological mirror symmetry through noncommutative algebras. We will proceed with some recent developments and open problems, including connections to the symplectic geometry of Landau-Ginzburg models and Van den Bergh’s noncommutative resolution conjecture for toric Gorenstein affine singularities. To conclude the talk, we will discuss an example of a higher dimensional generalization and its connection to my recent research works.

This talk is also partially based on two undergraduate research projects in the present semester, where we study variations of dimer models of the same lattice polygon from different choices in the fast inverse algorithm, and implications on the two sides of mirror symmetry:

- (DRP) Dimer Variation and Geometry of Landau-Ginzburg Models, with Kenneth Xiao and Elizabeth Cai (A-model)

- (NSERC USRA) Dimer Variation and NCCR Mutations, with Filip Mildrag and Elana Kalashnikov (B-model)

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

Title: Graphs with High Chromatic Number

Abstract: The classical theorem of Brooks tells us that if a graph G has no colouring with its maximum degree ∆≥3 colours, then it contains a clique with ∆+1 vertices. Does a similar phenomenon occur when the chromatic number is slightly smaller than ∆? Even the next case is unknown: in 1977, Borodin and Kostochka famously conjectured that if ∆≥9 and G has no (∆-1)-colouring then it contains a ∆(G)-clique. We discuss various results and questions around this conjecture.

Title:Compact Lattice Signatures via Iterative Rejection Sampling (ePrint: 2024/2052)

Abstract: This talk reviews the paper by Joel Gärtner that received one of the Best Paper Awards at CRYPTO 2025. The work introduces a new method for constructing lattice signatures using the “Fiat–Shamir with aborts” approach. By carefully designing the rejection condition, the authors significantly lower the rejection probability. This leads to a signature scheme that is much more compact than previous lattice-based Fiat–Shamir signature schemes. In this talk, we will carefully examine the proposed techniques as well as the concrete parameters that enable such compact signatures.

Title:Enumerating planar stuffed maps as hypertrees of mobiles

Abstract: A planar stuffed map is an embedding of a graph into the 2-sphere, considered up to orientation-preserving homeomorphisms, such that the complement of the graph is a collection of disjoint topologically connected components that are each homeomorphic to the 2-sphere with multiple boundaries. This is a generalization of planar maps whose complement of the graph is a collection of disjoint topologically connected components that are each homeomorphic to a disc. In this talk I will outline my work in constructing a bisection between bipartite planar stuffed maps and collections of integer-labelled trees connected by hyperedges such that they form a hypertree. This bijection directly generalizes the Bouttier-Di Franceso-Guitter bijection between bipartite planar maps and mobiles. Additionally, we show that the generating functions of these trees of mobiles satisfy both an algebraic equation, generalizing the case of ordinary planar maps, and a new functional equation. As an example, we explicitly enumerate a class of stuffed quadrangulations.

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

Title: Hash-Based Digital Signatures: An Overview with a Focus on Group Signature Schemes

Abstract: Digital signature schemes are crucial for secure communication, authentication, and data integrity in applications like secure email, financial transactions, and blockchain systems. However, classical schemes (e.g., RSA, ECDSA, Schnorr) are vulnerable to quantum attacks, driving the shift to post-quantum cryptographic alternatives.

Hash-based signature schemes are key because their security relies on cryptographic hash functions, not number-theoretic problems, making them more robust for post-quantum security. These schemes are categorized into one-time, few-time, and many-time signatures. To date, NIST has standardized three many-time hash-based schemes: LMS, XMSS, and SPHINCS+.

Group Signature Schemes (GSS) enable anonymous message signing on behalf of a group, with a designated authority able to reveal the signer's identity when necessary. This feature is critical in privacy-preserving applications like anonymous attestations and reputation systems. Fully dynamic GSSs are particularly valuable as they allow users to join or be revoked without system-wide updates. 

In this talk, I will review key hash-based group signature schemes, including G-Merkle, DGM, DGMT, and SPHINX-in-the-Head, discussing their limitations in scalability and efficiency. I will then introduce DGSP, our new scalable and efficient fully dynamic GSS, and compare it with existing post-quantum alternatives to highlight its advantages.