All reports by Author Jeroen Zuiddam:

__
TR21-035
| 13th March 2021
__

Robert Robere, Jeroen Zuiddam#### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

Revisions: 1

__
TR20-030
| 9th March 2020
__

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam#### Barriers for Rectangular Matrix Multiplication

__
TR20-029
| 6th March 2020
__

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam#### Geometric Rank of Tensors and Subrank of Matrix Multiplication

__
TR17-034
| 21st February 2017
__

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam#### On algebraic branching programs of small width

Revisions: 1

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam

Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the ... more >>>

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>