New Assistant Professor Nathan Harms finds best algorithms — or proves limits of computation
Dr. Nathan Harms joins UBC Computer Science to research theoretical computer science
Before Nathan Harms went into the sciences, he was an art school dropout.
“My art professors said my projects were too analytical and not emotional,” he said. “I was doing projects that were based on scientific things that interested me or inspired me. They were emotional to me because I loved science.”
Ultimately, he switched fields — first to physics, where he learned how to code, and then eventually to computer science, where he was fascinated with theory. Art and science can appear to be vastly different fields, but to Dr. Harms, they both involve discovering and creating something new.
“Ever since I was a kid, I remembered asking, ‘Why are things this way?’” he says. “With theoretical computer science, I started to see some satisfying answers. It’s telling you fundamental reasons about why things are the way they are.”
He describes his first time hearing about the halting problem (can we determine whether a computer program will finish running or loop forever?) as “earth-shattering.”
“There’s no systematic way of figuring out whether a process is going to halt or not,” he said. “This really drew me in because we can always imagine that we can write an algorithm to solve something or find a better way to do something. But sometimes, you can prove that there’s a fundamental limit on what you can do with computation — you can’t always find a better algorithm.”
Some of the problems he likes to solve are inspired by the natural sciences. For example, in a recent paper at the Symposium on the Theory of Computing (STOC), Dr. Harms and his co-author found a more efficient algorithm for problems like determining whether there are at least (say) 10,000 different species of fish in the ocean. The algorithm can solve this using a smaller random sample of fish: “it’s a sneaky algorithm — it's not very intuitive!”
After finishing his BSc in computer science at the University of Calgary, he went to the University of Waterloo to do his Master’s degree in computer science, studying halfspace testing. He continued with his PhD in computer science, studying sublinear algorithms. Afterwards, he worked as a postdoctoral fellow at École Polytechnique Fédérale de Lausanne in Switzerland.
Now, as an Assistant Professor in the Department of Computer Science at UBC, Dr. Harms plans to continue researching algorithms that do computing with limited information. Specifically, he focuses on two areas: property testing, where he seeks to determine which decisions can be made more efficiently than using a learning algorithm; and communication complexity, where he seeks to understand when and why randomness can be effective, when two parties are collaborating to solve a problem with the least amount of communication between them.
“Sometimes I find better algorithms for some problems, but the more fun part is proving the limitations,” says Dr. Harms.
While he has chosen computer science as a career path, he often goes back to his roots, dabbling in pen and ink. In fact, many of his intricately detailed drawings make appearances in his research presentations.
Dr. Harms has always had UBC in mind as a place to settle down in since graduate school. He’s looking forward to collaborating with other theory researchers at UBC and being near the ocean and the mountains.
His advice to computer science students would be to ask questions when they don’t know something.
“The goal of school is to learn and understand things, and the only way to do that is by trying to figure things out and asking questions,” he says. “Computer science is a science — it’s a way in which we are trying to understand the natural world and to figure out what’s going on at a fundamental level.”
