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

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 ...

computational learning theory In computer science, computational learning theory (or just learning theory) is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms. Overview Theoretical results in machine learning m ...

, and

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask ...

. He is currently a professor at the

University of Maryland The University of Maryland, College Park (University of Maryland, UMD, or simply Maryland) is a public land-grant research university in College Park, Maryland. Founded in 1856, UMD is the flagship institution of the University System of M ...

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 Jacob Alexander Lurie (born December 7, 1977) is an American mathematician who is a professor at the Institute for Advanced Study. Lurie is a 2014 MacArthur Fellow. Life When he was a student in the Science, Mathematics, and Computer Science ...

. He has co-blogged on computational complexity with Lance Fortnow 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 University, Harvard in 1985, advised by Harry R. Lewis. 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 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 Herbert Smith, 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 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