Goles, E., Montealegre, P., Perrot, K., & Theyssier, G. (2018). On the complexity of two-dimensional signed majority cellular automata. J. Comput. Syst. Sci., 91, 1–32.
Abstract: We study the complexity of signed majority cellular automata on the planar grid. We show that, depending on their symmetry and uniformity, they can simulate different types of logical circuitry under different modes. We use this to establish new bounds on their overall complexity, concretely: the uniform asymmetric and the non-uniform symmetric rules are Turing universal and have a P-complete prediction problem; the non-uniform asymmetric rule is intrinsically universal; no symmetric rule can be intrinsically universal. We also show that the uniform asymmetric rules exhibit cycles of super-polynomial length, whereas symmetric ones are known to have bounded cycle length. (C) 2017 Elsevier Inc. All rights reserved.
|
Golovach, P. A., Heggernes, P., Lima, P. T., & Montealegre, P. (2020). Finding connected secluded subgraphs. J. Comput. Syst. Sci., 113, 101–124.
Abstract: Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the SECLUDED Pi-SUBGRAPH problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k + t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the CONNECTED SECLUDED Pi-SUBGRAPH problem is FPT when parameterized by just t for many important graph properties Pi. (C) 2020 Elsevier Inc. All rights reserved.
|
Gutierrez, C., Hurtado, C. A., Mendelzon, A. O., & Perez, J. (2011). Foundations of Semantic Web databases. J. Comput. Syst. Sci., 77(3), 520–541.
Abstract: The Semantic Web is based on the idea of a common and minimal language to enable large quantities of existing data to be analyzed and processed. This triggers the need to develop the database foundations of this basic language, which is the Resource Description Framework (RDF). This paper addresses this challenge by: 1) developing an abstract model and query language suitable to formalize and prove properties about the RDF data and query language; 2) studying the RDF data model, minimal and maximal representations, as well as normal forms; 3) studying systematically the complexity of entailment in the model, and proving complexity bounds for the main problems; 4) studying the notions of query answering and containment arising in the RDF data model; and 5) proving complexity bounds for query answering and query containment. (C) 2010 Elsevier Inc. All rights reserved.
|
Montealegre, P., Perez-Salazar, S., Rapaport, I., & Todinca, I. (2020). Graph reconstruction in the congested clique. J. Comput. Syst. Sci., 113, 1–17.
Abstract: In this paper we study the reconstruction problem in the congested clique model. Given a class of graphs g, the problem is defined as follows: if G is not an element of g, then every node must reject; if G is an element of g, then every node must end up knowing all the edges of G. The cost of an algorithm is the total number of bits received by any node through one link. It is not difficult to see that the cost of any algorithm that solves this problem is Omega(log vertical bar g(n)vertical bar/n), where g(n) is the subclass of all n-node labeled graphs in g. We prove that the lower bound is tight and that it is possible to achieve it with only 2 rounds. (C) 2020 Elsevier Inc. All rights reserved.
|