Definability by constant-depth polynomial-size circuits

DOI10.1016/S0019-9958(86)80006-7MaRDI QIDQ3767263zbMATH OpenOpenAlexFDO

Authors Larry Denenberg, S. Shelah, Yuri Gurevich

Publication date 1986

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0019-9958(86)80006-7

zbMATH Keywords

circuit definabilityfirst-order definabilitymonadic predicate symbolssequences of Boolean circuits

Mathematics Subject Classification ID

Interpolation, preservation, definability (03C40) Properties of classes of models (03C52) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25) Switching theory, applications of Boolean algebras to circuits and networks (94C11)

Recommendations

• scientific article; zbMATH DE number 1086678
• scientific article; zbMATH DE number 988809
• Circuit complexity and the expressive power of generalized first-order formulas
• First-order definability on finite structures
• scientific article; zbMATH DE number 1954387
• Decidability and undecidability of theories with a predicate for the primes
• scientific article; zbMATH DE number 5510997
• scientific article; zbMATH DE number 3928955
• Some computational aspects of circumscription

Cited in

(28)

• Generalized lower bounds derived from Hastad's main lemma
• Linear-size constant-depth polylog-threshold circuits
• The invariant problem for binary string structures and the parallel complexity theory of queries
• Threshold circuits of small majority-depth
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology
• Properties of symmetric Boolean functions
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• A polynomial excluded-minor approximation of treedepth
• A logical characterization of constant-depth circuits over the reals
• On symmetric circuits and fixed-point logics
• Ehrenfeucht-Fraïssé Games on Random Structures
• Fixed-Point Definability and Polynomial Time
• A logic for constant-depth circuits
• scientific article; zbMATH DE number 1342210 (Why is no real title available?)
• scientific article; zbMATH DE number 1072417 (Why is no real title available?)
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Symmetric circuits for rank logic
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Symmetric arithmetic circuits
• Symmetric arithmetic circuits
• Limits of symmetric computation (invited talk)
• Regular representations of uniform TC^0
• Aggregate operators in constraint query languages
• Equi-rank homomorphism preservation theorem on finite structures
• Violating constant degree hypothesis requires breaking symmetry

This page was built for publication: Definability by constant-depth polynomial-size circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3767263)