Zobrazeno 1 - 10
of 1 183
pro vyhledávání: '"Descriptive complexity theory"'
Autor:
Alberto Marcone, Manlio Valenti
Publikováno v:
Fundamenta Mathematicae. 257:69-93
In this paper we study the notion of Salem set from the point of view of descriptive set theory. We first work in the hyperspace $\mathbf{K}([0,1])$ of compact subsets of $[0,1]$ and show that the closed Salem sets form a $\boldsymbol{\Pi}^0_3$-compl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e4df4d7745bee80bb995e23fe38702e2
https://doi.org/10.4064/fm997-7-2021
https://doi.org/10.4064/fm997-7-2021
Autor:
Frank Stephan, André Nies
Publikováno v:
Theoretical Computer Science. 900:1-19
We study algorithmic randomness properties for probability measures on Cantor space. We say that a measure μ on the space of infinite bit sequences is Martin-Lof absolutely continuous if the non-Martin-Lof random bit sequences form a null set with r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7ac64b56a35abd08dd6ce3ec627f260b
https://doi.org/10.1016/j.tcs.2021.11.003
https://doi.org/10.1016/j.tcs.2021.11.003
Autor:
Hella, Lauri
A generalized quantifier Q_𝒦 is called a CSP-quantifier if its defining class 𝒦 consists of all structures that can be homomorphically mapped to a fixed finite template structure. For all positive integers n ≥ 2 and k, we define a pebble game
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8f02fda176c5c9f3269252d4fc005df3
https://trepo.tuni.fi/handle/10024/147466
https://trepo.tuni.fi/handle/10024/147466
Autor:
Jonni Virtema, Jan Van den Bussche, José María Turull Torres, Flavio Ferrarotti, Senén González
Publikováno v:
Journal of Computer and System Sciences. 119:145-163
We propose logical characterizations of problems solvable in deterministic polylogarithmic time (PolylogTime) and polylogarithmic space (PolylogSpace). We introduce a novel two-sorted logic that separates the elements of the input domain from the bit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::40bba421040010a39d90507b36e892c3
https://doi.org/10.1016/j.jcss.2021.02.003
https://doi.org/10.1016/j.jcss.2021.02.003
Autor:
Tejas Bhojraj
Publikováno v:
Theoretical Computer Science. 875:65-80
We introduce quantum-K ($QK$), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::45b6d918adaace4ec6f5b8b84ac2033f
https://doi.org/10.1016/j.tcs.2021.05.017
https://doi.org/10.1016/j.tcs.2021.05.017
Conference
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.
Conference
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.
Publikováno v:
Journal of Computer and System Sciences. 113:42-59
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful approach to the Graph Isomorphism problem. 2-WL corresponds to the original algorithm suggested by Weisfeiler and Leman over 50 years ago. 1-WL is the classical color refinement ro
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::acecb4c2c146fb1f2358445db01cc37f
https://doi.org/10.1016/j.jcss.2020.04.003
https://doi.org/10.1016/j.jcss.2020.04.003
Autor:
Ghadeer Ghawadrah
Publikováno v:
Fundamenta Mathematicae. 249:303-309
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::37aff3fe6228a42fa46ef9397bfd0ad3
https://doi.org/10.4064/fm758-8-2019
https://doi.org/10.4064/fm758-8-2019
Publikováno v:
LICS
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
We initiate a systematic study of the computational complexity of the Constraint Satisfaction Problem (CSP) over finite structures that may contain both relations and operations. We show the close connection between this problem and a natural algebra
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bdaf7b606096d7ba1f742179a6665d40
https://doi.org/10.1109/lics52264.2021.9470670
https://doi.org/10.1109/lics52264.2021.9470670