TY - GEN

T1 - Natural algorithms

AU - Chazelle, Bernard

PY - 2009

Y1 - 2009

N2 - We provide further evidence that the study of complex self-organizing systems can benefit from an algorithmic perspective. The subject has been traditionally viewed through the lens of physics and control theory. Using tools typically associated with theoretical computer science, we settle an old question in theoretical ecology: bounding the convergence of bird flocks. We bound the time to reach steady state by a tower-of-twos of height linear in the number of birds. We prove that, surprisingly, the tower-of-twos growth is intrinsic to the model. This unexpected result demonstrates the merits of approaching biological dynamical systems as "natural algorithms" and applying algorithmic techniques to them.

AB - We provide further evidence that the study of complex self-organizing systems can benefit from an algorithmic perspective. The subject has been traditionally viewed through the lens of physics and control theory. Using tools typically associated with theoretical computer science, we settle an old question in theoretical ecology: bounding the convergence of bird flocks. We bound the time to reach steady state by a tower-of-twos of height linear in the number of birds. We prove that, surprisingly, the tower-of-twos growth is intrinsic to the model. This unexpected result demonstrates the merits of approaching biological dynamical systems as "natural algorithms" and applying algorithmic techniques to them.

UR - http://www.scopus.com/inward/record.url?scp=70349141346&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349141346&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973068.47

DO - 10.1137/1.9781611973068.47

M3 - Conference contribution

AN - SCOPUS:70349141346

SN - 9780898716801

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 422

EP - 431

BT - Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery

T2 - 20th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 4 January 2009 through 6 January 2009

ER -