An arithmetic model of computation equivalent to threshold circuits
From MaRDI portal
Publication:1186610
DOI10.1016/0304-3975(92)90335-DzbMath0745.68043OpenAlexW2077942962MaRDI QIDQ1186610
Carl Sturtivant, Gudmund Skovbjerg Frandsen, Joan. Boyar
Publication date: 28 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90335-d
circuitsarbitrary fan-in Boolean circuit complexityarithmetic modelBoolean threshold computationscharacteristic-two finite fieldsfan-in arithmetic gates
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (6)
Some results on uniform arithmetic circuit complexity ⋮ Extensions of an idea of McNaughton ⋮ On read-once threshold formulae and their randomized decision tree complexity ⋮ The computational efficacy of finite-field arithmetic ⋮ Non-commutative arithmetic circuits: depth reduction and size lower bounds ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- The computational efficacy of finite-field arithmetic
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- Log Depth Circuits for Division and Related Problems
This page was built for publication: An arithmetic model of computation equivalent to threshold circuits
