Constant Depth Reducibility

DOI10.1137/0213028zbMath0538.68038OpenAlexW1986804393MaRDI QIDQ3325043

Uzi Vishkin, Ashok K. Chandra, Larry J. Stockmeyer

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213028

zbMATH Keywords

parallelismcircuit complexitycombinatorial logic circuitsconstant depth truth table reducibilityprojection reducibilitysize and depth of circuitsunbounded fan-in circuits

Mathematics Subject Classification ID

Related Items (79)

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Equivalence classes and conditional hardness in massively parallel computations ⋮ Analog computation via neural networks ⋮ Threshold circuits of bounded depth ⋮ The complexity of planarity testing ⋮ On ACC ⋮ The complexity class θp2: Recent results and applications in AI and modal logic ⋮ On small depth threshold circuits ⋮ One-way functions and circuit complexity ⋮ A note on neural sorting networks with O(1) time complexity ⋮ A note on some languages in uniform \(ACC^ 0\) ⋮ On uniformity within \(NC^ 1\) ⋮ Limits on the power of concurrent-write parallel machines ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ A note on logspace optimization ⋮ Some results on uniform arithmetic circuit complexity ⋮ Parallel computation with threshold functions ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ Designing checkers for programs that run in parallel ⋮ Efficient parallel circuits and algorithms for division ⋮ Parallel complexity of algebraic operations ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Extensions of an idea of McNaughton ⋮ Parallel complexity of iterated morphisms and the arithmetic of small numbers ⋮ Queries with arithmetical constraints ⋮ On the coincidence of complexity classes BPC and \(\text{TC}^0 \) ⋮ The complexity of searching implicit graphs ⋮ Unnamed Item ⋮ The isomorphism conjecture for constant depth reductions ⋮ Parallelizing time with polynomial circuits ⋮ The binary network flow problem is logspace complete for P ⋮ Polynomial size \(\Omega\)-branching programs and their computational power ⋮ On the computational efficiency of symmetric neural networks ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Linear-size constant-depth polylog-threshold circuits ⋮ Some notes on threshold circuits, and multiplication in depth 4 ⋮ The complexity of the parity function in unbounded fan-in, unbounded depth circuits ⋮ An arithmetic model of computation equivalent to threshold circuits ⋮ Learning in parallel ⋮ The expressiveness of a family of finite set languages ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ Computing functions with parallel queries to NP ⋮ The graph of multiplication is equivalent to counting ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Regular languages in \(NC\) ⋮ The complexity of searching succinctly represented graphs ⋮ Multiplication, division, and shift instructions in parallel random access machines ⋮ The complexity of computing symmetric functions using threshold circuits ⋮ Circuit depth relative to a random oracle ⋮ Methods for proving completeness via logical reductions ⋮ On the power of small-depth threshold circuits ⋮ Computing with discrete multi-valued neurons ⋮ Root finding with threshold circuits ⋮ Correctness of linear logic proof structures is NL-complete ⋮ Extensions to Barrington's M-program model ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ A lower bound for primality ⋮ The complexity of propositional implication ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ Symmetries and the complexity of pure Nash equilibrium ⋮ The exact complexity of projective image matching ⋮ In-place algorithms for computing a largest clique in geometric intersection graphs ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ The Computational Complexity of Choice Sets ⋮ Threshold circuits of small majority-depth ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ Does Looking Inside a Circuit Help ⋮ A frame for general divide-and-conquer recurrences ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\) ⋮ New techniques for zero-knowledge: leveraging inefficient provers to reduce assumptions, interaction, and trust ⋮ Bounded-depth, polynomial-size circuits for symmetric functions ⋮ Non-uniform automata over groups ⋮ Two-coloring linked lists is NC\(^ 1\)-complete for logarithmic space ⋮ The parallel complexity of two problems on concurrency ⋮ The complexity of computing maximal word functions

This page was built for publication: Constant Depth Reducibility