Computer Science and Discrete Mathematics (CSDM)

A line of work has shown how nontrivial uniform algorithms for analyzing circuits can be used to derive nonuniform circuit lower bounds. In this talk, I will show in depth how the nonexistence of nontrivial circuit-analysis algorithms can also imply...

Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems...

The All-Pairs Min-Cut problem (APMC) asks to compute the minimum cut (or equivalently, the maximum flow) between all pairs of nodes in a graph.1 The naive solution of making n^2 calls to a single-pair min-cut algorithm was surpassed in 1961 by a...

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