Influence
system
figure 10. the algorithmic calculus.

Coding tree

flow tracker

Coupling times renormalization scales

arborator

Renormalization Dictionary

parameters

Periodic or chaotic

associative but not commutative. It begins by marking certain nodes of T1 as absorbed and pruning the subtrees below. This operation is called absorption by analogy with the absorbing states of a Markov chain: any orbit reaching an absorbed leaf comes to a halt, broken only after we reattach a copy of T2 at that leaf. The copy must be properly cropped.

6. 3. Dynamic renormalization

Direct sums model independent subsystems through parallel composition. Direct products model sequential composition. What are the benefits? In pursuit of some form of contractivity, the generalized flow tracker classifies the communication graphs by their connectivity properties and breaks up orbits into sequential segments accordingly (Figure 10). It partitions the set of stochastic matrices into classes and decomposes the coding tree T into maximal subtrees consisting of nodes v with matrices Pv from the same class. The power of this “renormalization” procedure is that it can be repeated recursively. We classify the communication graphs by their block-directionality type: G (x) is of type m → n − m if the agents can be partitioned into A, B (|A| = m) so that no B-agent ever links to an A-agent; if in addition, no A-agent links to any B-agent, G (x) is of type m → n − m. If we define the renormalization scale wk = | Wtk+ 1| − n + m for k = 1, . . . , l − 1 (where Wt denotes the set of wet nodes), any path of the coding tree can be expressed as

1. Afek, Y., Alon, N., Barad, O., Hornstein, E., Barkai, N., Bar-Joseph, Z. A biological solution to a fundamental distributed computing problem. Science 331 (2011), 183–185.

2. Bonifaci, V., mehlhorn, K., Varma, g. Physarum can compute shortest paths. In Proceedings of 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (2012), 233–240.

3. Camazine, S., deneubourg, J.L., Franks, N., Sneyd, J., Bonabeau, E., Theraulaz, g. Self-Organization in Biological Systems, Princeton University Press, 2001.

4. Chazelle, B. The convergence of bird flocking, arXiv:0905.4241vl, 2009. Prelim, version in Proceedings of SIAM SODA 2009, with improvements in Proceedings of ACM SoCG 2010.

5. Chazelle, B. The total s-energy of a multiagent system, SIAM J. Control Optim. 49 (2011), 1680–1706.

6. Chazelle, B. The dynamics of influence systems, arXiv:1204.3946v2, 2012. Prelim, version in Proceedings of 53rd FOCS, 2012.

7. Collins, g. E. quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Proceedings of 2nd GI Conference on Automata Theory and Formal Languages (1975), Springer-Verlag, New York, 134–183.

8. Cucker, F., Smale, S. Emergent behavior in flocks. IEEE Trans. Automatic Control 52 (2007), 852–862.

9. Fisher, J., Harel, d., Henzinger, T.A. Biology as reactivity. Commun. ACM 54 (2011), 72–82.

10. Hegselmann, R., Krause, U. Opinion dynamics and bounded confidence models, analysis, and simulation. J. Artif. Soc. Soc. Simulat. 5 (2002), 3.

11. Hegselmann R, Krause U. Truth and cognitive division of labor: first steps towards a computer aided social epistemology. J. Artif. Soc. Soc. Simulat. 9 (2006).

12. Hendrickx, J.m., Blondel, V.d.
Convergence of different linear
and non-linear Vicsek models. In
Proceedings of 17th International
Symposium on Mathematical
Theory of Networks and Systems
(MTNS2006) (July 2006, Kyoto,
Japan), 1229–1240.

 

Bernard Chazelle ( [e-mail]. edu), department of Computer Science, Princeton University.

The subscripts indicate the lengths of the (underlined) renormalized subsystems. Varying the shift d may change the coding tree, so we extend all the previous definitions to the global coding tree TD with phase space [0, 1]n × D, for a tiny interval D centered at the origin. We have all the elements in place for the algorithmic proof of Theorem 1 to proceed: see Chazelle6 for details.

acknowledgments I wish to thank Andrew Appel, Stan Leibler, Ronitt Rubinfeld, David Walker, and the anonymous referee for helpful comments and suggestions. This work was supported in part by NSF grants CCF-0832797, CCF-0963825, and CCF-1016250.