Non-commutative arithmetic circuits: depth reduction and size lower bounds
type: Item
instance of: scholarly article
title: Non-commutative arithmetic circuits: depth reduction and size lower bounds
zbMATH Open document ID: 0912.68046
DOI: 10.1016/S0304-3975(97)00227-2
author: Jia Jiao
author: Meena Mahajan
author: V. Vinay
author: Eric Allender
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1238686
zbMATH Keywords: arithmetic circuits
zbMATH Keywords: depth complexity
zbMATH Keywords: con-commutative computation
zbMATH Keywords: AuxPDAs
zbMATH Keywords: skew circuits
MaRDI profile type: Publication
cites work: P-uniform circuit complexity
cites work: The complexity of computing maximal word functions
cites work: A Uniform Circuit Lower Bound for the Permanent
cites work: Depth reduction for circuits of unbounded fan-in
cites work: Depth reduction for noncommutative arithmetic circuits
cites work: A very hard log-space counting class
cites work: A note on logspace optimization
cites work: Relationships among $PL$, $\#L$, and the determinant
cites work: Log Depth Circuits for Division and Related Problems
cites work: An arithmetic model of computation equivalent to threshold circuits
cites work: Q4131653
cites work: Randomness-optimal unique element isolation, with applications to perfect matching and related problems
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
cites work: The complexity of ranking simple languages
cites work: The complexity of iterated multiplication
cites work: Some Exact Complexity Results for Straight-Line Computations over Semirings
cites work: A circuit-based proof of Toda's theorem
cites work: Q3359761
cites work: The complexity of optimization problems
cites work: Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
cites work: Q4470491
cites work: On quasilinear-time complexity theory
cites work: Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
cites work: On Threshold Circuits and Polynomial Computation
cites work: On uniform circuit complexity
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Q4036702
cites work: Fast Parallel Computation of Polynomials Using Few Processors
cites work: NP is as easy as detecting unique solutions
cites work: Properties that characterize LOGCFL
cites work: Circuit Definitions of Nondeterministic Complexity Classes
cites work: A New Pebble Game that Characterizes Parallel Complexity Classes
Recommended article: On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains
Recommended article: Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
Recommended article: Q5111256
Recommended article: Q5121900
Recommended article: Q4904105
Recommended article: A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
Recommended article: On the relative power of reduction notions in arithmetic circuit complexity
Recommended article: Non-commutative arithmetic circuits with division
Recommended article: Q3467518
Recommended article: Lower bounds on monotone arithmetic circuits with restricted depths
description: scientific article; zbMATH DE number 1238686