PLEASE JOIN US FOR A COFFEE AND COOKIE RECEPTION FOLLOWING THE SEMINAR IN THE LOWER LEVEL LOBBY
Decision and Control Lecture Series
Decision and Control Laboratory, Coordinated Science Laboratory
Probabilistic cellular automata: density classification problem
Research Scientist, Inria Paris - Rocquencourt
Computer Science Department, Ecole Normale Supérieure, Paris, France
Wednesday, April 16, 2014
3:00 p.m. to 4:00 p.m.
B02 CSL Auditorium
Cellular automata are dynamical systems with incredibly complex behavior, generated by very simple local interaction rules. Applications range from theoretical computer science and computational complexity, distributed computing, statistical physics and biology. Analyzing CA is difficult and until now very little is known, despite the fact that CA have been studied since the 1940's. Many open questions are related to distributed computing and resistance to noise (in the initial configuration or in the dynamics). The main focus will be on the density classification problem. Consider an infinite graph with nodes initially labeled by independent Bernoulli random variables of parameter p. We want to design a deterministic or probabilistic CA that evolves on this graph and decides whether p is smaller or larger than 1/2. Precisely, the trajectories should converge to the uniform configuration with only 0's if p<1/2, and only 1's if p>1/2. The difficulty is twofold: 1) it is impossible to centralize the information (nodes are indistinguishable); 2) it is impossible to use classical counting techniques (labels contain only binary information). We will present solutions to the problem in some particular cases and discuss related open problems.
Ana Busic is a Research Scientist at Inria Paris - Rocquencourt and a member of Computer Science Department of Ecole Normale Supérieure, Paris, France. She was previously a CNRS Postdoctoral Fellow at the University Paris 7 from 2008 to 2009 and a Postoctoral Fellow at Inria Grenoble from 2007 to 2008. Ana Busic received a B.S. degree in Mathematics from the University of Zagreb in 2002, a M.S. degree in Mathematics in 2003, and a Ph.D. degree in Computer Science in 2007, both from the University of Versailles. Her research interests include stochastic modeling, cellular automata, simulation, and performance evaluation of communication networks and energy systems.