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 ( chazelle@cs.princeton.
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.