Arnab Bhattacharyya, Massachusetts Institute of Technology
Noise plays both a malevolent as well as a beneficial role in natural systems.
Its malevolent side is shown when individual components of a system malfunction due to random failures. Through the years, natural systems have evolved to be resilient to such failures of their parts. The resilience displayed is usually adaptive in a sense that is not usually displayed in man-made systems. We give examples of such adaptivity, formalize adaptation in the context of computer science, and prove theorems showing separation between adaptivity and non-adaptivity.
In a related work, we study correlations between noisy Markov processes. We restrict our Markov processes to be random walks on labelled directed graphs, and we discuss a natural interpretation of this restriction. We use group representation theory to give examples of graphs where noise causes two noisily correlated walks to rapidly decorrelate from each other. While such graphs are useful for certain combinatorial applications in theoretical computer science, our interpretation suggests they should not arise in natural systems.
Finally, we discuss the beneficial aspects of noise in natural systems. Organisms use noise in the form of mutations in order to explore possible genotypes and survive in the face of changing environments. Moreover, the exploration has to be computationally efficient in the sense that the system needs to rapidly find a fit genotype, without cycling through all possible genotypes. Further, we note that the result of the evolutionary process is itself in general an adaptive process. From a computer science perspective, then, the interesting problem is to devise search techniques that rapidly converge toward the most fit adaptive solution. We formalize the problem and present partial results.
Abstract Author(s): Arnab Bhattacharyya