Non-commutative arithmetic circuits: depth reduction and size lower bounds

DOI10.1016/S0304-3975(97)00227-2zbMath0912.68046MaRDI QIDQ1274913

Jia Jiao, Meena Mahajan, V. Vinay, Eric W. Allender

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

arithmetic circuitsdepth complexityAuxPDAscon-commutative computationskew circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

NL-printable sets and nondeterministic Kolmogorov complexity, Lower Bounds for Sums of Powers of Low Degree Univariates, Evaluating Matrix Circuits, Skew circuits of small width, Dual VP classes, Approximation of boolean functions by combinatorial rectangles, Complexity of regular functions, Arithmetic circuits: the chasm at depth four gets wider, Evaluation of circuits over nilpotent and polycyclic groups, Characterizing Valiant's algebraic complexity classes, Counting paths in VPA is complete for \(\#\mathrm{NC}^1\), Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}}, Unnamed Item, Integer circuit evaluation is PSPACE-complete, Computing LOGCFL certificates, Improved bounds for reduction to depth 4 and depth 3, Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata, Unnamed Item, Lower bounds for arithmetic circuits via the Hankel matrix, Algebraic Complexity Classes, A Selection of Lower Bounds for Arithmetic Circuits, Towards Optimal Depth Reductions for Syntactically Multilinear Circuits, Testing properties of functions on finite groups, On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Unnamed Item, Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees, How hard is computing the edit distance?, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On quasilinear-time complexity theory
• NP is as easy as detecting unique solutions
• The complexity of optimization problems
• On uniform circuit complexity
• Properties that characterize LOGCFL
• An arithmetic model of computation equivalent to threshold circuits
• A very hard log-space counting class
• The complexity of computing maximal word functions
• Depth reduction for circuits of unbounded fan-in
• The complexity of iterated multiplication
• Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits
• A note on logspace optimization
• A circuit-based proof of Toda's theorem
• The complexity of ranking simple languages
• Fast Parallel Computation of Polynomials Using Few Processors
• PP is as Hard as the Polynomial-Time Hierarchy
• P-uniform circuit complexity
• Log Depth Circuits for Division and Related Problems
• Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• On Threshold Circuits and Polynomial Computation
• Circuit Definitions of Nondeterministic Complexity Classes
• On the Tape Complexity of Deterministic Context-Free Languages
• A Uniform Circuit Lower Bound for the Permanent
• Relationships among $PL$, $\#L$, and the determinant
• Randomness-optimal unique element isolation, with applications to perfect matching and related problems
• Depth reduction for noncommutative arithmetic circuits
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers