Samuel R. (Sam) Buss is an American

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus ( ...

and

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

who has made major contributions to the fields of

mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

, complexity theory and

proof complexity In logic and theoretical computer science, and specifically proof theory and computational complexity theory, proof complexity is the field aiming to understand and analyse the computational resources that are required to prove or refute statements ...

. He is currently a

professor Professor (commonly abbreviated as Prof.) is an academic rank at universities and other post-secondary education and research institutions in most countries. Literally, ''professor'' derives from Latin as a "person who professes". Professor ...

at the

University of California, San Diego The University of California, San Diego (UC San Diego or colloquially, UCSD) is a public university, public Land-grant university, land-grant research university in San Diego, California. Established in 1960 near the pre-existing Scripps Insti ...

, Department of Computer Science and Department of Mathematics.

Biography

Buss received his

bachelor's degree A bachelor's degree (from Middle Latin ''baccalaureus'') or baccalaureate (from Modern Latin ''baccalaureatus'') is an undergraduate academic degree awarded by colleges and universities upon completion of a course of study lasting three to six ...

in 1979 from the

Emory University Emory University is a private research university in Atlanta, Georgia. Founded in 1836 as "Emory College" by the Methodist Episcopal Church and named in honor of Methodist bishop John Emory, Emory is the second-oldest private institution of h ...

, and his

master's degree A master's degree (from Latin ) is an academic degree awarded by universities or colleges upon completion of a course of study demonstrating mastery or a high-order overview of a specific field of study or area of professional practice.

and

Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is a ...

from

Princeton University Princeton University is a private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth as the College of New Jersey, Princeton is the fourth-oldest institution of higher education in the United States and one of the n ...

, respectively in 1983 and 1985. He joined the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...

, mathematics department in 1986 as an Lecturer, and stayed there until 1988. Buss joined the faculty of

Computer Science
an
Mathematics
Departments in 1988 as an assistant professor, where he was promoted to Professor in 1993. In 2019, Buss gave the

Gödel Lecture The Gödel Lecture is an honor in mathematical logic given by the Association for Symbolic Logic, associated with an annual lecture at the association's general meeting. The award is named after Kurt Gödel and has been given annually since 1990. ...

titled ''Totality, provability and feasibility.''

Research

Buss is considered one of the forefathers of bounded arithmetic and

. During his PhD, Buss worked in bounded arithmetic. He received his PhD in 1985. He introduced bounded arithmetic in his thesis and gave a nice proof theoretic characterization of polynomial time computation. His thesis is one of the main references in the area of bounded arithmetic. He is also author/editor of several books in mathematical logic and computer science. Buss proved in 1983 that the Boolean Formula Evaluation problem is in ALogTime, a major result in complexity theory. His main research areas are

, complexity theory and

. Other areas which he has contributed to include bounded arithmetic, bounded reverse mathematics, and lower bounds in propositional

proof system In mathematical logic, a proof calculus or a proof system is built to prove statements. Overview A proof system includes the components: * Language: The set ''L'' of formulas admitted by the system, for example, propositional logic or first-order ...

References

External links

Home page of Samuel R. Buss

Bounded arithmetic

{{DEFAULTSORT:Buss, Sam Living people American computer scientists Emory University alumni Princeton University alumni University of California, San Diego faculty Year of birth missing (living people) Gödel Lecturers