On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
From MaRDI portal
Publication:1567407
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
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-uniformNC1 ⋮ 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 1
- 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
