Alan Dix - research topics - randomness

randomness in computing

Traditional algorithms are deterministic, attempting to find the unique or the best solution. In contrast, 'modern' algorithmics (modern here really goes back at least 30 years!), including neural networks, genetic algorithms and simulated annealing, makes heavy use of randomness. These algorithms are non-deterministic and find 'a solution' rather than 'the solution' and 'good' rather than 'best'. Because of this more relaxed and inexact approach to solutions, these algorithms can tackle problems that are otherwise intractable including NP-hard ones. Quality is traded for computation. In some cases, this is a simple cost-benefit trade-off, in others this is because the computation for the exact solution would be impossible.

Examples of these algorithms include:

In some of these cases randomness is used simply to reduce the computational effort - if one could do the calculation in full it would be better but the random version is just 'good enough'. However in many cases, the randomness is essential otherwise the system would be worse or incorrect.


[CDMA 2000]  CDMA Develpment Group. What is CDMA (Code Division Multiple Access)?  (accessed 17th Nov 2001, dated © 2000) []

[Dugelay 2001]  Jean-Luc Dugelay and Fabien A. P. Petitcolas.   Digital watermarking (tutorial). SAICSIT 2001, South African Institute of Computer Scientists and Information Technologists Annual Conference, University of South Africa, Pretoria, September 2001. pp.25-28. [abstract]

[Dugelay 1999]  Jean-Luc Dugelay and Stéphane RocheChapter 6: A survey of current watermarking techniques. in Information hiding techniques for steganography and digital watermarking. Stefan Katzenbeisser and Fabien A. P. Petitcolas (eds.). Artech House Books, 1999. ISBN 1-58053-035-4 []

[Raman 1998]  R. Raman. Random Sampling Techniques in Parallel Computation. Proceedings of the Third Workshop on
Randomized Parallel Computing
. IPDPS/SPDP Workshops 1998, pp.351–360. [PDF]

[Schneier 1996]  B. Schneier.  Applied Cryptography second edition. Wiley, 1996. ISBN 0471128457 []