CS 297: Complex Systems

Office Hours: Thursdays 4-5.30pm, Phillips 717, or by appointment Mon/Tue afternoons.

Class Time/Place: Thursdays 6.10-8.40pm, Tompkins 410

Prerequisites: Core grad courses, interest in theoretical questions, curiosity.

Course description: This course will cover a variety of topics in the general area of Complex Systems. Topics include: the "edge of chaos", phase transitions, power-laws, small-world networks, boolean networks and complex dynamics. Applications to networks and biological systems will also be discussed. Students will be expected to present papers and complete a project.

What the course is about: The formal study of Complex Systems or Complexity has grown from a little-known topic in the 1960's to a full-fledged interdisciplinary subject today, as exemplified by the Santa Fe Institute, a research organization devoted entirely to the study of complex systems. The engaging story of this institute and the unique people who staff it has been told in many books, one of which is the textbook below.

Although there is no formal definition of a complex system, and no agreed upon definition of the field, several key questions and observations together seem to define the area:

There appear to be many examples of systems whose parameters can be changed to exhibit chaos on one end, and "order" on the other end. Sometimes, there is a sharp transition (a phase transition) from one to the other. Why does this happen? Are all complex systems like that?
Many complex systems (the cell, the economy) appear to be constructed out of smaller, simpler units. Indeed, simulated systems with extremely simple units and rules of interaction can exhibit extremely complex behavior. Why is that? Is it true that complex behavior arises mainly out of interactions? What is the nature of the this complex behavior and is it similar across complex systems?
What is the connection between computation and complexity? Are there computational problems that exhibit complexity of the kind seen in physical systems? Is there a connection between hard problems in computer science (NP-completeness) and this sort of complexity? It turns out that there are surprising connections.
What are the dynamics of complex systems? Is the "order" inherently unpredictable (as chaos is) or does the order have predictable properties?
If we are solving a problem that we know is not entirely in the "ordered" regime, can we exploit that somehow? That is, for hard problems, can we exploit some statistical-mechanical properties about its complexity in solving the problem?

Many of the key questions in this multidisciplinary area are still unsolved. What is interesting, from a computer science point of view, is that many questions appear to be mathematically intractable, and so, computer simulation plays a huge role in studying such systems. What is equally interesting is that you don't need a huge background to be able to do your own research in this area. Many key problems are easily defined and explained without much recourse to advanced math.

Possible Textbook: Complexity: the Emerging Science at the Edge of Order and Chaos. Mitchell Waldrop. Simon and Schuster, 1992 (paperback).

Additional (optional, recommended) books:

Six Degrees: The Science of a Connected Age. Duncan Watts. Norton Press, 2003 (paperback).
At Home in the Universe. Stuart Kauffman. Oxford University Press (paperback).
Introduction to Artificial Life. Christoph Adami. Telos Publishing.
Phase Transitions in Combinatorial Optimization Problems. A.K.Hartmann and M.Weight. Wiley Pub., 2005.

Topics: (subject to change)

Small-world and power-law networks. Applications in computer and biological networks.
Percolations and phase transitions.
Boolean networks: models, attractors, types of boolean networks, applications.
Complexity: complex systems, order and chaos, applications in economics, biological systems, cellular automata, dynamics of complex systems.

Some possible papers (subject to change)

Schedule

Coursework