On Threshold Circuits and Polynomial Computation
From MaRDI portal
Publication:4015974
DOI10.1137/0221053zbMath0765.68057OpenAlexW2071732851MaRDI QIDQ4015974
Publication date: 6 December 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0221053
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Related Items
Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ Dual VP classes ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ The dynamic complexity of transitive closure is in DynTC\(^{0}\). ⋮ Depth-efficient threshold circuits for multiplication and symmetric function computation ⋮ Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\) ⋮ The complexity of game isomorphism ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Root finding with threshold circuits ⋮ Green's theorem and isolation in planar graphs ⋮ Non-interactive zero knowledge from sub-exponential DDH ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ Efficient threshold circuits for power series ⋮ Pseudorandom Functions: Three Decades Later ⋮ Quantum neural networks
This page was built for publication: On Threshold Circuits and Polynomial Computation
