Forbes Prepares Two Primary Research Aims Devoted to Algebraic and Geometric Complexity Theory with NSF CAREER Award Funding

Dating back to his undergraduate years of study at Massachusetts Institute of Technology, Illinois CS professor Michael A. Forbes’ affinity for algebra led to a natural interest in algebraic techniques tied to theoretical computer science.

There have been two related lines of inquiry that sustained his interest over the years. Both also serve as inspiration for the NSF CAREER Award Forbes recently earned, which will help fund his research agenda in this area for the next five years with $500,000.

The first aim for his research centers on developing techniques for deciding whether a given algebraic expression simplifies to the zero, or “trivial” expression. This problem, known as polynomial identity testing (PIT), has a simple and efficient randomized solution, but developing a deterministic efficient algorithm is a major challenge.

The other aim builds off this concept and ties to a primary academic interest Forbes found as motivation since his graduate studies.

Many, including Forbes, consider Geometric Complexity Theory (GCT) – introduced by Ketan Mulmuley, of the University of Chicago, and Milind Sohoni, of the Indian School of Business – to be a prominent and ambitious program to address fundamental complexity lower bound questions, such as P versus NP, in computational complexity theory.

“(Mulmuley and Sohoni) had published papers in the late 90s and early 2000s on their ideas, and Mulmuley later had a speaking tour on these ideas in early 2009 that I attended while at MIT,” Forbes said. “The lecture created a fair bit of interest from the community at MIT and elsewhere because it was primarily about limits of algebraic computation. As such, it used mathematical tools such as algebraic geometry and representation theory. 

“Unfortunately, these areas, especially the former, are not areas that computer scientists tend to study, and as such the GCT program often comes across as inaccessible.”

Undeterred, Forbes continued focusing on these efforts.

Currently, he has come to understand that there is opportunity to further develop GCT questions specific to his interests.

“While mathematicians developed their own special cases of GCT questions as a way to gain experience and intuition, comparable work on the computer science side was less well developed.  Further, much of the attention on GCT focused on the representation theory aspects of the program, while the underlying algebraic geometry was comparatively less understood,” Forbes said.

To push both aims of his research agenda forward, Forbes considers the NSF funding a benefit to further connect his graduate students to the work. Specific research assistantships will grant graduate students an opportunity to concentrate their focus on the research – unlike teaching assistantships that split the time between research and classroom instruction.

It will also help Forbes develop a comprehensive travel budget. In addition to conferences, Forbes will use the funding to actively engage this community of researchers from such distant countries as Israel, India, Germany and France.