Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with formulas:
TR10-075 | 22nd April 2010
Ben Reichardt

Least span program witness size equals the general adversary lower bound on quantum query complexity

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

TR11-134 | 9th October 2011
Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

Separating multilinear branching programs and formulas

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

ISSN 1433-8092 | Imprint