Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Pavel Hrubes:

TR10-040 | 10th March 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Relationless completeness and separations

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.
We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ... more >>>

TR10-021 | 21st February 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Non-commutative circuits and the sum-of-squares problem

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

ISSN 1433-8092 | Imprint