“When mathematics and computer science come together, great stuff happens,” says SFI Professor Cristopher Moore. He and SFI Omidyar Fellow Josh Grochow are creating a test tube for such a combination during a working group at SFI this week, “Algebra, Geometry, Pseudorandomness, and Complexity.”
So far, computer science has relied mostly on relatively simple mathematics based in counting, such as graph theory and combinatorics. Recently, though, more abstract forms of math – group theory, algebraic geometry, and Fourier analysis, for example – have become important tools.
But Moore and Grochow believe computer scientists have barely scratched the surface of what higher math has to offer their field.
One example is in imitating randomness. Many computer science techniques use randomness to increase efficiency. An everyday use is how the Nielsen Ratings count television viewers. It would be difficult and time-consuming to track every viewer, so Nielsen randomly selects a smaller number of families, tracks their habits, and then extrapolates the results to everyone.
In a computer, though, everything is deterministic, so truly random numbers can’t be found. Instead, computer scientists settle for “pseudorandom numbers,” which are generated by some deterministic method so they’re not truly random at all and hence have subtle patterns. But if those patterns aren’t relevant for the task at hand, they can work as well as, or better than, truly random ones.
Because math is ultimately the study of patterns, it can be useful in generating pseudorandom numbers whose patterns are unproblematic for a particular task.
The invitation-only working group brings together an intimate group of researchers building bridges along this frontier. Topics range from basic pedagogy on algebraic geometry to participants’ current research.
More about the working group here.
“I am of the personal belief that to resolve the big questions in computational complexity theory,” Grochow says, “we are going to need some of these higher mathematical tools, and even some that haven’t been invented yet.”