Computer Science and Discrete Mathematics (CSDM)

Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings...

High dimensional expansion comes in two flavors: spectral, which relates to random walks;  and cosystolic, which relates to chains of linear maps. The later is a more mysterious notion, which turns out related to a variety of applications such as...

A locally testable code (LTC) is an error-correcting code equipped with a tester T that, given an input string x, queries only a small number of positions and rejects x with probability proportional to its distance from the code. Classic examples of...

Private Information Retrieval (PIR) is a method for a user to interact with t non-colluding servers and read some entry of a database of size n without revealing to the servers anything about which entry of the database was read. After a long line...

For every finite set of points in the plane, if every line going through any two of them contains a third, then they all lie on a single line. This ``local-to-global" theorem (which you can play with proving)  has many generalizations, to higher...

In both computer science and economics, efficiency is a cherished property. The field of algorithms is almost solely focused on their efficiency. The goal of AI research is to increase efficiency by reducing human labor.  In economics, the main...

In 2021 Avi gave a talk titled “Linear spaces of matrices” (see https://www.youtube.com/watch?v=H1H0OkZfZXw). As shown there, the study of linear spaces of matrices (which we call matrix spaces) arises naturally (and independently) in many different...

Two central results in modern complexity theory can be summed up as follows:

Everything provable is provable in zero knowledge (NP ⊆ CZK); and

Everything provable is locally checkable (NP = PCP[log n, 1]).

In a pair of recent works, we show how to...

Two matrices are called equivalent if one can be transformed into the other by multiplying with invertible matrices on the left and right. Extending this idea to 3-tensors, it is natural to define two 3-tensors as isomorphic if they can be...

We show that for all functions t(n)≥n, every multitape Turing machine running in time t can be simulated in space only O(tlogt‾‾‾‾‾√). This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time t in O(t/logt) space from...