A logical characterization of constant-depth circuits over the reals

DOI10.1007/978-3-030-88853-4_2MaRDI QIDQ2148775zbMATH OpenOpenAlexFDO

Authors Timon Barlag, Heribert Vollmer

Publication date 24 June 2022

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

zbMATH Keywords

computation over the realsconstant-depth circuit familiesdescriptive complexity

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• A logic for constant-depth circuits
• Algorithmic meta theorems for circuit classes of constant and logarithmic depth
• Depth of Boolean functions realized by circuits over an arbitrary infinite basis
• Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth
• Definability by constant-depth polynomial-size circuits
• Publication:4893147
• On the depth of \(k\)-valued logic functions over arbitrary bases
• Logics which capture complexity classes over the reals

Cites work

• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• An algebra and a logic for \(NC^ 1\)
• Expressibility and Parallel Complexity
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1263207 (Why is no real title available?)
• Languages that Capture Complexity Classes
• Logics which capture complexity classes over the reals
• Model-theoretic characterization of Boolean and arithmetic circuit classes of small depth
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy

Cited in

(3)

• scientific article; zbMATH DE number 1086678 (Why is no real title available?)
• Logical characterizations of algebraic circuit classes over integral domains
• A logical characterization of constant-depth circuits over the reals

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

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