Computer Science and Discrete Mathematics (CSDM)

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

Boosting is a fundamental and widely used method in machine learning, which determines that weak learnability of binary functions implies strong learnability. Traditionally, boosting theory has primarily focused on symmetric 0-1 loss functions...

A principal challenge in realizing the potential of quantum computing lies in our ability to perform computations fault-tolerantly, in the presence of the noise inherent to quantum devices. Non-Clifford quantum gates, which are analogous to the...