CS 297: Complex Systems
Prof. Rahul Simha
- Office Hours: Thursdays 4-5.30pm, Phillips 717,
or by appointment Mon/Tue afternoons.
- Class Time/Place: Thursdays
6.10-8.40pm, Tompkins 410
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
- 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
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:
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.
- 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
- 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
- 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?
- 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.
- 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,
- Complexity: complex systems, order and chaos, applications in
economics, biological systems, cellular automata, dynamics of complex
- Some possible papers (subject to change)