Members of the Allen School’s Theory of Computation group earned two Best Paper Awards at the 53rd annual Symposium on Theory of Computing (STOC 2021) last week for achieving a pair of “firsts” that advanced the state of the art in approximation algorithms and cryptography, respectively. One of the winning papers, co-authored by Allen School Ph.D. student Nathan Klein and professors Anna Karlin and Shayan Oveis Gharan, produced the first improvement on the Traveling Salesperson Problem in more than 40 years. The other, which Allen School professor Rachel Lin co-authored with Aayush Jain, a Ph.D. student at the University of California Los Angeles and intern at NTT Research, and UCLA professor Amit Sahai, answered a decades-old question by providing the first-ever proof of the security of indistinguishability obfuscation based on well-founded assumptions.
One of the core problems underpinning the theory and practice of computer science that extends to multiple other domains, the Traveling Salesperson Problem (TSP) seeks to find the most efficient route over multiple destinations and back to the starting point. Short of finding the optimum, computer scientists have relied on approximation algorithms to chip away at the problem by finding an answer that is, as Klein described in a piece he wrote for The Conversation, “good enough.” As the name suggests, TSP has obvious applications in transportation and logistics. But, Klein explained, a solution will have implications for multiple other domains, from genomics to circuit board design.
“This is important for more than just planning routes,” Klein wrote. “Any of these hard problems can be encoded in the Traveling Salesperson Problem, and vice versa: Solve one and you’ve solved them all.”
Klein and his colleagues may not have completely solved the problem, but they brought the field an important — and hugely symbolic — step closer. Their algorithm, which they revealed to the world last summer, is the first to break the elusive 50% threshold for TSP — meaning the cost of its result will always be less than 50% above the optimum. While their result represents only a marginal improvement over the previous state of the art in real terms, at roughly 49.99999%, the team’s achievement offers a foundation on which they and their fellow researchers can build in future work. And build they most assuredly will; according to Karlin, once a researcher encounters TSP, it is very difficult to set it aside.
“One of my favorite theoretical computer scientists, Christos Papadimitriou, summed it up perfectly,” observed Karlin. “He said, ‘TSP is not a problem. It is an addiction.’”
Her faculty colleague Oveis Gharan knows the feeling well, having spent the past 10 years tackling various elements of TSP. For him, this milestone is another step forward on an open-ended journey — and one he is keen to delve into more deeply now that the dust has settled and the proof has checked out.
“A natural follow-up to our result would be to find a simpler proof with a significantly bigger improvement over the 50%, but to be honest, that is not really what interests me,” said Oveis Gharan. “Often, when someone breaks a long-standing barrier, they develop or employ several new tools or ideas in the process. These typically are not well understood in their full generality, because they are mainly specialized for that specific application. So, what I want to do after such a result is to better understand these new tools and ideas. Why do they work? What other applications can they possibly have? Can we generalize them further? Is there any other open problem that they can help us address? We’re exploring these questions now with regard to some of the tools that we used in this TSP paper.”
Lin’s work with Jain and Sahai on indistinguishability obfuscation (iO) also represents a discovery that was decades in the making. In this case, the researchers proved the security of a potentially powerful cryptographic scheme for protecting computer programs from would-be hackers by making them unintelligible to adversaries while retaining their functionality.
The team’s breakthrough paper demonstrates that provably secure iO is constructed from subexponential hardness of four well-founded assumptions: Symmetric External Diffie-Hellman (SXDH) on pairing groups, Learning with Errors (LWE), Learning Parity with Noise (LPN) over large fields, and a Boolean Pseudo-Random Generator (PRG) that is very simple to compute. All four have a long history of study that is well-rooted in complexity, coding and number theory — enabling Lin and her collaborators to finally put a cryptographic approach that was first described in 1976, and mathematically formalized 20 years ago, on a firm footing. The researchers also devised a simple new method for leveraging LPN over fields and PRG in NC0 — a simple model of computation in which every output bit depends on a constant number of input bits — to build a structured-seed PRG (sPRG). The seed, which comprises both a public and private part, maintains the scheme’s pseudo-randomness in cases where an adversary is able to see the public seed and the sPRG output.
Now that they have verified the security of iO based on well-founded assumptions, Lin and her collaborators are already working to extend their results — and they are eager to see others expand upon them, as well.
“The next step is further pushing the envelope and constructing iO from weaker assumptions,” Lin said when the team announced its results. “At the same time, we shall try to improve the efficiency of the solutions, which at the moment is very far from being practical. These are ambitious goals that will need the joint effort from the entire cryptography community.”
STOC is organized by the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory (ACM SIGACT).
Read Quanta Magazine’s past coverage of the TSP result here and the iO result here.
Congratulations to all!