Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>
We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:
• An explicit hitting set of quasipolynomial size for ...
more >>>
We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.
This is part of a recent ... more >>>
For every $n$, we construct a sum-of-squares identitity
\[ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2\,,\]
where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.
The same bound holds over any field of positive characteristic.
