Samuel Buss
Encyclopedia
Samuel R. Buss is a American computer scientist
and mathematician
who has made major contributions to the fields of mathematical logic
, complexity theory
and proof complexity
. He is currently a Professor
at the University of California, San Diego
, Department of Computer Science and Department of Mathematics.
in 1979 from the Emory University
, and his Master's degree
and Ph.D.
from Princeton University
, respectively in 1983 and 1985. He joined the University of California, Berkeley
, mathematics department in 1986 as an Lecturer, and stayed there until 1988. Buss joined the faculty of University of California, San Diego
, Computer Science and Mathematics Departments in 1988 as an Assistant Professor, where he was promoted to Professor in 1993.
.
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. His is also author/editor of several books in mathematical logic and computer science.
Buss proved in 1983 that Boolean Formula Evaluation problem is in ALogTime, a major result in complexity theory
.
His main research areas are mathematical logic
, complexity theory
and proof complexity
. Other areas which he has contributed to include bounded arithmetic, bounded reverse mathematics, and lower bounds in propositional proof systems.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and mathematician
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
who has made major contributions to the fields of mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and proof complexity
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
. He is currently a Professor
Professor
A professor is a scholarly teacher; the precise meaning of the term varies by country. Literally, professor derives from Latin as a "person who professes" being usually an expert in arts or sciences; a teacher of high rank...
at the University of California, San Diego
University of California, San Diego
The University of California, San Diego, commonly known as UCSD or UC San Diego, is a public research university located in the La Jolla neighborhood of San Diego, California, United States...
, Department of Computer Science and Department of Mathematics.
Biography
Buss received his Bachelor's degreeBachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
in 1979 from the Emory University
Emory University
Emory University is a private research university in metropolitan Atlanta, located in the Druid Hills section of unincorporated DeKalb County, Georgia, United States. The university was founded as Emory College in 1836 in Oxford, Georgia by a small group of Methodists and was named in honor of...
, and his Master's degree
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
and Ph.D.
Doctor of Philosophy
Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...
from Princeton University
Princeton University
Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....
, respectively in 1983 and 1985. He joined the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, mathematics department in 1986 as an Lecturer, and stayed there until 1988. Buss joined the faculty of University of California, San Diego
University of California, San Diego
The University of California, San Diego, commonly known as UCSD or UC San Diego, is a public research university located in the La Jolla neighborhood of San Diego, California, United States...
, Computer Science and Mathematics Departments in 1988 as an Assistant Professor, where he was promoted to Professor in 1993.
Research
Buss is considered one of the forefathers of bounded arithmetic and proof complexityProof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
.
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. His is also author/editor of several books in mathematical logic and computer science.
Buss proved in 1983 that Boolean Formula Evaluation problem is in ALogTime, a major result in complexity theory
Complex systems
Complex systems present problems in mathematical modelling.The equations from which complex system models are developed generally derive from statistical physics, information theory and non-linear dynamics, and represent organized but unpredictable behaviors of systems of nature that are considered...
.
His main research areas are mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and proof complexity
Proof complexity
In computer science, proof complexity is a measure of efficiency of automated theorem proving methods that is based on the size of the proofs they produce. The methods for proving contradiction in propositional logic are the most analyzed...
. Other areas which he has contributed to include bounded arithmetic, bounded reverse mathematics, and lower bounds in propositional proof systems.
Awards and honors
Buss has supervised numerous MSc students, and 5 PhD students have completed their degrees under his supervision.External links
- Home page of Samuel R. Buss
- Samuel R. Buss at DBLPDBLPDBLP is a computer science bibliography website hosted at Universität Trier, in Germany. It was originally a database and logic programming bibliography site, and has existed at least since the 1980s. DBLP listed more than 1.3 million articles on computer science in January 2010...
- The Boolean formula value problem is in ALOGTIME
- Bounded Arithmetic
- Handbook of Proof Theory
- 3D Computer Graphics: A mathematical approach with OpenGL