Preface to the Special issue on the Vapnik-Chervonenkis dimension

The Vapnik-Chervonenkis(VC) is a combinatorial parameter of a class of binary functions or set system which has been shown to characterise the expressiveness of the system or class and in addition the learnability of the class from examples. The learnability follows from the fact that finite VC dimension implies an exponential bound on the probability of uniform relative deviation. The framework has also been formalised as the theory of e-nets for range spaces in computational geometry, where the size of the net is used to characterise the complexity of a number of geometric problems. The concept also plays an important role in the study of logic, where it is seen as a tool to characterise the expressability of a function class. Angus MacIntyre, Mark Jerrum and John Shawe-Taylor organised a Workshop on the Vapnik-Chervonenkis dimension at the International Centre for Mathematical Sciences in Edinburgh, Scotland which took place during the week of 9thhl3th September 1996. The meeting received support from the UK funding body, the Engineering and Physical Sciences Research Council through a grant held by Mark Jerrum as well as from the European Commission through the ESPRIT Working Group, NeuroCOLT, coordinated by John Shawe-Taylor.