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
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
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.. Buss est également auteur/éditeur de plusieurs livres en logique mathématique et en informatique..
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)
. . . .
Notes et références
Liens externes
Page d'accueil de Samuel R. Buss
Catégorie:Professeur à l'université de Californie à San Diego Catégorie:Étudiant de l'université de Princeton Catégorie:Étudiant de l'université Emory Catégorie:Personnalité américaine de l'informatique Catégorie:Gödel Lecturer