William Gasarch

William Ian Gasarch (born 1959^[1]) is an American computer scientist known for his work in computational complexity theory, computability theory, 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,^{[citation needed]} including Jacob Lurie. He has co-blogged on computational complexity with Lance Fortnow since 2007. He was the book review editor for ACM SIGACT NEWS from 1997-2015 before resigning and turning the job over to Fred Green, a professor of Computer science at Clark University.

Education[]

Gasarch received his doctorate in computer science from Harvard in 1985, advised by Harry R. Lewis. His thesis was titled Recursion-Theoretic Techniques in Complexity Theory and Combinatorics.^[2] 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.^{[citation needed]}

Work[]

Gasarch co-founded (with Richard Beigel) the field of Bounded Queries in Recursion Theory^[3] 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.^[4] He's published books such as Problems with a Point,^[5] 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.^[6] He also co-founded the subfield of recursion-theoretic inductive inference named Learning via Queries^[7] with Carl Smith. More recently he has been more involved with combinatorics, notably Ramsey Theory.^[8][9][10] He has written two surveys of what theorists think of the P vs NP problem.^[11][12]

Blog[]

Lance Fortnow began writing a blog on theoretical computer science with an emphasis on complexity theory in 2002.^[13] Gasarch was a frequent guest blogger until 2007 when he became an official co-blogger.

References[]

External links[]

• Gasarch's Homepage