A logical characterization of constant-depth circuits over the reals

DOI10.1007/978-3-030-88853-4_2OpenAlexW3208119394MaRDI QIDQ2148775

Timon Barlag, Heribert Vollmer

Publication date: 24 June 2022

Full work available at URL: https://arxiv.org/abs/2005.04916

zbMATH Keywords

descriptive complexitycomputation over the realsconstant-depth circuit families

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• Unnamed Item
• Unnamed Item
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• A model-theoretic characterization of constant-depth arithmetic circuits
• An algebra and a logic for \(NC^ 1\)
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Languages that Capture Complexity Classes
• Expressibility and Parallel Complexity
• Logics which capture complexity classes over the reals
• Model-Theoretic Characterization of Boolean and Arithmetic Circuit Classes of Small Depth

This page was built for publication: A logical characterization of constant-depth circuits over the reals