William Gasarch and Mohammad Hajiaghayi Co-Author Book on Algorithmic Limits

University of Maryland Department of Computer Science faculty members William Gasarch, a professor of computer science, and Mohammad Hajiaghayi, the Jack and Rita G. Minker Professor of Computer Science, have co-authored a forthcoming book examining how computer scientists determine how difficult problems are to solve and whether faster solutions are possible. Computational Intractability: A Guide to Algorithmic Lower Bounds, co-authored with Massachusetts Institute of Technology Professor Erik Demaine, is scheduled for publication on Oct. 13 by MIT Press. 

The book focuses on algorithmic lower bounds, which researchers use to understand the limits of how efficiently a computational problem can be solved. Rather than focusing only on finding faster algorithms, the book examines how researchers can determine when certain limits cannot be overcome.

The project grew out of conversations between Hajiaghayi and Demaine in 2013 about how computational complexity was taught. They saw an opportunity to approach the subject from the perspective of researchers who design and analyze algorithms.

“We felt there was not a class that taught complexity to students from the perspective of people working and thinking on algorithms,” Hajiaghayi said.

That discussion led them to develop related graduate courses at UMD and MIT in fall 2014. The courses examined the limits of solving a variety of computational problems and eventually produced lecture notes and other materials that became the book's foundation.

Hajiaghayi and Demaine later invited Gasarch, whose research includes computational complexity theory, to join the project.

Hajiaghayi said the courses examined lower bounds across different types of algorithms, providing the framework that later became the book's basis.

“We felt a book in this area would be unique, and we made it happen,” Hajiaghayi said.

For Gasarch, the book centers on a fundamental question in computational complexity: How difficult is a given problem to solve?

“Every chapter classifies a set of problems in terms of how hard they are,” he said.

The book covers several areas of computational complexity, including the limits of parallel computing and NP-completeness, while emphasizing specific problems and the methods researchers use to analyze them.

Through those examples, the authors aim to give readers a broader understanding of not only how algorithms solve problems, but also how computer scientists determine the limits of what those algorithms can do.

—Story by Samuel Malede Zewdu, CS Communications