Computer Science and Discrete Mathematics (CSDM)

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

Given linear equations over a finite field and under infinity norm, the Short-Integer-Solution (SIS^inf) problem asks to find a solution where each entry is a small number.

In 2021, Chen, Liu, and Zhandry presented an efficient quantum algorithm for...

Matrix-perturbation bounds quantify how the spectral characteristics of a baseline matrix A change under additive noise E. Classical results, including Weyl’s inequality for eigenvalues and the Davis–Kahan theorem for eigenvectors and eigenspaces...