62 citations · 222 across the 34 of their papers we have counts for
4 papers · 1 filter
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen +3
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows th…
Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective
Christian Ikenmeyer, Vladimir Lysikov
The main purpose of this paper is pedagogical. Despite its importance, all proofs of the correctness of Strassen's famous 1969 algorithm to multiply two 2x2 matrices with only seve…
Polynomials and the exponent of matrix multiplication
Luca Chiantini, Jonathan D. Hauenstein, Christian Ikenmeyer +2
We define tensors, corresponding to cubic polynomials, which have the same exponent as the matrix multiplication tensor. In particular, we study the symmetrized matrix multipli…
On algebraic branching programs of small width
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 pr…