Venkatesan Guruswami, a campus professor in electrical engineering and computer science, or EECS, won a 2023 Guggenheim Fellowship for his research proposal on mathematical computer science.
The Guggenheim Fellowship is awarded by the Guggenheim Memorial Foundation to celebrate individuals who demonstrate “exceptional creative ability” in the arts and sciences.
The foundation claims to accept approximately 175 out of 3000 applications each year, according to its website.
“The fellowship is based on a research proposal, which is in the scope of roughly a year,” Guruswami said. “This is a unique fellowship because it’s not just for science and engineering. In fact, if you look at their awards, most of them are for work in the creative arts and literature, humanities, social sciences, et cetera.”
Titled “Mathematical Structure and Efficient Algorithms: The Polymorphic Gateway,” Guruswami’s proposal tackles why some computational problems are hard and others are easy.
While it does dive into mathematical details, the proposal provides a general overview of computational problems.
“Even if you don’t know computer science, you might be familiar with the fact that some problems are easy to solve. Some are hard to solve. Is there a theory explaining this? How far can such a theory go?” Guruswami said. “I think this is perhaps appealing to a wide range of scholars who are intellectually curious.”
Guruswami stated in the proposal that while a unifying theory explaining tractability, or whether a given problem can be solved, may not exist in general, it does exist in the realm of constraint satisfaction problems, or CSPs.
An example of a CSP would be a system of linear equations with a solution satisfying all the equations simultaneously, according to Guruswami. He added that the existence of an efficient algorithm is in the case of a CSP determined by the existence of a nontrivial symmetry, or a polymorphism.
Guruswami completed his undergraduate education at Indian Institute of Technology Madras and obtained a doctoral degree at Massachusetts Institute of Technology, both in computer science.
Last year, Guruswami moved to the EECS department at UC Berkeley from Carnegie Mellon University, where he was a computer science professor for more than 13 years.
Guruswami is no stranger to UC Berkeley, having been a Miller Research Fellow on campus following his doctoral degree. He is also currently a senior scientist at the Simons Institute for the Theory of Computing, a leading theoretical computing center located on campus.
Guruswami said that one of his major research thrusts concerns error correcting codes: a study on how to safeguard the integrity of data from noise in communication.
“The field is very broad, because there are many different kinds of noise models you might study, depending on your specific application,” Guruswami said. “The internet, for example, (is a model in which) packets will get dropped.”
A precise mathematical model is used to capture the kind of errors of interest, and there is a rich ensuing theory of why things “seem right.” He claimed that the mathematical fields involved include algebra, graph theory, combinatorics and probabilistic reasoning.
Guruswami added that error correcting codes have important applications in reliably storing and retrieving data from the cloud, which is a ubiquitous modern-day need.
In his proposal, Guruswami said he will continue his journey to grasp the interplay between mathematical structure and the tractability or intractability of computational problems.
“I’m very grateful for being awarded this fellowship. It’s a privilege to work with the amazingly talented students at Berkeley on these challenges,” Guruswami said in an email. “And I’m really excited to see what insights on computation will emerge from our work.”
