4 citations · 8 across the 6 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2017
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
Arnaud Durand, Anselm Haak, Heribert Vollmer
In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes…
cs.CC2016★ 4 cited
Descriptive Complexity of Functions
Arnaud Durand, Anselm Haak, Juha Kontinen +1
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free fu…
cs.CC2016★ 4 cited
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
Anselm Haak, Heribert Vollmer
We study the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theor…