All reports by Author Pavel Hrubes:

__
TR10-040
| 10th March 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Relationless completeness and separations

__
TR10-021
| 21st February 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Non-commutative circuits and the sum-of-squares problem

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

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 >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

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 >>>