CSL Master Calendar

Back to Listing

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
E-Mail
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.

link for robots only