Samuel R. (Sam) Buss, born on August 6, 1957, is an American computer scientist and mathematician. He has made important contributions to areas such as the study of reasoning and problem-solving using math, how difficult problems are to solve using computers, and how complicated it is to prove mathematical statements. He is currently a professor at the University of California, San Diego, in the Department of Computer Science and the Department of Mathematics.

Biography

Buss earned his bachelor's degree in 1979 from Emory University. He later received his master's degree and Ph.D. from Princeton University in 1983 and 1985, respectively. In 1986, he began working as a Lecturer in the mathematics department at the University of California, Berkeley, and remained there until 1988. In 1988, he joined the faculty of the Computer Science and Mathematics Departments at the University of California, San Diego, as an assistant professor. He was promoted to Professor in 1993. In 2019, Buss delivered the Gödel Lecture titled Totality, provability and feasibility.

Research

Buss is considered one of the early pioneers of bounded arithmetic and proof complexity.

During his PhD, Buss studied bounded arithmetic. He completed his PhD in 1985. In his thesis, he introduced bounded arithmetic and provided a clear explanation of how polynomial time computation works. His thesis is a key reference in the field of bounded arithmetic. He has also written or edited several books in mathematical logic and computer science.

In 1983, Buss proved that the Boolean Formula Evaluation problem belongs to ALogTime, an important discovery in complexity theory.

His main research areas include mathematical logic, complexity theory, and proof complexity. He has also contributed to other areas, such as bounded arithmetic, bounded reverse mathematics, and lower bounds in propositional proof systems.