Samuel R. Buss
Samuel R. (Sam) Buss est un informaticien et mathématicien américain qui travaille en logique mathématique, théorie de la complexité et en complexité des preuves. Il est, en 2022, professeur à l'université de Californie à San Diego.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activités |
| A travaillé pour | |
|---|---|
| Directeur de thèse |
Biographie
Buss obtient son baccalauréat en 1979 à l'université Emory, sa maîtrise et son doctorat à l'université de Princeton, respectivement en 1983 et 1985. Il rejoint le département de mathématiques de l'université de Californie à Berkeley en 1986 en tant que lecturer jusqu'en 1988. Buss devient professeur assistant à la faculté d' 'informatique et de mathématiques de l'université de Californie à San Diego en 1988 ; il y est promu professeur en 1993.
En 2019, Buss est Gödel Lecturer, avec une conférence intitulée Totalité, prouvabilité et faisabilité.
Recherche
Buss est considéré comme l'un des pères de l'arithmétique bornée et de la complexité des preuves[1]
Buss a étudié l'arithmétique bornée c'est-à-dire des versions atténuées de l'arithmétique de Peano, dans lesquelles les quantificateurs sont par exemple limités. Elle a été introduite en 1971 par Rohit Jivanlal Parikh. Buss s'y est intéressé en 1985 dans le cadre de sa thèse de doctorat, la thèse a également été publiée sous forme de livre et constitue un ouvrage de référence dans ce domaine. Sa thèse est l'une des principales références dans le domaine de l'arithmétique bornée[2]. Buss est également auteur/éditeur de plusieurs livres en logique mathématique et en informatique[3].
Buss a prouvé en 1983 que le problème d'évaluation de formules booléennes est dans la classe de complexité ALogTime (alternating log time), alors un résultat majeur en théorie de la complexité. Buss a également donné des bornes inférieures dans les systèmes de preuve propositionnelle.
Publications (sélection)
- avec Dmitry Itsykson, Alexander Knop, Artur Riazanov et Dmitry Sokolov, « Lower Bounds on OBDD Proofs with Several Orders », ACM Transactions on Computational Logic, vol. 22, no 4, , article no 26 (30 pages) (DOI 10.1145/3468855).
- « The Boolean formula value problem is in ALOGTIME », Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), , p. 123-131 (lire en ligne).
- Bounded Arithmetic : Revision of 1985 Ph.D. Thesis, Naples, Bibliopolis, (lire en ligne).
- Samuel R. Buss (éditeur), Handbook of Proof Theory, Amsterdam, Elsevier, , X + 811 (lire en ligne).
Notes et références
- (en)/(de) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Samuel R. Buss » (voir la liste des auteurs) et en allemand « Samuel R. Buss » (voir la liste des auteurs).
- « A Limit of First Order Logic « Gödel's Lost Letter and P=NP » », Rjlipton.wordpress.com, (consulté le )
- « Bounded Arithmetic - Revision of 1985 Ph.D. Thesis ».
- « Publications and Other Research ».
Liens externes
- Ressources relatives à la recherche :