# William Gasarch

William Ian Gasarch | |
---|---|

Nationality | United States |

Alma mater |
Stony Brook University Harvard University |

Scientific career | |

Fields | Computer science |

Institutions | University of Maryland, College Park |

Doctoral advisor | Harry R. Lewis |

Website |
www http://blog.computationalcomplexity.org/ |

**William Ian Gasarch** is a 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, including Jacob Lurie, and over 45 undergraduates. 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.

## Biography[edit]

William 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*.^{[1]}
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[edit]

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

## Blog[edit]

Lance Fortnow began writing a blog on theoretical computer science
with an emphasis on complexity theory in 2003.^{[10]}
William Gasarch
was a frequent guest blogger until 2007 when he became an official co-blogger.
Largely because of the blog Fortnow/Gasarch were named one of the
50 most social-media savvy professors in America.^{[11]}
Their blog is also one of the top 30 computer science and programming blogs.^{[12]}

## Hobbies[edit]

William Gasarch collects novelty songs. He has the largest collection of satires of
Bob Dylan's music.^{[13]}

## References[edit]

**^**William Gasarch at the Mathematics Genealogy Project**^**http://www.cs.umd.edu/~gasarch/papers/gems.pdf Gems in the Field of Bounded Queries by William Gasarch, 2003**^**https://www.springer.com/us/book/9780817639662 Bounded Queries in Recursion Theory (with Georgia Martin), Birkhauser, 1999**^**http://www.cs.umd.edu/~gasarch/papers/lvqsur.pdf A Survey of Inductive Inference with an Emphasis on Queries, Gasarch and Smith, 1997**^**https://arxiv.org/abs/1005.3749 Lower Bounds on the van der Warden Numbers: Randomized and Deterministic-Constructive**^**https://arxiv.org/abs/1005.3750 Rectangle Free Colorings of Grids (with Fenner, Glover, Purewal), 2010**^**https://arxiv.org/abs/1108.3347 Proving programs terminate using well orderings, Ramsey Theory, and Matrices**^**http://www.cs.umd.edu/~gasarch/papers/poll.pdf The P=?NP Poll, William Gasarch, Guest Column in SIGACT NEWS Complexity Theory Column 36, 2002**^**http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf The Second P=?NP Poll, William Gasarch, Guest Column in SIGACT NEWS Complexity THeory Column 74, 2012**^**http://blog.computationalcomplexity.org/ Computational Complexity Weblog**^**http://www.onlinecolleges.net/50-most-social-media-savvy-professors-in-america/ 50 Most Social Media Savvy Professor In America**^**http://www.computersciencedegreehub.com/top-30-computer-science-programming-blogs-2014/ The Top 30 Computer Science and Programming Blogs**^**http://www.cs.umd.edu/~gasarch/dylan/dylan.html Satires of Bob Dylan. Webpage maintained by William Gasarch.