Zobrazeno 1 - 10
of 189
pro vyhledávání: '"Theory of computation ��� Problems, reductions and completeness"'
A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::811370386e56ef5b730787d6b31caafb
Publikováno v:
Journal of Computer and System Sciences. 132:1-15
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f592bb7401286d5cc6d9f8f2bf326a1
https://doi.org/10.1016/j.jcss.2022.09.002
https://doi.org/10.1016/j.jcss.2022.09.002
Publikováno v:
Theoretical Computer Science. 936:13-32
In a graph G = (V,E) with an edge coloring 𝓁:E → C and two distinguished vertices s and t, a colored (s,t)-cut is a set C̃ ⊆ C such that deleting all edges with some color c ∈ C̃ from G disconnects s and t. Motivated by applications in the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7fc5eddb6cac48a4f6ed047154cea6f8
https://doi.org/10.1016/j.tcs.2022.09.013
https://doi.org/10.1016/j.tcs.2022.09.013
Autor:
Nina, Maria Paula Parga, An, Haozhe, Gurumukhani, Mohit, Impagliazzo, Russell, Jaber, Michael, Künnemann, Marvin, Parga Nina, Maria Paula
Publikováno v:
16th International Symposium on Parameterized and Exact Computation
Leibniz International Proceedings in Informatics
Leibniz International Proceedings in Informatics (LIPIcs), 214
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Leibniz International Proceedings in Informatics
Leibniz International Proceedings in Informatics (LIPIcs), 214
16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
We define a class of problems whose input is an n-sized set of d-dimensional vectors, and where the problem is first-order definable using comparisons between coordinates. This class captures a wide variety of tasks, such as complex types of orthogon
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::543de6cafdbc439cb263cc95cb938884
https://doi.org/10.1007/s00453-022-01014-x
https://doi.org/10.1007/s00453-022-01014-x
Autor:
Huszár, Kristóf, Spreer, Jonathan
Publikováno v:
Leibniz International Proceedings in Informatics (LIPIcs)
39th International Symposium on Computational Geometry (SoCG 2023)
39th International Symposium on Computational Geometry (SoCG 2023), Jun 2023, Dallas, United States. pp.42:1--42:18, ⟨10.4230/LIPIcs.SoCG.2023.42⟩
Kristóf Huszár
39th International Symposium on Computational Geometry (SoCG 2023)
39th International Symposium on Computational Geometry (SoCG 2023), Jun 2023, Dallas, United States. pp.42:1--42:18, ⟨10.4230/LIPIcs.SoCG.2023.42⟩
Kristóf Huszár
Motivated by the algorithmic study of 3-dimensional manifolds, we explore the structural relationship between the JSJ decomposition of a given 3-manifold and its triangulations. Building on work of Bachman, Derby-Talbot and Sedgwick, we show that a "
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4ede02e45b3f15e058c198cd457ee474
https://hal.science/hal-04055617
https://hal.science/hal-04055617
Autor:
Lohrey, Markus
Publikováno v:
Theory of Computing Systems.
It is shown that the subgroup membership problem for a virtually free group can be decided in polynomial time where all group elements are represented by so-called power words, i.e., words of the form p_1^{z_1} p_2^{z_2} ⋯ p_k^{z_k}. Here the p_i a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4def700f17f24883492e6ab08baadeac
https://doi.org/10.1007/s00224-023-10122-2
https://doi.org/10.1007/s00224-023-10122-2
Autor:
Hader, Daniel, Patitz, Matthew J.
Algorithmic self-assembly occurs when components in a disorganized collection autonomously combine to form structures and, by their design and the dynamics of the system, are forced to intrinsically follow the execution of algorithms. Motivated by ap
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0180f5c1920f091ec5e24e8a3b81c1fc
http://arxiv.org/abs/2305.01877
http://arxiv.org/abs/2305.01877
Autor:
Bodirsky, Manuel, Knäuer, Simon
We show that the problem of deciding for a given finite relation algebra A whether the network satisfaction problem for A can be solved by the k-consistency procedure, for some natural number k, is undecidable. For the important class of finite relat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::22e64d37a071d5c9fa5510bbb5a822e3
http://arxiv.org/abs/2304.12871
http://arxiv.org/abs/2304.12871
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be sat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b69227b20d04840d835639dc87968d5b
https://theoretics.episciences.org/8967
https://theoretics.episciences.org/8967
Autor:
Manurangsi, Pasin
We study the complexity of computing (and approximating) VC Dimension and Littlestone’s Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::db179d9099bdd931fb4daf76188dff6f