Computer Science and Discrete Mathematics (CSDM)

The study of Turán numbers of graphs and hypergraphs is a rich problem in extremal combinatorics. The Turán problem asks, given a fixed forbidden (hyper)graph F, what is the maximum number of edges in an F-free (hyper)graph in terms of the number of...

High-dimensional expanders (HDX) are a generalization of expander graphs which have seen various applications in coding theory, PCPs, pseudorandomness, derandomization, approximate sampling, and beyond. One technique for proving a complex is an HDX...

Last week we defined the Linial--Meshulam model for random 2 dimensional simplicial complexes and discussed two notions of connectivity for it: Vanishing of its 1st cohomology with F2 coefficients, and vanishing of its fundamental group. This time...

In this talk, I will explore the fascinating landscape of assumptions in quantum cryptography—especially, how little we need to assume to build secure quantum protocols. We will cover key cryptographic primitives including quantum encryption...

Inspired by the Erdos--Renyi model for random graphs, Linial and Meshulam devised in 2006 a model for random 2-dimensional simplicial complexes. The goal of this talk (and the next) is to present some nice results about the behavior of these random...

Large language models (LLMs) sometimes generate statements that are plausible but factually incorrect—a phenomenon commonly called "hallucination." We argue that these errors are not mysterious failures of architecture or reasoning, but rather...

In this talk we will construct (approximate) locally list decodable codes from high dimensional expanders (HDXs).

Last week we saw that locally list decoding is a powerful tool from coding theory. We also got a subspace-based construction of...

Over 40 years ago, Karp, Upfal, and Wigderson posed a central open question in parallel computation: how many adaptive rounds are needed to find a basis of a matroid using only independence queries? Their pioneering work gave an upper bound of O(n‾√...

Can we encode data in a way that it is recoverable even when 1) most data becomes corrupted, and 2) we can only read a sub-constant fraction of the database? This is the central question of local list decoding, a powerful tool from coding theory...

A conjecture of Komlós states that the discrepancy of any collection of unit vectors is O(1), i.e., for any matrix A with unit columns, there is a vector x with -1,1 entries such that |Ax|∞=O(1). The related Beck-Fiala conjecture states that any set...