Harry Mairson
Encyclopedia
Harry George Mairson is a theoretical computer scientist and Professor of Computer Science
in the Volen National Center for Complex Systems at Brandeis University
in Waltham, Massachusetts
. His research is in the fields of logic in computer science, lambda calculus
and functional programming
, type theory
and constructive mathematics, computational complexity theory
, and algorithmics.
Mairson received a B.A. in Mathematics
from Yale University
in 1978 and a Ph.D. in Computer Science
from Stanford University
in 1984 under the supervision of Jeffrey Ullman
. His Ph.D. thesis, The Program Complexity of Searching a Table, won the Machtey Award
at the 1983 IEEE Symposium on Foundations of Computer Science
(FOCS). Mairson was a Postdoctoral researcher at INRIA Rocqencourt from 1984 to 1985, at Stanford University
in 1985, and at the University of Oxford
in 1986. He held a Visiting Professor position from 1999 to 2001 at Boston University
. From 2005 to 2007, Mairson has served as the Chair of the Faculty Senate at Brandeis. He is currently an Associate Editor of the journal Logical Methods in Computer Science
and Information and Computation
, and sits on the editorial board of Higher-Order and Symbolic Computation
.
Mairson's contributions to the theory of programming languages include proving that type inference
for the ML programming language, so-called Hindley–Milner type inference, is complete for exponential time and that parallel beta reduction is non-elementary
.
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...
in the Volen National Center for Complex Systems at Brandeis University
Brandeis University
Brandeis University is an American private research university with a liberal arts focus. It is located in the southwestern corner of Waltham, Massachusetts, nine miles west of Boston. The University has an enrollment of approximately 3,200 undergraduate and 2,100 graduate students. In 2011, it...
in Waltham, Massachusetts
Waltham, Massachusetts
Waltham is a city in Middlesex County, Massachusetts, United States, was an early center for the labor movement, and major contributor to the American Industrial Revolution. The original home of the Boston Manufacturing Company, the city was a prototype for 19th century industrial city planning,...
. His research is in the fields of logic in computer science, lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
and functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
and constructive mathematics, computational 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 algorithmics.
Mairson received a B.A. in Mathematics
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...
from Yale University
Yale University
Yale University is a private, Ivy League university located in New Haven, Connecticut, United States. Founded in 1701 in the Colony of Connecticut, the university is the third-oldest institution of higher education in the United States...
in 1978 and a Ph.D. in Computer Science
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...
from Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
in 1984 under the supervision of Jeffrey Ullman
Jeffrey Ullman
Jeffrey David Ullman is a renowned computer scientist. His textbooks on compilers , theory of computation , data structures, and databases are regarded as standards in their fields.-Early life & Career:Ullman received a Bachelor of Science degree in Engineering...
. His Ph.D. thesis, The Program Complexity of Searching a Table, won the Machtey Award
Machtey Award
The Machtey Awardis awarded at the annual IEEE Symposium on Foundations of Computer Science to that author of the best student paper. A paper qualifies as a student paper if all authors are full-time students at the date of the submission...
at the 1983 IEEE Symposium on Foundations of Computer Science
Symposium on Foundations of Computer Science
FOCS, the Annual IEEE Symposium on Foundations of Computer Science, is an academic conference in the field of theoretical computer science...
(FOCS). Mairson was a Postdoctoral researcher at INRIA Rocqencourt from 1984 to 1985, at Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
in 1985, and at the University of Oxford
University of Oxford
The University of Oxford is a university located in Oxford, United Kingdom. It is the second-oldest surviving university in the world and the oldest in the English-speaking world. Although its exact date of foundation is unclear, there is evidence of teaching as far back as 1096...
in 1986. He held a Visiting Professor position from 1999 to 2001 at Boston University
Boston University
Boston University is a private research university located in Boston, Massachusetts. With more than 4,000 faculty members and more than 31,000 students, Boston University is one of the largest private universities in the United States and one of Boston's largest employers...
. From 2005 to 2007, Mairson has served as the Chair of the Faculty Senate at Brandeis. He is currently an Associate Editor of the journal Logical Methods in Computer Science
Logical Methods in Computer Science
Logical Methods in Computer Science is a peer-reviewed journal in theoretical computer science and applied logic conceived in 2004...
and Information and Computation
Information and Computation
Information and Computation is a computer science journal published by Elsevier . The journal was founded in 1957 under its former name Information and Control. The editor-in-chief is A.R. Meyer...
, and sits on the editorial board of Higher-Order and Symbolic Computation
Higher-Order and Symbolic Computation
Higher-Order and Symbol Computation is a computer science journal published by Springer Science+Business Media. It focusses on programming concepts and abstractions and programming language theory.- Editors :Former editors-in-chief of the journal have been:* Richard P...
.
Mairson's contributions to the theory of programming languages include proving that type inference
Type inference
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....
for the ML programming language, so-called Hindley–Milner type inference, is complete for exponential time and that parallel beta reduction is non-elementary
NONELEMENTARY
In computational complexity theory, the complexity class NONELEMENTARY is the complement of the class ELEMENTARY.Example decidable problems in NONELEMENTARY this class are:* the problem of regular expression equivalence with not...
.