@article{DURAND202140,
    Abstract = {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 function variables in first-order formulae. We completely determine the inclusion structure and show that \#P and \#AC0 appear as classes of this hierarchy. In this way, we unconditionally place \#AC0 properly in a strict hierarchy of arithmetic classes within \#P. Furthermore, we show that some of our classes admit efficient approximation in the sense of FPRAS. We compare our classes with a hierarchy within \#P defined in a model-theoretic way by Saluja et al. and argue that our approach is better suited to study arithmetic circuit classes such as \#AC0 which can be descriptively characterized as a class in our framework.},
    Author = {Durand, Arnaud and Haak, Anselm and Kontinen, Juha and Vollmer, Heribert},
    File = {Descriptive complexity of \#P functions- A new perspective - j.jcss.2020.04.002.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {Finite model theory, Arithmetic circuits, Counting classes, Skolem function},
    Pages = {40-54},
    Title = {Descriptive complexity of \#P functions: A new perspective},
    URL = {https://www.sciencedirect.com/science/article/pii/S0022000020300374},
    Volume = {116},
    Year = {2021},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000020300374},
    bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2020.04.002},
    date-added = {2022-07-01 12:43:06 +0200},
    date-modified = {2022-07-01 12:43:06 +0200},
    doi = {10.1016/j.jcss.2020.04.002}
}

@article{DURAND202140, Abstract = {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 function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC0 appear as classes of this hierarchy. In this way, we unconditionally place #AC0 properly in a strict hierarchy of arithmetic classes within #P. Furthermore, we show that some of our classes admit efficient approximation in the sense of FPRAS. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. and argue that our approach is better suited to study arithmetic circuit classes such as #AC0 which can be descriptively characterized as a class in our framework.}, Author = {Durand, Arnaud and Haak, Anselm and Kontinen, Juha and Vollmer, Heribert}, File = {Descriptive complexity of #P functions- A new perspective - j.jcss.2020.04.002.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {Finite model theory, Arithmetic circuits, Counting classes, Skolem function}, Pages = {40-54}, Title = {Descriptive complexity of #P functions: A new perspective}, URL = {https://www.sciencedirect.com/science/article/pii/S0022000020300374}, Volume = {116}, Year = {2021}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0022000020300374}, bdsk-url-2 = {https://doi.org/10.1016/j.jcss.2020.04.002}, date-added = {2022-07-01 12:43:06 +0200}, date-modified = {2022-07-01 12:43:06 +0200}, doi = {10.1016/j.jcss.2020.04.002} }