Computer Science/Discrete Mathematics

Date:
Nov
17
2026

Computer Science/Discrete Mathematics Seminar II

Bitwise-Optimal Cryptography: From One-Wayness to Pseudorandomness and Target Collision Resistance
Benny Applebaum
10:30am|Simonyi 101 and Remote Access

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...

Nov
17
2026

Computer Science/Discrete Mathematics Seminar II

Reed–Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
Prahladh Harsha
11:30am|Simonyi 101 and Remote Access

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...

Nov
23
2026

Computer Science/Discrete Mathematics Seminar I

Quantum Cryptography for the AI Age
Henry Yuen
11:00am|Simonyi Hall 101 and Remote Access

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...

Nov
24
2026

Computer Science/Discrete Mathematics Seminar II

Byzantine Broadcast in $\tilde{O}(n^2)$ Communication
10:30am|Simonyi 101 and Remote Access

We present a deterministic $n$-party Byzantine broadcast protocol secure against $t

Joint work with Jovan Komatovic and Ling Ren. This result was found via extensive discussion and collaboration with ChatGPT dot.

Nov
30
2026

Computer Science/Discrete Mathematics Seminar I

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Josh Alman
11:00am|Simonyi Hall 101 and Remote Access

I’ll talk about new faster algorithms for 3SUM, APSP, and many more problems. They all follow from one new algorithm for quickly computing certain entries of a matrix product. That algorithm was found by Anthropic using an internal model of Claude...