Miklós Ajtai and Regina Barzilay received IEEE medals for applying unexpected methods to computer science

Retired IBM Research scientist Miklós Ajtai and MIT professor Regina Barzilay each received prestigious medals from the Institute of Electrical and Electronics Engineers (IEEE) this month. They were presented with the awards on April 23 at IEEE’s Vision Innovation Challenges Summit in Tokyo.

Ajtai won the IBM-sponsored John von Neumann Medal “for contributions to establishing lower bounds in computational complexity and founding lattice-based cryptography.” His work formed the theoretical foundation for quantum-safe cryptography. Barzilay was awarded the IBM-sponsored Frances E. Allen Medal “for innovative machine learning algorithms that have led to advances in human language technology and demonstrated impact on the field of medicine.” She is the School of Engineering Distinguished Professor for AI and Health at MIT, and her work involves clinical AI that can detect cancer earlier than conventional methods. Barzilay has also worked closely with IBM Research on several projects over the years.

Ajtai, born in Hungary, worked at IBM Research’s Almaden lab in California from 1984 until his retirement in 2015. His colleagues recognized him as a brilliant mathematician whose theoretical work held surprising practical implications for computer science.

“In my case, learning about branches of mathematics which had no obvious connection with computational problems turned out to be very useful,” he reflected. “The connection between the mathematical and computational problem became clear later, when I needed it.”

Quantum-safe before quantum

One example of this eventual connection is Ajtai’s work on lattice-based algorithms in the first decade or so of his career. Two of Ajtai’s papers from the 1990s helped to establish the foundation that put IBM on the road to where we are today with quantum-safe cryptography.

“Cryptography based on the presumed hardness of lattice problems is currently the basis for much of quantum-safe cryptography,” said Vadim Lyubashevsky, a cryptographer in the security group at IBM Research Europe. “Almost everyone working in the area is working on an offshoot of what Ajtai created almost 30 years ago,” Lyubashevsky said.

One of these papers, from 1998, showed that there are some lattice problems that are NP-hard.¹ The other paper, published in 1996, defined a problem whose random instances were as hard as worst-case instances, which made it a perfect candidate for cryptography.² “This latter problem — the Short Integer Solution (SIS) problem — is at the foundation of today's practical quantum-safe cryptography,” said Lyubashevsky.

“Miki — as some of his close colleagues at Almaden called him — was one of the most groundbreaking theoretical computer scientists to date in the community,” said Chid Apte, chair of the IBM Research Mathematical Sciences Council. That 1996 paper, Apte said, didn’t really take off at the time because the RSA public key encryption standard in place at the time was considered strong and sufficient. But now it’s extremely relevant.

“Unlike RSA encryption which can be broken by quantum computers, lattice-based cryptography cannot be,” Apte said. “In fact, much of the more recent work that was done in our Zurich labs by the quantum-safe crypto team there has been built on top of the theoretical work that Miki did way back in the late 1990s.”

Keeping it simple

The other achievement for which Ajtai has been recognized is the establishment of lower bounds of computational complexity.

“In computational complexity we are interested in the amount of resources, for example, the amount of time and memory, needed for the solutions of various computational problems,” Ajtai said. “A lower bound is a result which shows that in a given computational model a problem cannot be solved by using only a certain amount of resources.”

Proving lower bounds is difficult in general computation, because a lower bound is a statement not only about a specific algorithm but about all possible algorithms in the given model. Ajtai’s contribution was to establish such lower bounds in computational models using methods from various branches of mathematics.³

“This was a very important result,” said Phokion Kolaitis, a principal researcher at IBM Research Almaden. “He published relatively few papers, but every paper was a jewel. It was profound and impactful.”

For decades, this question of complexity was an open problem, said Lior Horesh, principal research scientist at IBM Research. “It’s beautiful when you take something that should be a number theory problem and make the connection to computer science,” said Horesh. “I think that’s remarkable.”

Regina Barzilay is bringing AI to diagnosis

The Frances E. Allen Medal is given each year for “innovative work in computing leading to lasting impact on other aspects of engineering, science, technology, or society.” Barzilay has a strong connection to IBM Research, having had multiple IBMers as her students, not to mention the ongoing collaboration of the MIT-IBM Watson AI Lab.

She first found out she’d received the award when she started receiving congratulatory phone calls before she saw the official word. A spam filter had ensnared the email informing her she’d won the award, which she found humorously ironic given that her early AI work was on natural language processing.

“But of course I was thrilled, and it was really special for me to get an award which is named for the first woman who won the Turing Award,” Barzilay said.

In Barzilay’s case, the award-winning work was on her contributions to healthcare. She developed neural molecular representations that can capture molecular structures in multiple resolutions, as well as algorithms that can manipulate them without overwhelming compute resources. What this means for healthcare is clinical AI to improve screening for deadly diseases, especially in early stages when treatment will be most effective.

Her work has helped accurately detect breast cancer up to five years before it shows up, doubling the detection rate of previous algorithms. It was especially useful during the COVID-19 pandemic, when hospitals needed to prioritize routine screening for patients at higher risk of the disease.

“It’s exciting not just from the intellectual perspective because it gives us access to so many questions we couldn’t address using conventional means, but also because these technologies have direct benefits to patient health,” she said.

Before then, she worked on natural language processing to translate texts from dead languages. But around 2015 Barzilay got sick, which gave her a closer look at medicine. “When I became a patient, I realized the healthcare system doesn’t utilize any of the great technologies that most computer scientists know,” she recalled. She said she felt patients could benefit from being exposed to AI technologies, so she started looking for where to apply them.

Fortunately, the shift from language to proteins wasn’t that difficult — a lot of the AI architecture and techniques used in medicine were first developed for language models. In a sense, you can look at a molecular structure as a sentence.

The great opportunity and challenge she saw is that scientists will never have the same amount of training data in medicine as there is available for language — partly due to patient privacy protections — but you have laws of physics, chemistry, and biology on your side, to help models stay true to the underlying fabric of physical systems. “You have other types of power that you don’t have in language,” Barzilay said.

In the meantime, she and her colleagues are working on a second version of BOLTZ, an open-source implementation of AlphaFold 3, the groundbreaking AI designed to model protein folding. Barzilay is also working on using AI models to design new molecules for drugs, she said. “We’re really excited to see if they can get to clinical authorization.”