## DCL Lecture Series: Ana Busic "Probabilistic cellular automata: density classification problem"

- Event Type
- Seminar/Symposium
- Sponsor
- Decision and Control Laboratory, Coordinated Science Laboratory
- Location
- CSL Auditorium (B02)
- Date
- Apr 16, 2014 3:00 - 4:00 pm
- Speaker
- Ana Busic, Research Scientist at Inria Paris - Rocquencourt
- Contact
- Angie Ellis
- amellis@illinois.edu
- Phone
- 217/30-1910
- Views
- 83
- Originating Calendar
- CSL Decision and Control Group
**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***Ana Busic***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**___________________________________________________________________________________________________________________________________________________________________________________________

**Abstract**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.

**Biography****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.