23 citations · 47 across the 14 of their papers we have counts for
3 papers · 1 filter
Enumeration Classes Defined by Circuits
Nadia Creignou, Arnaud Durand, Heribert Vollmer
We refine the complexity landscape for enumeration problems by introducing very low classes defined by using Boolean circuits as enumerators. We locate well-known enumeration probl…
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…
The arithmetic complexity of tensor contractions
Florent Capelli, Arnaud Durand, Stefan Mengel
We investigate the algebraic complexity of tensor calulus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture V…