William Gasarch
William Ian Gasarch | |
|---|---|
 Professor Bill Gasarch at UMD | |
| Born | 1959 (age 64–65) |
| Nationality | American |
| Alma mater | Stony Brook University Harvard University |
| Known for | Computational complexity theory Computability theory Computational learning theory Ramsey theory |
| 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 (/ɡəˈsɑːrʃ/ gə-SARSH;[1] born 1959[2]) 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.
Gasarch is a frequent mentor of high school student research projects; one of these, with Jacob Lurie, won the 1996 Westinghouse Science Talent Search for Lurie.[3] 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
[edit]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.[4] 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.[5]
Work
[edit]Gasarch co-founded (with Richard Beigel) the field of Bounded Queries in Recursion Theory[6] 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.[7] He has published books such as Problems with a Point,[8] 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.[9] He also co-founded the subfield of recursion-theoretic inductive inference named Learning via Queries[10] with Carl Smith. More recently he has been more involved with combinatorics, notably Ramsey Theory.[11][12][13] He has written three surveys of what theorists think of the P vs NP problem: in 2002, 2012, and 2019.[14][15][16] In 2020 he wrote Mathematical Muffin Morsels: Nobody Wants a Small Piece with Erik Metz, Jacob Prinz, and Daniel Smolyak. [17]
Blog
[edit]Lance Fortnow began writing a blog on theoretical computer science with an emphasis on complexity theory in 2002.[18] Gasarch was a frequent guest blogger until 2007 when he became an official co-blogger.
References
[edit]- ^ "Rectangle Free Colorings – William Gasarch". YouTube. May 8, 2017. Retrieved 12 October 2022.
- ^ "Still Typecasting from Dagstuhl". Computational Complexity Weblog. Lance Fortnow and William Gasarch. Retrieved 27 September 2018.
- ^ Conway, John H.; Jackson, Allyn (July 1996). "Budding Mathematician Wins Westinghouse Competition" (PDF). Notices of the American Mathematical Society. Retrieved 2016-09-26.
- ^ William Gasarch at the Mathematics Genealogy Project
- ^ Gasarch, William (March 16, 2023). "Curriculum vitae" (PDF). U. Maryland Computer Science. Retrieved 2024-02-14.
- ^ 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
- ^ https://www.worldscientific.com/worldscibooks/10.1142/11261 Problems with a Point Exploring Math and Computer Science, 2019
- ^ https://www.worldscientific.com/doi/abs/10.1142/9789813279735_0014 Chapter 14: Is This Problem Too Hard for a High School Math Competition?, 2019
- ^ http://www.cs.umd.edu/~gasarch/papers/lvqsur.pdf A Survey of Inductive Inference with an Emphasis on Queries, Gasarch and Smith, 1997
- ^ Gasarch, William; Haeupler, Bernhard (2011). "Lower Bounds on the van der Waerden Numbers: Randomized- and Deterministic-Constructive". Electronic Journal of Combinatorics. 18 (64). arXiv:1005.3749. doi:10.37236/551. S2CID 534179.
- ^ Gasarch, William; Haeupler, Bernhard (2010). "Rectangle Free Coloring of Grids". arXiv:1005.3750 [math.CO].
- ^ Gasarch, William; Haeupler, Bernhard (2011). "Proving programs terminate using well orderings, Ramsey Theory, and Matrices". arXiv:1108.3347 [math.CO].
- ^ Hemaspaandra, Lane A. (2002-06-01). "SIGACT news complexity theory column 36". ACM SIGACT News. 33 (2): 34–47. doi:10.1145/564585.564599. ISSN 0163-5700. S2CID 36828694.
- ^ Hemaspaandra, Lane A. (2012-06-11). "SIGACT news complexity theory column 74". ACM SIGACT News. 43 (2): 51–52. doi:10.1145/2261417.2261433. ISSN 0163-5700. S2CID 52847337.
- ^ Gasarch, William I. (2019-03-13). "Guest Column: The Third P=?NP Poll". ACM SIGACT News. 50 (1): 38–59. doi:10.1145/3319627.3319636. ISSN 0163-5700. S2CID 83458626.
- ^ Gasarch, William; Metz, Erik; Prinz, Jacob; Smolyak, Daniel (28 May 2020). Mathematical Muffin Morsels: Nobody Wants A Small Piece. World Scientific. ISBN 978-981-12-1519-3.
- ^ http://blog.computationalcomplexity.org/ Computational Complexity Weblog
