January

2009-01-15

Start-of-quarter, organizational meeting:

Give updates on current research.

Discuss goals for quarter.

2009-01-22

2nd organizational meeting:

Finish updates on current research.

Set schedule for research talks.

Possible talks for next quarter:

Sean Whalen: Structural Drift

Ben Johnson: Game Theory Review and Multiagent Dynamical Systems

Chris/John/Jim: E from eM

Chris: Generalized HMMs

Youval Dar: Proteins/Prions/Mad Cows

Nick Travers: Period-3 implies chaos

Richard Watson: Causality or Neural nets

(Guest) Dave Feldman: 2D information theory or ?

(Guest) Karoline Wiesner: Quantum Machines or Computation in Bio-molecules or ?

2009-01-29

Ed Puckett

Py++: Python interface to C/C++

February

2009-02-05

Chris Ellison

Alternative models of probabilistic automata

Readings:

1. Probabilistic Finite-State Machines - Part I
2. Probabilistic Finite-State Machines - Part II

2009-02-12

Dawn Sumner and John Mahoney

LineBugs

Readings:

3. Modern Microbialite Morphology (webpage)
4. Microbial Motility and Morphological Biosignatures (abstract)

2009-02-19

Dave Albers (Columbia University)

Time-dependent density correlation in complex dynamics

Abstract:

Preliminary work regarding the evolution of time-dependent densities will be presented. In particular, the presentation will focus on time-delayed mutual information treated as a time-series; the subsequent dynamics of this time-series will be analyzed and interpreted. The results have particular relevance to system memory (as quantified by persistent correlations), as well as the ability to accurately model the system in question. Furthermore, complex dynamics (e.g., high-dimensional chaotic or random) are categorized via the memory present in the given system.

2009-02-26

Spencer Mathews

Finitary Process Soup

March

2009-03-05

Benny Brown

Robotics Multiagent Development System

2009-03-12

Nick Travers

Cellular Automata Computational Mechanics

April

2009-04-08

Organizational

Planned meetings for quarter.

2009-04-15

Susanna Still (Information and Computing Sciences, U Hawaii)

Interactive Learning

2009-04-22

Kevin Mitchell (UC Merced)

Using invariant manifolds to classify chaotic transport pathways in mixed phase space

Abstract:

We describe how the topological structure of stable and unstable manifolds (so-called homo- or hetero-clinic tangles) embedded within a chaotic phase space can be used to extract a symbolic classification of chaotic transport and escape pathways. We pay particular attention to phase spaces that contain a mixture of both chaos and regularity. For such systems, the dynamics in the vicinity of "stable islands" is known to be particularly troublesome to analyze. We describe a technique that utilizes the structure of invariant manifolds in the vicinity of such stable islands to extract a symbolic model for the islands' influence on the transport process. Though our analysis focuses on Hamiltonian systems of two degrees-of-freedom, we also discuss the extension of our technique to higher dimensional phase spaces. We illustrate this technique with a few specific examples drawn from atomic physics.

2009-04-29

Discussion

Obama's speech to the National Academy

(time permitting, other topics as well)

article

video

May

2009-05-06

Youval Dar

Looking For L $\beta$ H: A Quick Evaluation of Whether A Protein Segment Is Able To Form A Left Hand Beta Helix Structure

Readings:

5. Introduction

2009-05-13

Manuel Marques-Pita (Portland State University)

Conceptual Structure in Cellular Automata

Abstract:

In this talk I introduce wildcard redescriptions (schemata) of the highest-performing CA rules for the well-known density-classification task, and explore the notion of conceptual structure revealed by such redescriptions. In particular I will focus on one such property: Process Symmetry, which is present in rules that perform equally well for initial configurations with majority 0s and majority 1's. I will show that schemata make it possible to compress the look-up tables for CAs, and make it possible to explain what a CA is doing on the local level. This raises the question central to my research: Can such schemata be used to characterize mechanisms for performing collective computation in cellular automata? I will use a simple example, the GKL rule, in order to explore possible answers to this question.

Readings:

6. Conceptual Structure in Cellular Automata: The Density Classification Task
7. The Role of Conceptual Structure in Learning Cellular Automata to Perform Collective Computation

2009-05-20

David Feldman (College of the Atlantic)

Complexity vs. Entropy in Cellular Automata: Wedges not Edges

Abstract:

The past several decades has seen a considerable effort toward the development of measures of complexity. These measures are intended to capture, to varying degrees, our intuitive notions of pattern, regularity, memory, or structure. One of the questions motivating this work concerns the nature of the relationship between complexity and entropy. There is a persistent belief that maximally complex phenomena those that combine order and disorder. In particular, it is often claimed that systems' complexity reach a sharp maximum at a well defined transition point between order and disorder. The phenomena is referred to as the "edge of chaos."

In this talk I will review several information-theoretic measures of randomness and structural complexity. I will then present calculations of complexity-entropy diagrams for a range of systems: one-dimensional maps of the unit interval; one- and two-dimensional Ising models; Markov chains; cellular automata; and topological languages. (Feldman, Crutchfield, and McTague. Chaos. 18:043106. 2008. DOI: 10.1063/1.2991106. http://arxiv.org/abs/0806.4789) A central conclusion that will emerge from this survey is that there is a large range of possible complexity-entropy behaviors. In particular, there is not a universal complexity-entropy curve and "edges of chaos" are by no means typical. If time permits I will present recent computations of complexity-entropy diagrams for one- and two-dimensional cellular automata that demonstrate that there is not a clear complexity-entropy transition for cellular automata.

I will conclude with some speculation on why the belief in the edge of chaos phenomena has been so persistent and mention several possible avenues for future research.

Readings:

8. The Organization of Intrinsic Computation: Complexity-Entropy Diagrams and the Diversity of Natural Information Processing

2009-05-27

Carl Boettiger

Inferring Adaptive Landscapes from Phylogenetic Trees

Abstract:

Adaptive landscapes are powerful representations of the forces of natural selection and underlie much evolutionary theory. However, empirically mapping an adaptive landscape is a challenging process, relying on measurements of both trait and fitness values across a distribution of species. Meanwhile, recent advances in both laboratory and computational genetics have made accurate phylogenetic trees readily available for many species. Rather than look at species independently, we can now use their shared history and ancestry to explore questions about the adaptive landscapes on which they have evolved. We use the phylogenetic trees to take us back into the past and follow the course of evolution and speciation over time. Existing methods have only been able to address the case of a single adaptive peak, since they rely partly on an analytic technique that requires a linear selective force. Multiple adaptive peaks require nonlinear forces, and a computational paradigm shift in the approach to comparative methods. Computational tricks and high-performance computing resources enable us to explore arbitrary landscapes -- non-linear selection with multiple peaks.

June

2009-06-03

Ryan James

Readings:

9. Complexity of Two-Dimensional Patterns

2009-06-10

Jörg Reichardt (University of Würzburg)

Reducing Complex Systems

Abstract:

All research is, at least in principle, pattern detection. More specifically, it is pattern detection in experimental data. Scientists then state hypotheses about how structure and patterns emerge in data. In some cases, scientists are able to reduce the description of a system to only few relevant system parameters and can describe functional dependencies between these in mathematical form. When studying complex systems, especially in the bio-sciences, scientists are often overwhelmed by the amount of data they have to digest. Fortunately, we can surrender the task of pattern detection and hypothesis formulation to a computer.

We will discuss the chances and limitations of this automated and data-driven research using an example from network analysis. Many complex systems can be abstracted as networks. The structure of these networks is intimately linked to global properties of the system. This will be an ideal test-case to see how well automated methods can detect inherent structure in networks.

A central question addressed will be if we can break the “curse of dimensionality” – in other words: How can we be sure that what a computer finds in data is truly reflecting structure in the data and not a mere result of an automated search through a large hypothesis space? Our example will show that automated methods may, contrary to many claims from the data-mining community, only be able to automatically discover patterns with a large effect size in network data and miss essential, but less pronounced structure. The observed limitations are not due to the finite size of the data-set or poor data-quality, but rather due to the inherent sparsity of the network and hence present a fundamental aspect of network and complex systems analysis in general.

Readings:

10. (Un)detectable cluster structure in sparse networks

July

August

September

October

2009-10-06

Chris Ellison

Inferring eMs with MCMC

2009-10-13

Elizabeth Leicht (UCD Postdoc)

Methods and Models for the Study of Complex Networks

Abstract:

Many biological, social, and technological systems take the form of networks. Over the past decade a science of networks has been emerging and providing insights into the structure and function of many disparate types of networks, such as protein-interactions in a cell, collaboration networks of scientists, the Internet, and the World Wide Web. A great deal of this work emphasizes the study of network growth and structure, including phase transitions in network structure, and tools from statistical physics are enabling many of the advances. The first part of this talk will focus on key aspects of network structure, in particular modularity or community structure, methods for its detection, and implications for real networks. In addition, the talk will describe how modularity can be exploited to alter the location of the phase transition marking the onset of large-scale connectivity in networks and how these results impact our understanding of systems of interacting networks, with implications for diseases spreading across geographic regions and for engineering minimalist communications networks.

2009-10-20

Gergana Bounova (MIT)

November

2009-11-17

Dave Albers (Columbia University)