MathFIT Events 1998-99

Below are the summer schools and workshops sponsored by MathFIT during 1998-99. Text is included to give a flavour of the events.

• Phase-transition phenomena in combinatorial problems

  "Phase-transition phenomena in combinatorial search problems have traditionally been studied in evolutionary graph theory, but there has been a considerable growth of interest following the empirical studies of search algorithm costs pioneered by researchers in artifical intelligence. Independently of the algorithmic and combinatorial theories, phase-transition effects have long formed an important part of classical models of physical systems and the rich mathematical study of percolation theory. An informal description of a 'phase-transition effect' is as the behaviour whereby 'small' changes in certain parameters of a system occasion dramatic shifts in some globally observed behaviour of the system, such shifts being marked by a 'sharp threshold' point. A very simple example of this in the change from one material state to a different one as temperature is increased, with the 'threshold' being given by melting/boiling point. In combinatorial graph theory, a 'similar' phenomenon has been observed with respect to random graphs: if graphs with m(n) edges are selected uniformly at random from the set of n-vertex graphs, then for many properties, Q there is a 'threshold function', t(n) such that if m(n)/t(n) is less than 1 then a randomly chosen graph 'almost certainly' has property Q; and if m(n)/t(n) is greater than 1, such a graph 'almost certainly' does not have property Q. Much of the recent interest in phase-transition phenomena stems from empirical studies of search heuristics for NP-complete problems: these provide strong evidence that the combinatorial property of a decision problem having a phase-transition with respect solution: instances 'outside' the threshold region are typically resolved quickly; while the run-time peaks for instances 'close to' the threshold point."

  Contact: Dr Paul Dunne, University of Liverpool
  Date: 25-27 January 1999

• Combinatorics and communications applications

  "Since the late 1940s, and the publication of Shannon's seminal papers, the growth in combinatorial mathematics has been fuelled by a burgeoning range of applications relating to the communication of information. This has been parallelled by the huge growth in Information Technology, which has not only made new types of communications possible, but has also generated much of the enormous volumes of data which is communicated via modern communications networks. The problems naturally arising from communications have generated some of the most exciting combinatorial mathematics over the last 50 years. There are many practical problems arising as a result of the widespread use of modern methods of data transmission which can be addressed through combinatorial mathematics. For instance: detection and correction of errors which arise during transmission of data (these issues lead to the concept of good error correcting codes); confidentiality and authenticity of data (this is addressed by the design of cryptographic algorithms and authentication codes); cross interference between various users on a single channel (which leads to frequency assignment methods and CDMA coding); detection of dishonest users operating in a network (this has motivated, for example, the invention of traitor-tracing schemes); and management and distribution of cryptographic keys (threshold cryptography, secret sharing schemes and public key cryptography arise in this setting)."

  Contact: Dr Steven Galbraith, Royal Holloway University of London
  Date: 14-15 April 1999

• Complexity and exact computation over the real numbers

  "Computations involving real numbers are generally handled by approximation, whether it be fixed precision or arbitrary precision. Over the last 25 years or so, an alternative approach to real computation has been developed, called exact real computation in which results are generated exactly, without approximation. Systems for exact real computation have been built based upon alternative representations of real numbers, especially continued fractions. However, for exact systems to be fully developed there are several remaining areas to be understood and implemented. Traditionally, such systems have focussed on arithmetic. Extending exact computation to differential and integral calculus, and to solutions of differential equations, requires new techniques. A quite different aspect is that of efficiency of exact systems. For example, there is a question whether efficient methods from numerical analysis, such as adaptive methods, can be used to provide a reasonable performance for exact calculus. A great deal of expertise about efficiency of implementation of exact systems has been developed but no systematic understanding of the area has yet emerged. Recently, however, there has been an explosive growth in the study of the complexity of computation involving real numbers. Generalising complexity theory to computations involving real numbers results in many of the standard complexity theory concepts taking on a very different flavour."

  Contact: Professor David Rydeheard, University of Manchester
  Date: 10-12 July 1999

• Combinatorial pattern matching

  "Combinatorial pattern matching addresses issues of searching and matching strings, and more complex patterns such as trees, regular expressions, graphs, point sets, and arrays. The efficiency of algorithms for searching and matching patterns is especially critical for some of the key application areas in computer science. Topics of concentration include data compression, coding with emphasis on error correction for efficient and reliable communication and storage, approximate string and tree matching, pattern-matching in digitised images and compressed data, information retrieval and search engines for the world wide web, data mining for textual and genomic sequences, external memory issues in pattern matching, and combinatorial problems in computational biology, especially within the context of the human genome project. Combinatorial pattern matching is a flourishing area which attracts researchers in computer science, mathematics, electrical engineering, molecular biology, and genetics, with the main driving force coming from theoretical computer science and combinatorics."

  Contact: Dr Cenk Sahinalp, University of Warwick
  Date: 20-21 July 1999

Return to MathFIT Past Events.