Harry George Mairson is a theoretical computer scientist and Professor of

Computer Science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...

in th
Volen National Center for Complex Systems
at

Brandeis University , mottoeng = "Truth even unto its innermost parts" , established = , type = Private research university , accreditation = NECHE , president = Ronald D. Liebowitz , ...

Waltham, Massachusetts Waltham ( ) is a city in Middlesex County, Massachusetts, United States, and was an early center for the labor movement as well as a major contributor to the American Industrial Revolution. The original home of the Boston Manufacturing Company, ...

. His research is in the fields of

logic in computer science Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas: * Theoretical foundations and analysis * Use of computer technology to aid logicians ...

, lambda calculus and

functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...

type theory In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a fou ...

and

constructive mathematics In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, and

algorithmics Algorithmics is the systematic study of the design and analysis of algorithms. It is fundamental and one of the oldest fields of computer science. It includes algorithm design, the art of building a procedure which can solve efficiently a specific ...

. His Ph.D. thesis, ''The Program Complexity of Searching a Table'', won the

Machtey Award The Machtey Award is awarded at the annual IEEE Symposium on Foundations of Computer Science (FOCS) to the author(s) of the best student paper(s). A paper qualifies as a student paper if all authors are full-time students at the date of the submiss ...

at the 1983 IEEE Symposium on Foundations of Computer Science (FOCS).FOCS Best Student Paper Award (Machtey Award)
/ref> Mairson was a Postdoctoral researcher at

INRIA The National Institute for Research in Digital Science and Technology (Inria) () is a French national research institution focusing on computer science and applied mathematics. It was created under the name ''Institut de recherche en informatiq ...

Rocqencourt from 1984 to 1985, at Stanford University in 1985, and at the

University of Oxford , mottoeng = The Lord is my light , established = , endowment = £6.1 billion (including colleges) (2019) , budget = £2.145 billion (2019–20) , chancellor ...

in 1986.National Science Foundation proposal 0702312 He held a Visiting Professor position from 1999 to 2001 at

Boston University Boston University (BU) is a Private university, private research university in Boston, Massachusetts. The university is nonsectarian, but has a historical affiliation with the United Methodist Church. It was founded in 1839 by Methodists with ...

. 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 ''Information and Computation'' is a closed-access computer science journal published by Elsevier (formerly Academic Press). The journal was founded in 1957 under its former name ''Information and Control'' and given its current title in 1987. , ...

'', and sits on the editorial board of ''

Higher-Order and Symbolic Computation ''Higher-Order and Symbolic Computation'' (formerly ''LISP and Symbolic Computation''; print: , online: ) was a computer science journal published by Springer Science+Business Media. It focuses on programming concepts and abstractions and program ...

''. Mairson's contributions to the theory of

programming languages A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...

include proving that

type inference Type inference refers to the automatic detection of the type of an expression in a formal language. These include programming languages and mathematical type systems, but also natural languages in some branches of computer science and linguistic ...

for the

ML programming language ML (Meta Language) is a general-purpose functional programming language. It is known for its use of the polymorphic Hindley–Milner type system, which automatically assigns the types of most expressions without requiring explicit type annot ...

, so-called Hindley–Milner type inference, is complete for

exponential time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

and that parallel

beta reduction Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...

is non-elementary.

Education

Mairson received a B.A. in Mathematics from

Yale University Yale University is a Private university, private research university in New Haven, Connecticut. Established in 1701 as the Collegiate School, it is the List of Colonial Colleges, third-oldest institution of higher education in the United Sta ...

in 1978 and a Ph.D. in

from Stanford University in 1984 under the supervision of

Jeffrey Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the d ...

External links

Harry Mairson at Brandeis University

Brandeis University Faculty Guide: Harry Mairson

The Mathematics Genealogy Project - Harry Mairson

References

{{DEFAULTSORT:Mairson, Harry Year of birth missing (living people) Living people Yale University alumni Stanford University alumni American computer scientists Programming language researchers Brandeis University faculty Theoretical computer scientists