1/27/2023 Aaron Seidlitz, Illinois CS
In the final year of his Ph.D. program at Illinois CS, Robert Andrews used the basis of one published paper with advisor Michael A. Forbes to build his own breakthrough and award-winning paper in theoretical computation.
Written by Aaron Seidlitz, Illinois CS
While fostering an interest in mathematics and computation for most of his life thus far, Illinois Computer Science Ph.D. student Robert Andrews faced moments of doubt that, he said, helped turn him into the researcher he is today.
Over time, managing any doubt helped him hone his focus on theoretical computation, a progression that led to several rewarding moments.
Perhaps none are more meaningful to Andrews than a pair of recently published papers – the second of which earned a Best Student Paper Award this past fall at the 63rd IEEE Symposium on Foundations of Computer Science (FOCS).
Andrews is the single author for this paper, entitled “On Matrix Multiplication and Polynomial Identity Testing.”
“Seeing the reaction to this result is reaffirming in two different ways,” Andrews said. “First, I thought that the results and techniques we used in both the first paper and this one were strong and had some merit to them. It was nice to have that confirmed through the research community’s response to our work.
“Second, when a conference like FOCS sees and recognizes the value in your work, then it is personally very reassuring.”
After earning both his bachelor’s degree at Illinois CS, he focused further on complexity theory – a Theory and Algorithms subfield that paired well with his Ph.D. advisor, professor Michael A. Forbes. Now having worked together for years, Andrews considers Forbes “absolutely a world leader in complexity theory.”
Meanwhile, Forbes credits his pupil with building off their earlier work together, to form something that was “more easily appreciated and understood.”
“I was really impressed by Robert's ability to digest the algebraic combinatorics that our work built on. It isn't material standard to our areas of expertise, but he managed to distill the literature into a form that was useable for our purposes,” Forbes said.
The award-winning paper derived from an earlier paper that he and Forbes shared credit on – “Ideals, Determinants, and Straightening: Providing and Using Lower Bounds for Polynomial Ideals.”
The student said this paper conducted more “heavy hitting” mathematical computation stemming from a problem that Forbes wanted Andrews to address.
“Michael is so good at identifying solvable problems that he wants us to focus on. He’s encouraging but allows us the space to conduct our own work,” Andrews said. “This paper provided a nice tool to remove randomness from certain kinds of computation. This gets back to one of these fundamental questions about computation, which is the power of randomness.
“We weren’t the first to remove the use of randomness from the problem we looked at, but we did get a slightly stronger result than what was achieved by prior work.”
The next paper, which won the Best Student Paper Award, built off these notions to solve another problem.
“This result addresses two problems we care a lot about in theoretical computer science,” Andrews said. “So, one problem is multiplying matrices, and the reason that people want to multiply matrices quickly is because it's very useful in all kinds of linear algebra. And you're going to see linear algebra take place in numerical and scientific computation.
“Now, there's a second problem, called polynomial identity testing. Given two representations of supposedly the same polynomial, we want to check if these polynomials are actually the same. There's a very fast algorithm that uses randomness.”
Building off the momentum of these two papers and the Best Student Paper Award, Andrews is now moving toward a postdoc position upon completion of his Ph.D. work this spring.
He’s gained confidence from the acceptance of his research community, and he feels energized for his next steps. The confidence that once wavered has now been bolstered.
“From the time I was a kid, I had an interest in mathematics. I then learned to program through Northwestern University, which offered an introductory class for junior high and high school students,” Andrews said. “It was so nice when I won this award, because it ties back to why I’m even interested in this field. I was at home visiting my mom when I found out about the award. I was standing right next to her and asked her to stop everything she was doing to look at the email.
“That kind of moment is incredible, and she was over-the-moon excited. That’s also solidified the confidence I have in myself to know that I can continue doing this.”