Definability by constant-depth polynomial-size circuits
From MaRDI portal
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
- The logic of explicitly presentation-invariant circuits
- scientific article; zbMATH DE number 988809
- Circuit complexity and the expressive power of generalized first-order formulas
- First-order definability on finite structures
- The decidability of the first-order theory of the Knuth-Bendix order in the case of unary signatures
- 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
(29)- 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
- Invariant definability and P/poly
- 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
- Symmetric quantum computation
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)