Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Haak, Anselm"'
We present a randomized algorithm for solving low-degree polynomial equation systems over finite fields faster than exhaustive search. In order to do so, we follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA 2017), Bj\"orklun
Externí odkaz:
http://arxiv.org/abs/2410.20162
We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for hard enumeration analogous to the polynomial hierarchy, which was rece
Externí odkaz:
http://arxiv.org/abs/2006.06953
In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators paraW and
Externí odkaz:
http://arxiv.org/abs/1904.12156
We study descriptive complexity of counting complexity classes in the range from #P to #$\cdot$NP. A corollary of Fagin's characterization of NP by existential second-order logic is that #P can be logically described as the class of functions countin
Externí odkaz:
http://arxiv.org/abs/1902.00246
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 $\textrm{NC}^1$, $\textrm{SAC}^1$ and $\textrm{AC}^1$ as well as thei
Externí odkaz:
http://arxiv.org/abs/1710.01934
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
Externí odkaz:
http://arxiv.org/abs/1604.06617
Autor:
Haak, Anselm, Vollmer, Heribert
We study the class $\textrm{AC}^0$ of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far.
Externí odkaz:
http://arxiv.org/abs/1603.09531
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Haak, Anselm
In this thesis, we study the descriptive complexity of counting classes based on Boolean circuits. In descriptive complexity, the complexity of problems is studied in terms of logics required to describe them. The focus of research in this area is on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b43fb90823bcc2010f9db192b29e70c6