Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-COMMUTATIVE CIRCUITS:
Reports tagged with Non-commutative circuits:
TR15-022 | 9th February 2015
Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Lower bounds for non-commutative skew circuits

Revisions: 1

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


TR17-135 | 10th September 2017
Ramprasad Saptharishi, Anamay Tengse

Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

Revisions: 1

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


TR18-095 | 11th May 2018
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Hardness Amplification for Non-Commutative Arithmetic Circuits

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


TR24-026 | 15th February 2024
Pavel Hrubes

A subquadratic upper bound on sum-of-squares compostion formulas

Revisions: 1

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.

more >>>

TR24-099 | 5th June 2024
Pavel Hrubes

A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials

For every $n$, we construct a sum-of-squares identity
$ (\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.

As an application to ... more >>>




ISSN 1433-8092 | Imprint