Seminars

We show that for all functions $t(n) \geq n$, every multitape Turing machine running in time $t$ can be simulated in space only $O(\sqrt{t \log t})$. This is a substantial improvement over Hopcroft, Paul, and Valiant's simulation of time $t$ in $O(t...

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

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

1. Everything provable is provable in zero knowledge (NP ⊆ CZK); and
2. Everything provable is locally checkable (NP = PCP[log n, 1]).

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

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

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