On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits

DOI10.1006/jcss.1999.1675zbMath0956.68060OpenAlexW2178086598MaRDI QIDQ1567407

Samir Datta, Manindra Agrawal, Eric W. Allender

Publication date: 12 March 2001

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1999.1675

Mathematics Subject Classification ID

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

Related Items (15)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Uniform derandomization from pathetic lower bounds ⋮ Dual VP classes ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ Parameterised counting in logspace ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ On the Power of Algebraic Branching Programs of Width Two ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Division in logspace-uniformNC¹ ⋮ A model-theoretic characterization of constant-depth arithmetic circuits ⋮ Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ On the power of algebraic branching programs of width two

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Bounded-depth, polynomial-size circuits for symmetric functions
• The complexity of combinatorial problems with succinct input representation
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Parallel computation with threshold functions
• On uniform circuit complexity
• An arithmetic model of computation equivalent to threshold circuits
• On iterated integer product
• A very hard log-space counting class
• Verifying the determinant in parallel
• Non-commutative arithmetic circuits: depth reduction and size lower bounds
• Nondeterministic \(NC^1\) computation
• Gap-definable counting classes
• Bits and relative order from residues, space efficiently
• Depth reduction for circuits of unbounded fan-in
• On ACC
• The complexity of iterated multiplication
• Counting quantifiers, successor relations, and logarithmic space
• On uniformity within \(NC^ 1\)
• Constant Depth Reducibility
• P-uniform circuit complexity
• Log Depth Circuits for Division and Related Problems
• Definability by constant-depth polynomial-size circuits
• Finite monoids and the fine structure of NC ¹
• Fast Parallel Arithmetic via Modular Representation
• On Threshold Circuits and Polynomial Computation
• Circuit Definitions of Nondeterministic Complexity Classes
• Computational Complexity of Probabilistic Turing Machines
• Some results on uniform arithmetic circuit complexity
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Relationships among $PL$, $\#L$, and the determinant
• Natural proofs

This page was built for publication: On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits