Solving complex problems from A to Z

Back in the 1970s, when programming pioneers were still figuring out how to use their oversized computers, theorists developed a system for categorizing computer science problems based on how fast they could be solved. 

This “complexity theory” took the form of a kind of alphabet soup: problems that could be solved by a reasonably fast program—like multiplication, or the alphabetizing of a list of names—were denoted by the letter “P”. Further up the complexity ladder was “NP”—problems that might not be solvable, but could be verified in a reasonable amount of time when a potential solution was provided.

As complexity theory advanced, it became clear that many NP challenges were actually variations on the same problem; this was good news, because solving one would clear the path for solving all of the others. But bad news as well, because this subset of similar NP problems—categorized under the new moniker “NP complete”—was still unsolvable by known programming methods. And this was just the tip of the complexity iceberg. Soon, a new set of challenges was identified, distinguished by being “at least as hard as” NP complete problems. This new category was named “NP hard.”

This is where the work of Dr. Amir Abboud comes in. Building on the theory that underlies NP hardness—the  property shared by a subset of those problems that cannot necessarily be solved by computers—
Dr. Abboud set about defining “hardness” as it applies to P: those problems that can be solved with a reasonable amount of efficiency.

Located at the intersection of complexity theory and algorithm science, Dr. Abboud’s research uses a rigorous, theory-based approach to examine and improve the way algorithm designers tackle real-life computational problems. 
“During my doctoral work, I was surprised to realize that this valuable and obvious agenda had been largely overlooked by the theory community,” says Dr. Abboud. “Since then, things have changed—today, ‘hardness in P’ is being studied by dozens of research groups around the world.”

While there is still much work to do, he says, this theoretical approach is important enough—and simple enough—to be incorporated into mainstream computer science education for undergraduates. 
“As computer scientists, finding the best path forward is sometimes a process of elimination,” he says. “The overall goal of my research is to help computer science move forward by providing hard evidence about the problems that can—and cannot—be solved.”

Bio

A native of Haifa, Dr. Abboud was just 12 years old when he began studying mathematics at The Open University of Israel, and 15 when he entered the University of Haifa, where he earned his BSc, summa cum laude, in computer science in 2010. He completed his MSc (2012) summa cum laude at the Technion—Israel Institute of Technology and his PhD (2018) at Stanford University, both in computer science as well. Since finishing his doctorate, Dr. Abboud has been employed by IBM Research’s Almaden Lab in San Jose, California, where he has been examining the computational complexity of fundamental computer science problems.

Dr. Abboud has earned awards for excellence throughout his academic career and has held visiting researcher appointments at MIT, the Simons Institute at UC Berkeley, and the University of Haifa. An invited speaker at professional conferences around the world, Dr. Abboud serves on the program committee of various gatherings, including the Symposium on Foundations of Computer Science, the International Colloquium on Automata, Languages and Programming, and the Symposium on Discrete Algorithms—conferences at which his submissions became the top-cited papers.

He is fluent in Arabic, Hebrew, and English. He is an avid soccer fan and a former member of Maccabi Haifa’s junior team.