Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with multilinear arithmetic formulas:
TR06-001 | 1st January 2006
Ran Raz, Iddo Tzameret

The Strength of Multilinear Proofs

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

TR17-156 | 15th October 2017
Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

ISSN 1433-8092 | Imprint