Parallel computation with threshold functions
From MaRDI portal
Publication:1107324
DOI10.1016/0022-0000(88)90030-XzbMath0652.68064MaRDI QIDQ1107324
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
threshold modelalternating Turing machineaddress complexitysimulations of deterministic Turing machinesunbounded fan-in parallel computationWRAM
Related Items
Simulation of PRAMs with scan primitives by unbounded fan-in circuits, Speedup of determinism by alternation for multidimensional Turing machines, The parallel complexity of integer prefix summation, A note on some languages in uniform \(ACC^ 0\), On uniformity within \(NC^ 1\), Iterated multiplication in \(VTC^0\), On the relative complexity of some languages in \(NC^ 1\), Extensions of an idea of McNaughton, Extensions of MSO and the monadic counting hierarchy, On the computational complexity of the Dirichlet Problem for Poisson's Equation, Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts, On counting propositional logic and Wagner's hierarchy, Expressive power of SQL., A note on uniform circuit lower bounds for the counting hierarchy (extended abstract), Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\), A characterization of definability of second-order generalized quantifiers with applications to non-definability, On the computational efficiency of symmetric neural networks, Lower bounds against weakly-uniform threshold circuits, Some notes on threshold circuits, and multiplication in depth 4, On uniformity and circuit lower bounds, String Matching: Communication, Circuits, and Learning., Time lower bounds do not exist for CRCW PRAMs, The complexity of computing symmetric functions using threshold circuits, \(NC^ 1\): The automata-theoretic viewpoint, Computing with discrete multi-valued neurons, Root finding with threshold circuits, Extensions to Barrington's M-program model, An oracle separating \(\oplus P\) from \(PP^{PH}\), On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits, Monotone circuits for monotone weighted threshold functions, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), Lower bounds for invariant queries in logics with counting., Cellular automata and discrete neural networks
Cites Work
- The complexity of computing the permanent
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A note on the parallel computation thesis
- On the construction of parallel computers from various basis of Boolean functions
- The complexity of combinatorial problems with succinct input representation
- On uniform circuit complexity
- A characterization of the power of vector machines
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Tape bounds for time-bounded Turing machines
- Simulation of Parallel Random Access Machines by Circuits
- Parity, circuits, and the polynomial-time hierarchy
- Constant Depth Reducibility
- The Complexity of Enumeration and Reliability Problems
- Finding the maximum, merging, and sorting in a parallel computation model
- Ultracomputers
- Alternation
- A universal interconnection pattern for parallel computers
- On Time Versus Space
- Neural networks and physical systems with emergent collective computational abilities.
- Parallelism in random access machines
- Computational Work and Time on Finite Machines
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
