To refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1m25r
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chazelle, Bernard | - |
dc.date.accessioned | 2021-10-08T19:45:59Z | - |
dc.date.available | 2021-10-08T19:45:59Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.citation | Chazelle, Bernard. "How Many Bits Can a Flock of Birds Compute?" Theory of Computing 10, no. 16 (2014): pp. 421-451. doi:10.4086/toc.2014.v010a016 | en_US |
dc.identifier.issn | 1557-2862 | - |
dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr1m25r | - |
dc.description.abstract | We derive a tight bound on the time it takes for a flock of birds to reach equilibrium in a standard model. Birds navigate by constantly averaging their velocities with those of their neighbors within a fixed distance. It is known that the system converges after a number of steps no greater than a tower-of-twos of height logarithmic in the number of birds. We show that this astronomical bound is actually tight in the worst case. We do so by viewing the bird flock as a distributed computing device and deriving a sharp estimate on the growth of its busy-beaver function. The proof highlights the use of spectral techniques in natural algorithms. | en_US |
dc.format.extent | 421 - 451 | en_US |
dc.language.iso | en_US | en_US |
dc.relation.ispartof | Theory of Computing | en_US |
dc.rights | Final published version. This is an open access article. | en_US |
dc.title | How Many Bits Can a Flock of Birds Compute? | en_US |
dc.type | Journal Article | en_US |
dc.identifier.doi | 10.4086/toc.2014.v010a016 | - |
pu.type.symplectic | http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article | en_US |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
BitsFlockBirdsCompute.pdf | 502.17 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.