Samuel R. Buss
Pour les articles homonymes, voir Buss.
| Naissance |
ou |
|---|---|
| Surnom |
Sam |
| Nationalité | |
| Formation | |
| Activités |
| A travaillé pour | |
|---|---|
| Directeur de thèse |
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.
Biographie[modifier | modifier le code]
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[modifier | modifier le code]
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)[modifier | modifier le code]
- 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[modifier | modifier le code]
- (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[modifier | modifier le code]
- Ressources relatives à la recherche :
