-
Physics of Complex Systems
Emergence, Innovation & Robustness in Evolutionary Systems
Information Processing & Computation in Complex Systems
Dynamics & Quantitative Studies of Human Behavior
Emergence, Organization & Dynamics of Living Systems
Information Processing & Computation in Complex Systems
Computation has been a central theme of SFI research since its inception, including seminal contributions in evolutionary and adaptive computation, relationships between physics and computation, models of distributed and collective agent-based computation, and applications of biological insights to engineered computational systems. For a comprehensive list of SFI researchers working on topics related to information processing and computation, click here.
Quantum Algorithms and Cryptography
Quantum computing began in earnest in 1994, when Peter Shor showed that a
quantum computer could factor large integers exponentially faster than any known
classical algorithm. Shor’s algorithm would break RSA public-key
cryptography, on which much of modern commerce and communication is based. Since
then, quantum computing has become a growing field in computer science, and has
repaid its debt to physics in giving rise to a deeper understanding of quantum
entanglement and its consequences. Shor’s celebrated factoring
algorithm fits inside a more general frame-work, called the hidden subgroup
problem (HSP). This problem seeks to find the symmetries in a function,
where the symmetries are defined by some “hidden
subgroup”, H, and, consequently, an important task is to
find this hidden subgroup. The HSP includes virtually every problem for which
quantum algorithms offer an exponential speedup over classical computing. Most
interestingly, if the HSP could be solved for the symmetric group Sn,
i.e., the group of permutations of n objects, this would produce an
efficient algorithm for the Graph Isomorphism problem. This problem
asks whether two graphs have the have the same topology up to a relabeling of
their vertices. Like factoring, this problem appears to be intractable
for classical computers, and so an efficient quantum algorithm for it would be
extremely exciting. A major obstacle to extending Shor’s approach to
Graph Isomorphism is that the symmetric group is nonabelian; that is,
ab 
ba for some pairs of elements a,b. However,
some progress by SFI Researchers, including SFI Professor Cris Moore , SFI
External Professor Dan Rockmore , and former SFI Postdoctoral Fellow David Bacon
, has been made on a number of families of “slightly”
nonabelian groups. One goal of future research is to tackle highly nonabelian
groups. This work has important implications for cryptography.
Phase Transitions in NP-Hard Constraint Satisfaction Problems
Many NP-hard constraint satisfaction problems, such as k-SAT or Graph Coloring, have “phase transitions” in which they jump from satisfiability to unsatisfiability when the density of constraints passes a critical threshold. SFI Professor Cris Moore and colleagues proved a long-standing conjecture that the critical density for k-SAT is proportional to 2k. They proved tight bounds on the chromatic number of random graphs and on the phase transition in a hypergraph problem studied by Paul Erdös. Moore and colleagues have also provided an exact solution for the phase transition in another satisfiability problem, showing a strong analogy to the “second-order phase transitions” of statistical physics.
Pattern Discovery in Time Series and Spatiotemporal Data
SFI External Professor Jim Crutchfield , former SFI Post-doc Cosma Shalizi , and collaborators have developed an approach to pattern discovery, by contrast with pattern recognition or pattern learning, and have exploited their computational mechanics approach to address pattern discovery problems. In pattern recognition and pattern learning problems, the representations used are generally pre-specified. In pattern discovery, by contrast, the aim is to avoid (as far as possible) such a priori assumptions about what structures are relevant. Whereas there are useful approaches for pattern discovery via trial and error, some even informed by empirical psychology (see research of SFI External Professor John Holland ) Crutchfield and colleagues have shown that a more direct approach based on computational mechanics is not only possible but also illuminates the ideal results and the limitations of all pattern-discovery methods.
Computational mechanics originated in physics as a complementary approach to statistical mechanics for dealing with complex, organized systems. In such systems the “forward” approach of statistical mechanics, namely, deriving macroscopic properties from the interactions of microscopic components, is often intractable, although data can be had in abundance. Computational mechanics follows an “inverse” strategy, extending the idea of extracting “geometry from a time series”. It builds the simplest model capable of capturing the patterns in the data, a representation of the causal structure of the hidden process that generated the observed behavior. This representation— the €-machine—is the unique maximally efficient model of the observed data-generating process. This approach has been used by Crutchfield and SFI External Professor Nihat Ay and others to analyze dynamical systems, cellular automata, hidden Markov models, evolved spatial computation, stochastic resonance, and globally coupled maps.
Evolving and Understanding Computation in Cellular Arrays
There is much current interest and progress in building decentralized, distributed computing networks, at the macroscale (e.g., for networks of sensors) and at the nanoscale (e.g., for self-assembled molecular electronics). However, there has been less progress on programming and combining these devices to produce useful computation. SFI External Professor Melanie Mitchell contends that a more powerful and ultimately practical approach is to harness the ability of cellular arrays to form complex patterns in ways that will produce decentralized collective information processing. This approach to information processing is very different from classical approaches, and requires non-standard programming and analysis techniques. Mitchell and collaborators are investigating evolutionary computation as a method for "programming" cellular arrays to perform computations, to investigate analysis techniques that build on both pattern dynamics and classical computation theory, and to extend beyond the idealized cases of noise-free systems to investigate the "real-world" requirements of dealing with asynchronous updating, unreliable components, and non-periodic boundary conditions.
Work on cellular automata at SFI also includes research by SFI Postdoctoral Fellow Emily Gamber on CA’s in arbitrary dimensions and on arbitrary subshift spaces, from the point of view of symbolic and topological dynamics. SFI Postdoctoral Fellow Thimo Rohlf is interested in dynamics and learning in simple dynamical systems (e.g., cellular automata) with memory and/or delays –in particular, how memory and delays "complexify" dynamics and affect the computational capacities of these systems.
A key question for research on communication is how communication and information processing arise in nature and society. External Professor John Miller studies this process using systems of evolving automata (Moore machines) that "learn" to communicate with one another and act on the result. Automata provide a nice representation of agents able to do simple information processing on discrete inputs and outputs---such a representation is rich in possibilities. Automata are allowed to interact with one another and receive payoffs based on those interactions. The better-performing automata are then allowed to reproduce with some variation. Over time, this allows the adaptive system to effectively explore a broad space of potential strategies. In such a coevolutionary system, Miller has found that communication protocols can emerge and, using these, agents can achieve much higher levels of performance in stylized games.
Statistical Order and Robust Information Processing
In his highly influential book, What is Life, Shrodinger distinguished between two sources of order in biological systems. One is classical order, the usual example being a mechanical clock. The other is the many-atomic order of statistical mechanics, where ordered states are derived through an appropriate averaging over many interacting particles. In biology, statistical order plays the dominant role, dampening out the thermal fluctuations afflicting components. In order to build cells capable of responding adaptively to environmental cues, elaborate signaling networks have evolved capable of reliably, transducing energy from the environment into internal informational states of the cell. SFI Professors David Krakauer and Eric Smith and External Professors Walter Fontana and Supriya Krishnamurthy are exploring how signal transduction makes use of statistical, molecular switches, many of which involve the covalent modification of proteins, giving rise to chemically distinct protein states.
Robustness arises as a byproduct of statistical order in biology as individual components are frequently correlated in their activity, and this can be exploited as a source of redundancy. External Professor Nihat Ay and David Krakauer consider information flow in biological networks and how redundant activity distributed across the network can be used to restore system function upon removal of one or more nodes. The analysis of network robustness requires the development of a concept of network causality -- how nodes contribute to a collective function and how nodes differ in their importance. Similar principles apply once we reach the social level, and in animal societies communication networks play an essential role in facilitating transitions to facultative “social units” –an important issue in research on the major evolutionary transitions. SFI Research Fellow Jessica Flack and Krakauer have considered how power is encoded in communication networks, and how signaling strategies have evolved so as to promote group-level redundancy required to correct individual signaling errors that, if left unchecked, would produce functionally suboptimal (given component characteristics and interactions) higher-level structures (see Emergence, Organization, & Dynamics of Living Systems ).
In related work, SFI External Professor John Miller is developing nonlinear optimization algorithms for biological systems that might provide new insights into how such systems function, and how they can be controlled. For example, molecular pathways often engender redundancies, implying that the effect on an organism of knocking out one gene depends on what other genes are knocked out. Similarly, the impact on a cancerous cell of adding another drug to a chemotherapy cocktail depends on what other drugs are already present in the mix. Consider the problem of discovering novel and effective chemotherapy cocktails. If drugs in such cocktails react with one another in nonlinear ways, then even small sets of drugs may be impossible to exhaustively explore given the implied combinatorics (a set of twenty drugs can create over one million unique cocktails). However, the space of possibilities becomes manageable using a nonlinear optimization approach. A nonlinear optimization algorithm can be used to search the space of possible cocktails given an objective like finding minimal cocktails that maximally inhibit the growth of cancerous cells. Miller, in collaboration with colleagues at the MD Anderson Cancer Center in Houston, implemented such an algorithm for cocktails to inhibit lung carcinoma. The algorithm was able to find an effective cocktail (with inhibition levels four standard deviations above the mean) by sampling less than one hundred cocktails out of a space of over half a million potential cocktails.
Biologically Inspired Solutions to Computational Problems
The explosive growth of the Internet has created new opportunities and risks by increasing the number of contacts between separately administered computing resources. Widespread networking and mobility has blurred many traditional computer system distinctions, including those between operating system and application, network and computer, user and administrator, and program and data. An increasing number of executable codes, including applets, agents, viruses, email attachments, and download-able software, are escaping the confines of their original systems and spreading through communications networks. These programs coexist and co-evolve with us in our world, not always to good effect. Computers are routinely disabled by network-borne infections, browsers crash due to unforeseen interactions between an applet and a language implementation, and applications are broken by operating system upgrades. SFI Professor Stephanie Forrest and colleagues refer to this situation as “computation in the wild”, to capture the fact that software is developed, distributed, stored, and executed in rich and dynamic environments populated by other programs and computers, which collectively form a hardware/software ecosystem. Consequently, Forrest believes that networked computer systems can be better understood, developed, and controlled when viewed from the perspective of living systems, as opposed to the perspective of conventional software and hardware engineering principles.
Taking seriously the analogy between computer systems and living systems requires rethinking several aspects of the computing infrastructure—developing design strategies from biology, constructing software that can survive in the wild, understanding the current software ecosystem, and recognizing that all nontrivial software must evolve. There are deep connections between computation and life, so much so that in some important ways, “living computer systems” are already pervasive, and moreover, such systems are spreading rapidly and will have major impact on human life and society in the future. Such biologically inspired approaches to computation and computer security have led to ideas such as “computational immune systems” and hardware/software that emphasize autonomy, robustness, adaptation, self-repair, redundancy, diversity, and even disposable components. The value of diversity in current hardware and software “monoculture” is becoming mainstream, as evidenced by Microsoft Corporation’s recent announcement that a simple form of diversity termed “address space randomization” will be incorporated into Vista, the next generation of the Windows operating system. Research by Forrest and others at SFI focuses on techniques for promoting computational diversity in the communication and application layers of computer systems as well in lower-level component layers (e.g. instruction sets and memory layouts). Forrest is also pursuing the possibility of using evolutionary computation techniques from biological systems to produce software diversity within a single standard.
Please direct comments on the content of this page to Jessica Flack ().