NEWS
2000/2001
Issue No 10
2000 SCIENTIFIC PROGRAMME
Workshop on Model Theoretic Algebra and Algebraic
Methods of Computation
4 - 14 September
Organisers:
Felipe Cucker (Hong Kong),
Pascal Koiran (Lyon),
Angus Macintyre (Edinburgh),
Christian Michaux (Mons)
Supported by:
The Engineering and Physical Sciences Research Council
The objective of the Workshop was to bring together several research groups concerned with definability in classical algebraic structures. There are three easily identified groups:
- (i) applied model theorists;
- (ii) the group centred round Blum–Shub – and Smale – concerned with computability on general structures;
- (iii) the Russian school of algorithmic geometry.
The meeting resulted in progress in four particular areas:
1. Geometry
Since Khovanski’s paper in 1980, on the uniform finiteness of number of connected components for semi-Pfaffian sets, there has been intensive activity on related algorithmic and definability issues. On the pure side, the major work is due to Wilkie, in his proofs of model-completeness for real exponentiation and o-minimality of Pfaffian functions. By general model theory this yields deep results on Whitney stratifications. A major challenge is to effectivize the results, because of potential relevance to neural networks, sparse polynomials, etc. During the meeting Vorobjov reported on joint work with the analytic geometer Gabrielov, in which reasonably effective upper bounds are obtained. This should encourage model theorists to take up again the issue of a more explicit decidability proof for real exponentiation.
A quite startling advance was reported by Rojas, concerning connected components of sets defined by trinomials. Here one has been able to get close to optimal bounds, in contrast to the astronomical bounds got by naive use of Hovanski’s method.
In the setting of complex algebraic geometry Chistov explained some basic new algorithms for smooth stratification.
2. VC dimension and learning theory
Several years ago Karpinski and Macintyre had shown the power of a combination of Khovanski’s methods and model theory by getting close to the optimal bounds for the VC-dimension of sigmoidal neural networks. More generally they had begun to link Vapnik’s more recent work to o-mimimality, and related model-theoretic notions, with a view to randomized algorithms in certain real and p-adic geometrical situations. Macintyre had been unaware that the interests of Smale’s group had also turned in this direction. One of the highlights of the meeting was Smale’s account of his project, mainly with Cucker, to bring deep functional analysis to bear on the estimation problems (sample error, approximation error) of a suitably abstract learning theory. It is not at all clear how this approach relates to that via o-minimality and Morse theory. The Workshop certainly accelerated discussion of this basic issue.
3. Database theory
In recent years some highly original work of Baldwin, Benedikt et al. has shown the importance of modern model-theoretic notions for database theory. Benedikt’s lecture on this led to an interaction with Macintyre, concerning p-adic aspects of this. The literature until now deals with real geometrical situations where the relevance of VC-dimensions can be well-estimated. In the p-adic cases, the VC-dimensions are known to be finite, but one does not yet know how to calculate them.
4. Circuit complexity and model theory
Krajicek reported on deep work joint with Scanlon, on model-theoretic Euler characteristics and their connections to the hardcore complexity issues around the Hilbert Nullstellensatz (a favourite theme of the Smale school also).
As it turned out, the most striking presentations all had to do with algorithms and geometry (broadly construed). Any new algorithm is likely to be of use somewhere in engineering, computer science or artificial intelligence. Model theory has already made significant contributions to learning theory, and the new involvement of Smale’s group, with a different perspective, should consolidate the link.
Return to Contents List
Participants:
Basarab, Serban, Romanian Academy of Sciences
Benedikt, Michael, Bell Labs
Blum, Lenore, Carnegie Mellon University
Borovik, Alexandre, UMIST
Bradfield, Julian, University of Edinburgh
Buergisser, Peter, University of Paderborn
Chapuis, Olivier, Université Lyon I
Chistov, Aleksandr L, Russian Academy of Sciences
Cucker, Felipe, City University of Hong Kong
de Naurois, Paulin, Ecole Normale Superieure
de Lyon Dickmann, Max, University Paris VII
Fournier, Hervé, ENS Lyon
Grigorev, Dimitri, Université de Rennes 1
Kalorkoti, Kyriakos, Unviersity of Edinburgh
Karpinski, Marek, Universität Bonn
Koiran, Pascal, ENS Lyon
Krajicek, Jan, Academy of Sciences at Prague
Langley, Simon, University of the West of England
MacIntyre, Angus, University of Edinburgh
Makowsky, Johann, Technion - Israel Institute of Technology
Marker, David, University of Illinois at Chicago
Meer, Klaus, Odense University
Michaux, Christian, Université de Mons-Hainaut
Petrovich, Alejandro, University of Buenos Aries
Poizat, Bruno, Université Claude Bernard (Lyon 1)
Portier, Natacha, ENS Lyon
Prunescu, Mihai, Universität Greifswald
Richardson, Dan, University of Bath
Rojas, J Maurice, City University of Hong Kong
Shackell, John, University of Kent at Canterbury
Smale, Stephen, City University of Hong Kong
Stevens, Perdita, University of Edinburgh
Toffalori, Carlo, University of Camerino
Tucker, J V, University of Wales, Swansea
Vorobjov, Nicolai, University of Bath
Xirotiri, Olga, University of Crete
Return to Contents List