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.

Samuel Buss
Samuel Buss à Oberwolfach en 2005
Biographie
Naissance
Nationalité
Formation
Activité
Autres informations
A travaillé pour
Dir. 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
  1. « A Limit of First Order Logic « Gödel's Lost Letter and P=NP » », Rjlipton.wordpress.com, (consulté le )
  2. « Bounded Arithmetic - Revision of 1985 Ph.D. Thesis ».
  3. « Publications and Other Research ».

Liens externes
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.