In close collaboration with Seoul National University's Structural Complexity Laboratory


This is an old revision of the document!

Structured Complexity Group Aims

The Structured Complexity Group aims to develop, extend and apply automated methods for learning good solutions to problems, where the answers are expected to be complex structures.

Real-World problems can be divided into three main kinds

  • Problems where a good solution is determined both by the values involved, and their relationship - sin(log(x)) is different from log(sin(x)) - and we don't know how complex a solution should be (but still we would like a simple solution if possible)

We are mainly interested in the third kind - problems where the likely answers are structurally complex. We work with stochastic methods for solving such problems (Genetic Programming and similar). These problems are generally very tough - there are very few methods which can tackle them.

We are interested especially in

  • How to represent solutions to problems
    • We mainly work with different kinds of grammar representation
  • How to use any knowledge we may have to simplify the problems
    • This is one motivation for using grammars
  • How to automatically break down the problems into simpler problems where possible
  • How to find simple solutions where possible, without damaging the ability to find complex solutions when necessary
  • How to find structured solutions when complexity is necessary, so that we can handle the complexity
  • How to understand the behaviour of current algorithms better
  • How to find general solutions to families of problems, rather than just single solutions to single problems

Our work is particularly inspired by the ability of natural systems to cope with unbounded complexity (the real world), and to generate systems and solutions with highly structured complexity (our DNA is highly structured, with analogues to sub-programs and parameter passing).