Depth reduction for noncommutative arithmetic circuits

DOI10.1145/167088.167226zbMath1310.68097OpenAlexW2032312352MaRDI QIDQ5248521

Jia Jiao, Eric W. Allender

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167226

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

How hard is to compute the edit distance, A quasi-polynomial-time algorithm for sampling words from a context-free language, Relationships among $PL$, $\#L$, and the determinant, Properties of probabilistic pushdown automata, Computing LOGCFL certificates, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Properties of probabilistic pushdown automata, How hard is computing the edit distance?, The complexity of computing maximal word functions