Source author record

Pedro Montealegre

Pedro Montealegre appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Discrete Mathematics Computation and Language Computational Complexity physics.soc-ph

Catalog footprint

What is connected

9works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Computing Power of Hybrid Models in Synchronous Networks

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector $x\in\{0,1\}^n$ together with an index $i\in[n]$, Bob is given a binary vector $y\in\{0,1\}^n$ together with an index $j\in[n]$, and, after a single round of 2-way communication, Alice must output a boolean $\textrm{out}_A$, and Bob must output a boolean $\textrm{out}_B$, such that $\mbox{out}_A\land\mbox{out}_B = x_j\oplus y_i$. We show that the communication complexity of XOR-Index is $Ω(n)$ bits.

preprint2021arXiv

On the impact of treewidth in the computational complexity of freezing dynamics

An automata network is a network of entities, each holding a state from a finite set and evolving according to a local update rule which depends only on its neighbors in the network's graph. It is freezing if there is an order on states such that the state evolution of any node is non-decreasing in any orbit. They are commonly used to model epidemic propagation, diffusion phenomena like bootstrap percolation or cristal growth. In this paper we establish how treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general model checking formalism that captures many classical decision problems: prediction, nilpotency, predecessor, asynchronous reachability. Then, on one hand, we present an efficient parallel algorithm that solves the general model checking problem in NC for any graph with bounded degree and bounded treewidth. On the other hand, we show that these problems are hard in their respective classes when restricted to families of graph with polynomially growing treewidth. For prediction, predecessor and asynchronous reachability, we establish the hardness result with a fixed set-defiend update rule that is universally hard on any input graph of such families.

preprint2020arXiv

Compact Distributed Certification of Planar Graphs

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a \dMAM\/ protocol), and uses small certificates, on $O(\log n)$ bits in $n$-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a \emph{proof-labeling scheme} for planarity, still using certificates on just $O(\log n)$ bits. We also show that there are no proof-labeling schemes -- in fact, even no \emph{locally checkable proofs} -- for planarity using certificates on $o(\log n)$ bits.

preprint2020arXiv

Local Certification of Graphs with Bounded Genus

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $\mathsf{dMAM}(O(\log n))$ protocol for this class, that is, a distributed interactive protocol with $O(\log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $\mathsf{dMAM}(O(\log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(\log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.

preprint2019arXiv

Competing Activists--Political Polarization

Recent empirical findings suggest that societies have become more polarized in various countries. That is, the median voter of today represents a smaller fraction of society compared to two decades ago and yet, the mechanisms underlying this phenomenon are not fully understood. Since interactions between influential actors ("activists") and voters play a major role in opinion formation, e.g. through social media, we develop a macroscopic opinion model in which competing activists spread their political ideas in specific groups of society. These ideas spread further to other groups in declining strength. While unilateral spreading shifts the opinion distribution, competition of activists leads to additional phenomena: Small heterogeneities among competing activists cause them to target different groups in society, which amplifies polarization. For moderate heterogeneities, we obtain target cycles and further amplification of polarization. In such cycles, the stronger activist differentiates himself from the weaker one, while the latter aims to imitate the stronger activist.

preprint2016arXiv

Automata networks for multi-party communication in the Naming Game

The Naming Game has been studied to explore the role of self-organization in the development and negotiation of linguistic conventions. In this paper, we define an automata networks approach to the Naming Game. Two problems are faced: (1) the definition of an automata networks for multi-party communicative interactions; and (2) the proof of convergence for three different orders in which the individuals are updated (updating schemes). Finally, computer simulations are explored in two-dimensional lattices with the purpose to recover the main features of the Naming Game and to describe the dynamics under different updating schemes.

preprint2016arXiv

On Distance-$d$ Independent Set and other problems in graphs with few minimal separators

Fomin and Villanger (STACS 2010) proved that Maximum Independent Set, Feedback Vertex Set, and more generally the problem of finding a maximum induced subgraph of treewith at most a constant $t$, can be solved in polynomial time on graph classes with polynomially many minimal separators. We extend these results in two directions. Let $\Gpoly$ be the class of graphs with at most $\poly(n)$ minimal separators, for some polynomial $\poly$. We show that the odd powers of a graph $G$ have at most as many minimal separators as $G$. Consequently, \textsc{Distance-$d$ Independent Set}, which consists in finding maximum set of vertices at pairwise distance at least $d$, is polynomial on $\Gpoly$, for any even $d$. The problem is NP-hard on chordal graphs for any odd $d \geq 3$. We also provide polynomial algorithms for Connected Vertex Cover and Connected Feedback Vertex Set on subclasses of $\Gpoly$ including chordal and circular-arc graphs, and we discuss variants of independent domination problems.

preprint2015arXiv

PSPACE-Completeness of Majority Automata Networks

We study the dynamics of majority automata networks when the vertices are updated according to a block sequential updating scheme. In particular, we show that the complexity of the problem of predicting an eventual state change in some vertex, given an initial configuration, is PSPACE-complete.

preprint2014arXiv

Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover ($\operatorname{vc}$) and modular width ($\operatorname{mw}$). We prove that for any graph, the number of minimal separators is $\mathcal{O}^*(3^{\operatorname{vc}})$ and $\mathcal{O}^*(1.6181^{\operatorname{mw}})$, and the number of potential maximal cliques is $\mathcal{O}^*(4^{\operatorname{vc}})$ and $\mathcal{O}^*(1.7347^{\operatorname{mw}})$, and these objects can be listed within the same running times. (The $\mathcal{O}^*$ notation suppresses polynomial factors in the size of the input.) Combined with known results, we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time $\mathcal{O}^*(4^{\operatorname{vc}})$ or $\mathcal{O}^*(1.7347^{\operatorname{mw}})$.