PageRank Optimization by Edge Selection (2009)
Csáji, Balázs Csanád, Jungers, Raphaël M., Blondel, Vincent D.
The importance of a node in a directed graph can be measured by its PageRank. The PageRank of a node is used in a number of application contexts - including web-page ranking - and can be interpreted...
Continuous-time average-preserving opinion dynamics with opinion-dependent communications (2009)
Blondel, Vincent D., Hendrickx, Julien M., Tsitsiklis, John N.
We study a simple continuous-time multi-agent system related to Krause's model of opinion dynamics: each agent holds a real value, and this value is continuously attracted by every other value...
Vincent D. Blondel, Julien M. Hendrickx, Raphaël M. Jungers
We prove that the one-player game Solitaire Clobber 2 is equivalent to an optimization problem on a set of words defined by seven classes of forbidden patterns when played on the line or on the...
Julien M. Hendrickx, Jean-charles Delvenne, Vincent D. Blondel
graphs for the analysis of rigidity and persistence in
Library of Congress Cataloging-in-Publication Data (2008)
Vincent D. Blondel, Alexandre Megretski, Edited Vincent, D. Blondel, Poul Anderson
Unsolved problems in mathematical systems and control theory
Dynamics of latent voters (2008)
Lambiotte, Renaud, Saramaki, Jari, Blondel, Vincent D.
We study the effect of latency on binary-choice opinion formation models. Latency is introduced into the models as an additional dynamic rule: after a voter changes its opinion, it enters a waiting...
Bell, Paul, Delvenne, Jean-Charles, Jungers, Raphael, Blondel, Vincent D.
We study decidability and complexity questions related to a continuous analogue of the Skolem-Pisot problem concerning the zeros and nonnegativity of a linear recurrent sequence. In particular, we...
On Krause's multi-agent consensus model with state-dependent connectivity (Extended version) (2008)
Blondel, Vincent D., Hendrickx, Julien M., Tsitsiklis, John N.
We study a model of opinion dynamics introduced by Krause: each agent has an opinion represented by a real number, and updates its opinion by averaging all agent opinions that differ from its own by...
Intelligent Systems at the Service of Man... (2008)
Ivo Petras, Igor Podlubny, Lubomír Dorcák, Blas M. Vinagre, J. I. Suárez, B. M. Vinagre, ...
Lanusse, and Jocelyn Sabatier, “Optimal Tunings for Fractional PI λ D µ Controllers”. In:
Prof Eva Tardos, Vlady Ravelomanana, Herve Daudé, Ivan Rapaport, Karol Suchan, Ioan Todinca, ...
15:00-15:20 Computing the growth of the number of overlap-free words with spectra
the complexity of computing the capacity of codes that avoid forbidden difference patterns
Fast unfolding of communities in large networks (2008)
Blondel, Vincent D., Guillaume, Jean-Loup, Lambiotte, Renaud, Lefebvre, Etienne
We propose a simple method to extract the community structure of large networks. Our method is a heuristic method that is based on modularity optimization. It is shown to outperform all other known...
Geographical dispersal of mobile communication networks (2008)
Lambiotte, Renaud, Blondel, Vincent D., De Kerchove, Cristobald, Huens, Etienne, Prieur, Christophe, Smoreda, Zbigniew, ...
In this paper, we analyze statistical properties of a communication network constructed from the records of a mobile phone company. The network consists of 2.5 million customers that have placed 810...
Theory of Computing Systems (2008)
Vincent D. Blondel, Vincent Canterini
Abstract. We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one...
Bilinear Functions and Trees over the (2008)
Max Semiring, Sabrina Mantaci, Vincent D. Blondel, Jean Mairesse
Abstract. We consider the iterates of bilinear functions over the semiring (max, +). Equivalently, our object of study can be viewed as recognizable tree series over the semiring (max, +). In this...
Distortion theorems for rational functions without poles or (2008)
Vincent D. Blondel, Rudolf Rupp
zeros in simply connected domains
Julien M. Hendrickx, Jean-charles Delvenne, Vincent D. Blondel
graphs for the analysis of rigidity and persistence in
John N. Tsitsiklist, Vincent D. Blondel
Abstraet. We analyze the computability and the complexity of various defini-tions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices...
Vincent D. Blondel, Anahí Gajardo, Maureen Heymans, Pierre Senellart, Paul Van Dooren
Abstract. We introduce a concept of similarity between vertices of directed graphs. Let GA and GB be two directed graphs with, respectively, nA and nB vertices. We define an nB × nA similarity...
Vol. 24, No. 4, pp. 963–970 AN ELEMENTARY COUNTEREXAMPLE TO THE FINITENESS CONJECTURE ∗ (2008)
Vincent D. Blondel, Jacques Theys, A. Vladimirov
Abstract. We prove that there exist (infinitely many) values of the real parameters a and b for which the matrices
John N. Tsitsiklis, Vincent D. Blondel
The last sentence of Corollary 2 in [TB] states that it is NP-hard to decide whether all products of two given real matrices are stable and "that this is true even if the matrices have {0,...
the complexity of computing the capacity of codes that avoid forbidden difference patterns
Descent methods for Nonnegative Matrix Factorization (2008)
Ho, Ngoc-Diep, Van Dooren, Paul, Blondel, Vincent D.
In this paper, we present several descent methods that can be applied to nonnegative matrix factorization and we analyze a recently developed fast block coordinate method. We also give a comparison...
Fast unfolding of communities in large networks (2008)
Vincent D Blondel, Jean-loup Guillaume, Renaud Lambiotte, Etienne Lefebvre
Fast unfolding of communities in large networks
Distortion Theorems for Rational Functions Without Poles Or Zeros in Simply Connected Domains (2007)
Vincent D. Blondel, Rudolf Rupp
We prove distortion theorems for rational functions without poles or zeros in simply connected domains. The distance between the values u(z1 ) and u(z2 ) assumed by such a rational function is...
Approximations of the rate of growth of switched (2007)
Vincent D. Blondel, Yurii Nesterov, Jacques Theys
linear systems
Vincent D. Blondel, Jacques Theys, Alexander A. Vladimirov
systems that are periodically stable may be unstable
URL: www.control.auc.dk/˜jakob/ Stabilization Result (2007)
Jakob Stoustrup, Senior Member, Vincent D. Blondel
1 This paper discusses the problem of designing fault tolerant compensators that stabilize a given system both in the nominal situation, as well as in the situation where one of the sensors or one of...
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
stability of saturated linear dynamical
The stability of saturated linear dynamical systems (2007)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
is undecidable
Pierre P. Senellart, Vincent D. Blondel
We deal with the issue of automatic discovery of similar words (synonyms and near-synonyms) from dierent kind of sources: from large corpora of documents, from the Web, and from monolingual...
Vincent D. Blondel, Natacha Portier
presence of a zero in an integer linear recurrent
Open Problems On, Vincent D. Blondel, Alexander Megretski, Roger Brockett, Jean-michel Coron, Miroslav Krstic, ...
this paper we consider the well-known Schur problem the solution of which satisfy in addition the extremal condition (z)w(z) min ; jzj < 1 (58.1) where w(z) and min are mxm matrices and min > 0...
Overlap-free words and spectra of matrices (2007)
Jungers, Raphael M., Protasov, Vladimir Y., Blondel, Vincent D.
Overlap-free words are words over the binary alphabet $A=\{a, b\}$ that do not contain factors of the form $xvxvx$, where $x \in A$ and $v \in A^*$. We analyze the asymptotic growth of the number...
Distance distribution in random graphs and application to networks exploration (2007)
Blondel, Vincent D., Guillaume, Jean-Loup, Hendrickx, Julien M., Jungers, Raphael M.
We consider the problem of determining the proportion of edges that are discovered in an Erdos-Renyi graph when one constructs all shortest paths from a given source node to all other nodes. This...
Linear time algorithms for Clobber (2007)
Blondel, Vincent D., Hendrickx, Julien M., Jungers, Raphael M.
We prove that the single-player game clobber is solvable in linear time when played on a line or on a cycle. For this purpose, we show that this game is equivalent to an optimization problem on a set...
Jungers, Raphael M., Blondel, Vincent D.
An edge-colored directed graph is \emph{observable} if an agent that moves along its edges is able to determine his position in the graph after a sufficiently long observation of the edge colors....
On the Finiteness Property for Rational Matrices (2007)
Jungers, Raphael M., Blondel, Vincent D.
We analyze the periodicity of optimal long products of matrices. A set of matrices is said to have the finiteness property if the maximal rate of growth of long products of matrices taken from the...
Abstract Available online at www.sciencedirect.com (2007)
Raphaël M. Jungers, Vincent D. Blondel
www.elsevier.com/locate/laa On the finiteness property for rational matrices �
Hendrickx, Julien M., Fidan, Baris, Yu, Changbin, Anderson, Brian D. O., Blondel, Vincent D.
In this paper, we study the construction and transformation of two-dimensional persistent graphs. Persistence is a generalization to directed graphs of the undirected notion of rigidity. In the...
Efficient algorithms for deciding the type of growth of products of integer matrices (2006)
Jungers, Raphaël, Protasov, Vladimir, Blondel, Vincent D.
For a given finite set $\Sigma$ of matrices with nonnegative integer entries we study the growth of $$ \max_t(\Sigma) = \max\{\|A_{1}... A_{t}\|: A_i \in \Sigma\}.$$ We show how to determine in...
On the complexity of computing the capacity of codes that avoid forbidden difference patterns (2006)
Blondel, Vincent D., Jungers, Raphael, Protasov, Vladimir
We consider questions related to the computation of the capacity of codes that avoid forbidden difference patterns. The maximal number of $n$-bit sequences whose pairwise differences do not contain...
Efficient algorithms for deciding the type of growth of products of integer matrices (2006)
Raphaël Jungers, Vladimir Protasov, Vincent D. Blondel
products of integer matrices
Computational universality in symbolic dynamical systems, Fundamenta Informaticae (2006)
Jean-charles Delvenne, Vincent D. Blondel
Abstract. Many different definitions of computational universality for various types of systems have flourished since Turing’s work. In this paper, we propose a general definition of universality...
Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)
Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis
Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...
Decidable and undecidable problems about quantum automata (2005)
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran
Abstract. We study the following decision problem: is the language recognized by a quantum nite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on...
Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)
Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis
Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...
Decidable and undecidable problems about quantum automata (2005)
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran, Natacha Portier
Abstract. We study the following decision problem: is the language recognized by a quantum finite automaton empty or nonempty? We prove that this problem is decidable or undecidable depending on...
Rigidity and persistence of three and higher dimensional formations (2005)
Julien M. Hendrickx, Barıs Fidan, Changbin Yu, Vincent D. Blondel
Abstract. In this paper, we generalize the notion of persistence, which has been originally introduced for two-dimensional formations, to ℜ d for d ≥ 3, seeking to provide a theoretical framework...
Tsitsiklis. Convergence in multiagent coordination, consensus, and flocking (2005)
Vincent D. Blondel, Julien M. Hendrickx, Alex Olshevsky, John N. Tsitsiklis
Abstract — We discuss an old distributed algorithm for reaching consensus that has received a fair amount of recent attention. In this algorithm, a number of agents exchange their values...
Directed graphs for the analysis of rigidity and persistence in autonomous agent systems (2005)
Julien M. Hendrickx, Jean-charles Delvenne, Vincent D. Blondel
autonomous agent systems
Van Dooren, Vincent D. Blondel, Vincent D. Blondel, Paul Van Dooren
Abstract. We introduce a concept of similarity between vertices of directed graphs. Let GA and GB be two directed graphs with respectively nA and nB vertices. We define a nA nB similarity matrix S...
Computationally Efficient Approximations of the Joint Spectral Radius (2004)
Vincent D. Blondel, Yurii Nesterov
The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate that can be obtained by forming long products of matrices taken from the set. This quantity appears...
Fault-Tolerant Control: A Simultaneous Stabilization Result (2004)
J. W. Helton, O. Marino, Classical Control, Using Methods, H. Kwakernaak, Robust Control, ...
This nsI discusses the problem ofdesign1I faulttoleran compen073I that stabilize a given system bothin theneI226 situation as well asin thesituation whereon of thesen184 or on of the actuators has...
Decidable and undecidable problems about quantum automata (2003)
Blondel, Vincent D., Jeandel, Emmanuel, Koiran, Pascal, Portier, Natacha
We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether...
Decidable and undecidable problems about quantum automata. (2003)
Blondel, Vincent D., Jeandel, Emmanuel, Koiran, Pascal, Portier, Natacha
(eng) We study the following decision problem: is the language recognized by a quantum finite automaton empty or non-empty? We prove that this problem is decidable or undecidable depending on whether...
An elementary counterexample to the finiteness conjecture (2003)
Vincent D. Blondel, Jacques Theys, Alexander A
The Lagarias-Wang finiteness conjecture was introduced in 1995 in connection with problems related to spectral radius computation of
Undecidable problems for probabilistic automata of fixed dimension (2003)
Vincent D. Blondel, Vincent Canterini
We prove that several problems associated to probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our...
Automatic Discovery of Similar Words (2003)
Pierre P. Senellart, Vincent D. Blondel
We deal with the issue of automatic discovery of similar words (synonyms and near-synonyms) from different kind of sources: from large corpora of documents, from the Web, and from monolingual...
Automatic Discovery of Similar Words (2003)
Pierre Senellart, Vincent D. Blondel
The purpose of this chapter is to review some methods used for automatic extraction of similar words from different kinds of sources: large corpora of documents, the World Wide Web, and monolingual...
Automatic Discovery of Similar Words (2003)
Pierre Senellart, Vincent D. Blondel
The purpose of this chapter is to review some methods used for automatic extraction of similar words from different kinds of sources: large corpora of documents, the World Wide Web, and monolingual...
Switched systems that are periodically stable may be unstable (2002)
Vincent D. Blondel, Jacques Theys, Alexander A
In this contribution, we prove the existence of switched linear systems that are periodically stable but are not absolutely stable. The switched
Automatic extraction of synonyms in a dictionary (2002)
We propose a method for automatic synonym extraction in a dictionary. Our method is based on an algorithm that computes similarity measures between vertices in graphs. This algorithm can be thought...
Automatic extraction of synonyms in a dictionary (2002)
We propose a method for automatic synonym extraction in a dictionary. Our method is based on an algorithm that computes similarity measures between vertices in graphs. This algorithm can be thought...
3 How Hard Is It to Control Switched Systems? (2002)
Magnus Egerstedt, Vincent D. Blondel
We show that the problem of deciding if there exists a control that drives a switched control system between two given states b undecidable. We firthermore in-vestigate what happens if we search for...
Switched systems that are periodically stable may be unstable (2002)
Vincent D. Blondel, Jacques Theys, Alexander A
In this contribution, we prove the existence of switched linear systems that are periodically stable but are not absolutely stable. The switched linear system associated to the finite set of real...
Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (2000)
Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis
The lower and average spectral radii measure respectively the minimal and average growth rates of long products of matrices taken from a nite set. The logarithm of the average spectral radius is...
A Survey of Computational Complexity Results in Systems and Control (2000)
Vincent D. Blondel, John N. Tsitsiklis
The purpose of this paper is twofold: (a) to provide a tutorial introduction to some key concepts from the theory of computational complexity, highlighting their relevance to systems and control...
The Boundedness of All Products of a Pair of Matrices is Undecidable (2000)
Vincent D. Blondel, John N. Tsitsiklis
We show that the boundedness of the set of all products of a given pair # of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius #(#) is not...
The Boundedness of All Products of a Pair of Matrices Is Undecidable (2000)
Vincent D. Blondel, John N. Tsitsiklis
We show that the boundedness of the set of all products of a given pair \Sigma of rational matrices is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ae(\Sigma) is...
Vincent D. Blondel, Alexander Megretski, Roger Brockett, Jean-michel Coron, Miroslav Krstic, Anders Rantzer, ...
Some of the problems appearing in this booklet will appear in a more extensive forthcoming book on open problems in systems theory. For more information about this future book, please consult the...
Complexity of stability and controllability of elementary hybrid systems (1999)
Vincent D. Blondel, John N. Tsitsiklis
e consider classes of nonlinear systems that include simple hybrid systems and prove that questions related to the stability and controllability of these systems are either undecidable or...
Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)
Vincent D. Blondel, Stephane Gaubert, John N. Tsitsiklis
The lower and average spectral radii measure the minimal and average growth rates, respectively, of long products of matrices taken from a finite set. The logarithm of the average spectral radius is...
The Stability of Saturated Linear Dynamical Systems is Undecidable (1999)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...
Boundedness of Finitely Generated Matrix Semigroups is Undecidable (1999)
Vincent D. Blondel, John N. Tsitsiklis
We show that the the boundedness of a finitely generated matrix semigroup is undecidable. Furthermore, we show that the joint (or generalized) spectral radius ae(\Sigma), associated with a finite set...
Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)
Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis
Abstract—The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral...
This work was supported by the NATO under grant CRG-961115, by (1999)
Network Alapedes, Vincent D. Blondel, John N. Tsitsiklis
� This paper was not presented at any IFAC meeting. This paper was recommended for publication in revised from by Editor M. Morari.
Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard (1999)
Vincent D. Blondel, Stéphane Gaubert, John N. Tsitsiklis
Abstract—The lower and average spectral radii measure, respectively, the minimal and average growth rates of long products of matrices taken from a finite set. The logarithm of the average spectral...
E-mail: Pascal.Koiran ens-lyon.fr (1999)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis
We prove that several global properties (global convergence, global asymptotic stability, mortality, and nilpotence) of particular classes of discrete time dynamical systems are undecidable. Such...
Deciding Stability and Mortality of Piecewise Affine Dynamical Systems (1998)
Vincent D. Blondel, Olivier Bournez, Pascal Koiran, Christos H. Papadimitriou, John N. Tsitsiklis
This paper studies problems such as: given a discrete time dynamical system of the form x(t + 1) = f(x(t)) where f : R
Vincent D. Blondel, John N. Tsitsiklis
It has become increasingly apparent this last decade that many problems in systems and control are NP-hard and, in some cases, undecidable. The inherent complexity of some of the most elementary...
Complexity of Stability and Controllability of Elementary Hybrid Systems (1997)
Vincent D. Blondel, John N. Tsitsiklis
this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable...
Structured Numbers. Properties of a hierarchy of operations on binary trees. (1997)
We introduce a hierarchy of operations on (finite and infinite) binary trees. The operations are obtained by successive repetition of one initial operation. The first three operations are...
Complexity of Stability and Controllability of Elementary Hybrid Systems (1997)
Vincent D. Blondel, John N. Tsitsiklis
: In this paper, we consider simple classes of nonlinear systems and prove that basic questions related to their stability and controllability are either undecidable or computationally intractable...
When is a Pair of Matrices Mortal? (1997)
Vincent D. Blondel, John N. Tsitsiklis
A set of matrices over the integers is said to be k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be mortal...
Structured Numbers. Properties of a hierarchy of operations on binary trees. (1997)
We introduce a hierarchy of operations on (finite and infinite) binary trees. The operations are obtained by successive repetition of one initial operation. The first three operations are...
John N. Tsitsiklis, Vincent D. Blondel
We analyse the computability and the complexity of various definitions of spectral radii for sets of matrices. We show that the joint and generalized spectral radii of two integer matrices are not...
John N. Tsitsiklis, Vincent D. Blondel
and to approximate
When is a Pair of Matrices Mortal? (1996)
Vincent D. Blondel, John N. Tsitsiklis
A set of matrices over the integers is said to be length-k-mortal (with k positive integer) if the zero matrix can be expressed as a product of length k of matrices in the set. The set is said to be...
Abstract. We introduce a hierarchy of operations on (finite and infinite) binary trees. The operations are obtained by successive repetition of one initial operation. The first three operations are...