Presentation Review: How the Computational Perspective is Transforming the Sciences

Occasionally I will review interesting talks and papers.

In this talk, Papadimitriou speaks about how computational aspects of sciences have influenced the sciences and are leading to several important results. He touches upon several sciences: quantum physics, statistical mechanics, biological systems, game theory, social networks, economics and brain as he explains how they are deeply interacting with computer science.

Quantum computers can be used to solve problems which otherwise take an exponential amount of time. However, the existing quantum computer experiments work for small number of particles (~6), which translates to quantum algorithms succeeding only for small inputs. As of now, it is unclear whether quantum computers can be built for large inputs. This is a question of testing the theory of Quantum Physics. As Umesh Vazirani says "Quantum computation is as much about testing Quantum Physics as it is about building powerful computers".

In statistical mechanics, when parameters of local interactions evolve, macroscopic properties
change dramatically, and we have a phase transition (melting of solid into liquid is an example). In computer science, certain randomized algorithms are known to converge exponentially faster when the parameters are in the right range. A deep fact is that two phenomena are indeed the same. The same phenomena also occur/used in coding theory and artificial intelligence, as this reference explains.

Then Papadimitriou moves on to explore the relation between biological systems and computer science. One example he shows is a 2006 paper "An optimal brain can be composed of conflicting agents" in which the authors find that "under natural physiological limitations, an optimal decision-making system can involve ‘selfish’ agents that are in conflict with one another, even though the system is designed for a single purpose." This result is on common ground between artificial intelligence multi-agent systems and theory of evolution in biology.

The next biology example is related to Charles Darwin's statement "To think that the eye could evolve by natural selection seems, I freely confess, absurd to the highest degree” considering that such an evolution might be highly improbable. Leslie Valiant in a recent paper "Evolvability" suggests a theory to "explain quantitatively which mechanisms can evolve in realistic population sizes within realistic time periods, and which are too complex. If evolution merely performed a random search it would require exponential time, much too long to explain the complexity of existing biological structures." Natural selection has been used for decades in solving large search problems in artificial intelligence and computer science.

The third biology example involves population selection processes used in search in artificial intelligence and computer science (also on the lines of Darwin's theory of selection). Simulated annealing and genetic algorithms are widely used search methods. In these methods search is carried out by a population of search "threads" - and these threads evolve through a selection process in each "generation" of threads. Simulated annealing is akin to asexual reproduction. Genetic algorithms are akin to sexual reproduction. Simulated annealing works so much better than genetic algorithms in solving optimization problems. Why is that? As per a recent paper "Genetic Modularity" by Livnat and Papadimitriou (yet to be published), sex favors variance over optimization. This also means sex favors creation of new species.

Internet is a large system that was never designed and its study is akin to the study of natural processes and social science. In game theory, Nash and other proved the existence of equilibria, which are predictions of behavior. Computing equilibria can be used to predict the stock market, for example. A recent result (paper here) says that computing a Nash equilibrium is an intractable problem.

In social networks, recent results (paper) show that "it is a small world". That is, most people are within a few "hops" or connections from you. This result follows from maths developed for study of internet viz how many routers does a packet have to traverse to reach its destination.

Link to the original presentation.