Short works

Books : reviews

Tino Gramss, Stefan Bornholdt, Michael Gross, Melanie Mitchell, Thomas Pellizzari, eds.
Non-Standard Computation: molecular computation, cellular automata, evolutionary algorithms, quantum computers.
Wiley-VCH. 1998

rating : 4.5 : passes the time
review : 2 June 1999

This promised to be a very interesting book, but it was let down for me by being too low level -- too much about the scientific and technological bases, and not enough about any new computational paradigms. (The very poor level of proof reading, with some chapters thick with spelling mistakes, also detracts.)

I was hoping for an overview of what new tools are being added to our computational capability, with maybe a review of the current state of the art, but what I got was a bunch of essays that have an idiosyncratic viewpoint, with all the details in the wrong places (for me, at least).

For example, the chapter on Genetic Algorithms devotes hardly any space to the schemata model (beyond saying it is intuitive) but instead develops a "statistical mechanics" model, without then providing the intuition of how this model helps us to cast or solve new computational problems. It also seems to imply that mutation is the key concept, with cross-over just an interesting second order add-on (whereas the study of genetic algorithms has shown is that cross-over is key, with mutation playing a surprisingly small role).

The two chapters on quantum computing range over the theoretical QM underpinnings, and the current technology, but again provide no intuition of how these devices work as computers. (And the second of these chapters has an almost useless bibliography, since it omits the papers' titles.)

So I was left disappointed.


Heinz Georg Schuster. Introduction to Non-standard Computation. 1998
Michael Gross. Molecular Computation. 1998
Using DNA to solve computational problems can allow massive parallelism, by exploring 1019 cases in parallel. This doesn't solve the trouble with exponentially difficult problems -- but it does delay it by several orders of magnitude! Currently, to program such a device, one needs to be a good bench chemist -- by DNA-sequencing technologies might make automatic compilation easier.
    Supramolecules are large molecules that are (partly) built from non-covalent bonds. Natural supramolecules include DNA; artificial ones also look promising for computational applications.
Stefan Bornholdt. Genetic Algorithms. 1998
Solving optimisation problems with artificial evolution
Melanie Mitchell. Computation in Cellular Automata: A Selected Review. 1998
A good overview of what cellular automata are, and a clear description of how higher-level 'particles' can be used to design cellular automata algorithms. [By far the best chapter. I find cellular automata intrinsically interesting, but this chapter still left me wondering what advantages they have as computers.]
Tino Gramss. The Theory of Quantum Computation: An Introduction. 1998
Theoretical quantum mechanic underpinnings of quantum computers -- all Hamiltonians and reversibility
Thomas Pellizzari. Quantum Computers: First Steps Towards a Realization. 1998
Current technology for building (very small!) quantum computers, including error correction

Stefan Bornholdt, Heinz Georg Schuster, eds.
Handbook of Graphs and Networks: from the genome to the internet.
Wiley-VCH. 2003


Bela Bollobas, Oliver M. Riordan. Mathematical results on scale-free random graphs. 2003
Mark E. J. Newman. Random graphs as models of networks. 2003
Albert-Laszlo Barabasi. Emergence of scaling in complex networks. 2003
Reuven Cohen, Shlomo Havlin, Daniel ben-Avraham. Structural properties of scale-free networks. 2003
Romualdo Pastor-Satorras, Alessandro Vespignani. Epidemics and immunization in scale-free networks. 2003
Ralf J. Sommer. Cells and genes as networks in nematode development and evolution. 2003
Ricard V. Sole, Romualdo Pastor-Satorras. Complex networks in genomics and proteomics. 2003
Sergei Maslov, Kim Sneppen, Uri Alon. Correlation profiles and motifs in complex networks. 2003
Wolfgang Kinzel. Theory of interacting neural networks. 2003
Barbara Drossel, Alan J. McKane. Modelling food webs. 2003
Kai Nagel. Traffic networks. 2003
Alan Kirman. Economic networks. 2003
Lada A. Adamic, Rajan M. Lukose, Bernardo A. Huberman. Local search in unstructured networks. 2003
Sergei N. Dorogovtsev, Jose F. F. Mendes. Accelerated growth of networks. 2003
Gerard Weisbuch, Sorin Solomon. Social percolators and self organized criticality. 2003
Sanjay Jain, Sandeep Krishna. Graph theory and the evolution of autocatalytic networks. 2003