William Ian Gasarch ( ; born 1959) is an American computer scientist known for his work in computational complexity theory,

computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

, computational learning theory, and Ramsey theory. He is currently a professor at the University of Maryland Department of Computer Science with an affiliate appointment in Mathematics. As of 2015 he has supervised over 40 high school students on research projects, including Jacob Lurie. He has co-blogged on computational complexity with

Lance Fortnow Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology. Biogra ...

since 2007. He was book review editor for ACM SIGACT NEWS from 1997 to 2015.

Education

Gasarch received his doctorate in computer science from

Harvard Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of higher le ...

in 1985, advised by

Harry R. Lewis Lewis has been honored for his "particularly distinguished contributions to undergraduate teaching"; his students have included future entrepreneurs Bill Gates and Mark Zuckerberg, and numerous future faculty members at Harvard and other scho ...

. His thesis was titled ''Recursion-Theoretic Techniques in Complexity Theory and Combinatorics''. He was hired into a tenure track professorial job at the University of Maryland in the Fall of 1985. He was promoted to Associate Professor with Tenure in 1991, and to Full Professor in 1998.

Work

Gasarch co-founded (with Richard Beigel) the field of Bounded Queries in Recursion Theory and has written many papers in the area capped off by a book on the topic co-authored with Georgia Martin, titled ''Bounded Queries in Recursion Theory''. He's published books such as ''Problems with a Point'', a book with a broad view on mathematics and theoretical computer science which he co-authored with

Clyde Kruskal Clyde P. Kruskal (born May 25, 1954)Author biography from is an American computer scientist, working on parallel computing architectures, models, and algorithms. As part of the ultracomputer project, he was one of the inventors of the read–mod ...

and includes works by other professors such as David Eppstein. He also co-founded the subfield of recursion-theoretic inductive inference named ''Learning via Queries'' with Carl Smith. More recently he has been more involved with combinatorics, notably Ramsey Theory. He has written two surveys of what theorists think of the

P vs NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used above ...

problem.

Blog

Lance Fortnow began writing a blog on theoretical computer science with an emphasis on complexity theory in 2002.http://blog.computationalcomplexity.org/ Computational Complexity Weblog Gasarch was a frequent guest blogger until 2007 when he became an official co-blogger.

References

External links

Gasarch's Homepage
{{DEFAULTSORT:Gasarch, William Living people American computer scientists Computability theorists University of Maryland, College Park faculty Harvard University alumni Science bloggers 1959 births