Computer Science & Discrete Mathematics (CSDM)

Computer Science & Discrete Mathematics (CSDM) Seminar

A weekly seminar on topics in theoretical computer science and discrete mathematics

Time: Every Monday 11:00 AM-12:00 PM, and Tuesday 10:30 AM-12:30 PM,   Place: Simonyi 101

Information about CSDM

Upcoming Talk

Foundations for Collective Decision-Making over Complex Decision Spaces

Speaker: Bailey Flanigan, Massachusetts Institute of Technology
When: Monday, November 16, 2026 | 11:00 AM EST
Where: Simonyi Hall 101 and Remote Access

Abstract

Many societal decisions on which we want collective input — from allocating a public budget to deciding how an automated decision rule should behave — have enormous combinatorial spaces of possible outcomes. The standard approach to eliciting public input in such contexts is to elicit element-level judgments (e.g., which decision rule output a person prefers at a single input) and assume they suffice to reconstruct what people want. In this talk, I will present recent work (Flanigan & Si, EC 2026) showing that such elicitation methods fundamentally cannot identify preference structures that deal with global properties of the outcome, such as ensuring that a budget be balanced over impact categories, or that a decision rule treats like people alike. The preference model underlying this result, which generalizes standard choice models to represent priorities over the entire outcome space, also suggests a way forward: eliciting preferences at the level of global priorities rather than local judgements may recover richer preferences efficiently. I will illustrate this with ongoing work on participatory budgeting and discuss the questions it raises for the foundations of preference elicitation over complex decision spaces.

Add to calendar 11/16/2026 11:00 11/16/2026 12:00 America/New_York Computer Science/Discrete Mathematics Seminar I use-title Topic: Foundations for Collective Decision-Making over Complex Decision Spaces Speakers: Bailey Flanigan, Massachusetts Institute of Technology More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-i-637 Many societal decisions on which we want collective input — from allocating a public budget to deciding how an automated decision rule should behave — have enormous combinatorial spaces of possible outcomes. The standard approach to eliciting public input in such contexts is to elicit _element-level_ judgments (e.g., which decision rule output a person prefers at a _single input_) and assume they suffice to reconstruct what people want. In this talk, I will present recent work (Flanigan & Si, EC 2026 [https://urldefense.com/v3/__https:/arxiv.org/pdf/2607.02672__;!!NubF!JoVxPeJO1z91XMFEp5pPnXRWyyRCp4Eta3OaowkOPMKnM1ssvbneNAF1EdBoY4EeqSi9C8Iszi6i$]) showing that such elicitation methods fundamentally cannot identify preference structures that deal with global properties of the outcome, such as ensuring that a budget be balanced over impact categories, or that a decision rule treats like people alike. The preference model underlying this result, which generalizes standard choice models to represent priorities over the entire outcome space, also suggests a way forward: eliciting preferences at the level of _global priorities_ rather than local judgements may recover richer preferences efficiently. I will illustrate this with ongoing work on participatory budgeting and discuss the questions it raises for the foundations of preference elicitation over complex decision spaces. Simonyi Hall 101 and Remote Access a7a99c3d46944b65a08073518d638c23

Upcoming Schedule

Tuesday, Nov 17, 2026 | 10:30am
Benny Applebaum, Tel Aviv University
Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance
 Abstract

We study bitwise-optimal cryptographic primitives: functions in NC⁰ (where each output bit depends on only a constant number of input bits) that achieve exponential security, together with linear stretch for pseudorandom generators (PRGs) and linear compression for universal one-way hash functions (UOWHFs).

We show that any exponentially secure one-way function in NC⁰ implies bitwise-optimal PRGs and UOWHFs, establishing an equivalence between these three primitives in this highly efficient regime. Interestingly, such an equivalence is not known for general, unrestricted cryptographic primitives in the exponential-security regime without additional regularity assumptions.

Our proof relies on new structural results on locally computable functions that allow us to remove the regularity assumption required by previous constructions. Along the way, we also establish a projection-based compression theorem for locally samplable sources.

View additional event details
Add to calendar Tuesday, 2026-11-17 10:30 America/New_York Computer Science/Discrete Mathematics Seminar II use-title Topic: Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance Speakers: Benny Applebaum, Tel Aviv University More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-633 We study bitwise-optimal cryptographic primitives: functions in NC⁰ (where each output bit depends on only a constant number of input bits) that achieve exponential security, together with linear stretch for pseudorandom generators (PRGs) and linear compression for universal one-way hash functions (UOWHFs). We show that any exponentially secure one-way function in NC⁰ implies bitwise-optimal PRGs and UOWHFs, establishing an equivalence between these three primitives in this highly efficient regime. Interestingly, such an equivalence is not known for general, unrestricted cryptographic primitives in the exponential-security regime without additional regularity assumptions. Our proof relies on new structural results on locally computable functions that allow us to remove the regularity assumption required by previous constructions. Along the way, we also establish a projection-based compression theorem for locally samplable sources. Simonyi 101 and Remote Access a7a99c3d46944b65a08073518d638c23
Tuesday, Nov 17, 2026 | 11:30am
Prahladh Harsha, Tata Institute of Fundamental Research
Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
 Abstract

Understanding the limits of list-decodability of Reed–Solomon (RS) codes has been one of the most important open problems in algebraic coding theory. In the RS list-decoding problem, we are given $n$ distinct points $a_1, \ldots, a_n$ in a finite field $\mathbb{F}$ and a received word $(y_1, \ldots, y_n) \in \mathbb{F}^n$. The goal is to find all polynomials $P \in \mathbb{F}[X]$ of degree at most $k$ that agree with the received word on at least $A$ points, i.e., $P(a_i) = y_i$ for at least $A$ indices $i$. The central question is how small the agreement $A$ can be while the list of such polynomials stays polynomially small and can be found efficiently. RS codes are said to be list-decodable up to capacity if this is possible for $A = (1+\epsilon)k$, for every $\epsilon > 0$.

Recently, in a remarkable breakthrough, Brakensiek, Chen, Putterman, Zhang, and Zheng showed that RS codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to resolve the proximity-gaps question for RS codes.

In this talk, I’ll give a transparent exposition of these results, with an emphasis on explaining why the approach works. I’ll compare these results with previous approaches and give a complete proof of the algorithmic list-decodability result. Time permitting, I’ll also discuss the extension to the proximity-gaps problem.

Based on joint work with Mrinal Kumar and Ramprasad Saptharishi.

View additional event details
Add to calendar Tuesday, 2026-11-17 11:30 America/New_York Computer Science/Discrete Mathematics Seminar II use-title Topic: Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps Speakers: Prahladh Harsha, Tata Institute of Fundamental Research More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-ii-631 Understanding the limits of list-decodability of Reed–Solomon (RS) codes has been one of the most important open problems in algebraic coding theory. In the RS list-decoding problem, we are given $n$ distinct points $a_1, \ldots, a_n$ in a finite field $\mathbb{F}$ and a received word $(y_1, \ldots, y_n) \in \mathbb{F}^n$. The goal is to find all polynomials $P \in \mathbb{F}[X]$ of degree at most $k$ that agree with the received word on at least $A$ points, i.e., $P(a_i) = y_i$ for at least $A$ indices $i$. The central question is how small the agreement $A$ can be while the list of such polynomials stays polynomially small and can be found efficiently. RS codes are said to be list-decodable up to capacity if this is possible for $A = (1+\epsilon)k$, for every $\epsilon > 0$. Recently, in a remarkable breakthrough, Brakensiek, Chen, Putterman, Zhang, and Zheng showed that RS codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to resolve the proximity-gaps question for RS codes. In this talk, I’ll give a transparent exposition of these results, with an emphasis on explaining _WHY_ the approach works. I’ll compare these results with previous approaches and give a complete proof of the algorithmic list-decodability result. Time permitting, I’ll also discuss the extension to the proximity-gaps problem. Based on joint work with Mrinal Kumar and Ramprasad Saptharishi. Simonyi 101 and Remote Access a7a99c3d46944b65a08073518d638c23
Monday, Nov 23, 2026 | 11:00am
Henry Yuen, Columbia University
Quantum Cryptography for the AI Age
 Abstract

Quantum computers will pose a major threat to the cryptography we use today. But quantum physics also lets us do things that are impossible classically. With quantum key distribution, for example, two people can share a secret key without a computational hardness assumption. We can even have digital tokens that can’t be copied, such as quantum money and one-shot signatures.

In this talk I’ll highlight two examples of “quantum-powered cryptography” and speculate about what they might have to do with AI safety and alignment. First, there’s a whole world of quantum cryptographic primitives that rely on fewer mathematical assumptions than we need classically. Given the recent spate of AI cryptanalysis results, there's urgency in finding cryptosystems that rely on as few assumptions as possible.

Second, I will talk about interactive proofs of physical location. Trustworthy proofs of location are not possible in a classical world, but are possible in a quantum world via *quantum position verification* protocols. I will discuss how such protocols may be helpful for problems in AI alignment (e.g., holding AI agents liable for their actions).

View additional event details
Add to calendar Monday, 2026-11-23 11:00 America/New_York Computer Science/Discrete Mathematics Seminar I use-title Topic: Quantum Cryptography for the AI Age Speakers: Henry Yuen, Columbia University More: https://www.ias.edu/math/events/computer-sciencediscrete-mathematics-seminar-i-636 Quantum computers will pose a major threat to the cryptography we use today. But quantum physics also lets us do things that are impossible classically. With quantum key distribution, for example, two people can share a secret key without a computational hardness assumption. We can even have digital tokens that can’t be copied, such as quantum money and one-shot signatures. In this talk I’ll highlight two examples of “quantum-powered cryptography” and speculate about what they might have to do with AI safety and alignment. First, there’s a whole world of quantum cryptographic primitives that rely on fewer mathematical assumptions than we need classically. Given the recent spate of AI cryptanalysis results, there's urgency in finding cryptosystems that rely on as few assumptions as possible. Second, I will talk about interactive proofs of physical location. Trustworthy proofs of location are not possible in a classical world, but are possible in a quantum world via *quantum position verification* protocols. I will discuss how such protocols may be helpful for problems in AI alignment (e.g., holding AI agents liable for their actions). Simonyi Hall 101 and Remote Access a7a99c3d46944b65a08073518d638c23
More Events

Past Seminars Archive

Past Seminars Archive

Information About CSDM