Biography: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.
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 book review editor for ACM SIGACT NEWS from 1997 to 2015.
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.[3] 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[4] 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.[5] He has published books such as Problems with a Point,[6] 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.[7] He also co-founded the subfield of recursion-theoretic inductive inference named Learning via Queries[8] with Carl Smith. More recently he has been more involved with combinatorics, notably Ramsey Theory.[9][10][11] He has written three surveys of what theorists think of the P vs NP problem: in 2002, 2012, and 2019.[12][13][14] In 2020 he wrote Mathematical Muffin Morsels: Nobody Wants a Small Piece with Erik Metz, Jacob Prinz, and Daniel Smolyak. [15]
Blog
Lance Fortnow began writing a blog on theoretical computer science with an emphasis on complexity theory in 2002.[16] Gasarch was a frequent guest blogger until 2007 when he became an official co-blogger.
References
- ↑ "Rectangle Free Colorings – William Gasarch". YouTube. May 8, 2017. https://www.youtube.com/watch?v=TXJ6fYF9em8. Retrieved 12 October 2022.
- ↑ "Still Typecasting from Dagstuhl". Lance Fortnow and William Gasarch. https://blog.computationalcomplexity.org/2018/09/still-typecasting-from-dagstuhl.html. Retrieved 27 September 2018.
- ↑ 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
- ↑ 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). doi:10.37236/551.
- ↑ 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. https://doi.org/10.1145/564585.564599.
- ↑ 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. https://doi.org/10.1145/2261417.2261433.
- ↑ 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. https://doi.org/10.1145/3319627.3319636.
- ↑ Gasarch, William; Metz, Erik; Prinz, Jacob; Smolyak, Daniel (28 May 2020) (in en). Mathematical Muffin Morsels: Nobody Wants A Small Piece. World Scientific. ISBN 978-981-12-1519-3. https://books.google.com/books?id=pdrrDwAAQBAJ&dq=Mathematical+Muffin+Morsels%3A+Nobody+Wants+a+Small+Piece&pg=PR5.
- ↑ http://blog.computationalcomplexity.org/ Computational Complexity Weblog
External links
 |  |
