Communications of the ACM

Institute of Technology (MIT). Their original aim was to find a new way to construct authentication systems that did not rely on cryptographic functions that are assumed to be hard for computers to break. To do so, they employed the idea of the zero-knowledge proof, which lets two remote systems (known as provers) demonstrate to a third party, the verifier, that they hold a secret, without revealing the secret itself.

The provers are assumed to be able to solve any problem. To prevent the provers from cheating, the verifier uses randomly generated queries in an interactive protocol designed to catch attempts by either prover to conspire with the other to deliver a false answer. The only way they could lie reliably is to work together. To avoid this possibility, classical implementations of zero-knowledge proofs rely on setting up the tests so the two provers cannot communicate with each other directly.

The work on multiprover interactive proof (MIP) systems later expanded into delegated computing: to let systems offload tasks to remote servers. In a paper presented at the 2008 ACM Symposium of the Theory of Computing in British Columbia, Canada, Goldwasser and colleagues referenced the Harry Potter series, whose seventh and final volume was published that year, with the claim that a “muggle” machine (in this context, a conventional computer) could check the work much more capable computers claim to be able to perform. The question that challenged theoreticians was how much more those magical systems could do, and still let non-wizardly computers check whether their work is valid.

A few years after the original MIP
work appeared, Lászlo Babai, Lance
Fortnow, and Carsten Lund, working
at the University of Chicago, showed a
user with access to a machine able only
to handle problems in polynomial time
could verify the work on problems that,
for a Turing machine that can perform
multiple operations in each computa-
tional step, require exponential time to
solve. This is a complexity class known
as NEXP. The open question before last
year was what difference quantum en-
tanglement between the provers would
make, an arrangement that mathemati-
cians call MIP*.
“When MIP* was first introduced, it
wasn’t clear whether it was more pow-
erful than MIP,” Wright says.

Researchers believed MIP* could deliver greater power by letting the provers share states through entanglement. But it carried with it the threat of collusion. Separate provers could use their shared knowledge to collude with each other in a way that classical multiprover systems do not. This would, in turn, reduce the theoretical power of multiprover systems that use quantum-capable provers.

ACM has named 58 members ACM Fellows for their wide-ranging, fundamental contributions in areas including artificial intelligence, cloud computing, combating cybercrime, quantum computing, and wireless networking.

“Computing technology has
had a tremendous impact in
shaping how we live and work
today,” said ACM President Cherri
M. Pancake. “In highlighting the
accomplishments of the ACM Fel-
lows, we hope to give credit where
it is due, while also educating the
public about the extraordinary
array of areas in which computing
professionals work.”
The 2019 Fellows hail from
universities, companies and
research centers in Australia,
Canada, China, Egypt, France,
Germany, Israel, Italy, Switzer-
land, and the United States.

The 2019 ACM Fellows are: Scott J. Aaronson,

University of Texas

Tarek F. Abdelzaher, University of Illinois at Urbana-Champaign

Saman Amarasinghe,

Massachusetts Institute of Technology

Kavita Bala, Cornell University

Magdalena Balazinska,

University of Washington

Paul Beame, University of
Washington

Emery D. Berger, University of Massachusetts Amherst

Ronald F. Boisvert,

National Institute of Standards and Technology

Christian Cachin,

University of Bern

Brad Calder, Google

Diego Calvanese, Free University of Bozen-Bolzano

Srdjan Capkun, Swiss Federal Polytechnic, Zurich

Claire Cardie, Cornell University

Timothy M. Chan, University of Illinois at Urbana-Champaign

Kanianthra Mani Chandy,

California Institute of Technology

Xilin Chen, Institute of Computing Technology, Chinese Academy of Sciences

Elizabeth F. Churchill, Google

Philip R. Cohen,

Monash University

Vincent Conitzer, Duke University

Noshir Contractor,

Northwestern University

Matthew B. Dwyer,

University of Virginia

Elena Ferrari,

University of Insubria

Michael J. Freedman,

Princeton University

Deborah Frincke, U.S. National Security Agency

Lise Getoor, University of California, Santa Cruz

Maria L. Gini,

University of Minnesota

Subbarao Kambhampati,

Arizona State University

Tamara G. Kolda,

Sandia National Laboratories

Songwu Lu, University of California, Los Angeles

Wendy Elizabeth Mackay, Inria

Diana Marculescu,

University of Texas at Austin

Sheila McIlraith,

University of Toronto

Rada Mihalcea,

University of Michigan

Robin R. Murphy,

Texas A&M University

Marc Najork, Google

Jason Nieh, Columbia University

Hanspeter Pfister,

Harvard University

Timothy M. Pinkston, University of Southern California

Mihai Pop, University of Maryland, College Park

Andreas Reuter, Heidelberg University/Heidelberg Laureate Forum Foundation

Jeffrey S. Rosenschein,

Hebrew University

Srinivasan Seshan,

Carnegie Mellon University

Prashant J. Shenoy, University of Massachusetts Amherst

Peter W. Shor, Massachusetts
Institute of Technology
Mona Singh, Princeton University
Ramesh K. Sitaraman, University
of Massachusetts Amherst
Dawn Song, University of
California, Berkeley
Salvatore J. Stolfo,

Columbia University Dacheng Tao,

The University of Sydney
Moshe Tennenholtz, Technion
Giovanni Vigna, University of
Yale University

Darrell Whitley,

Colorado State University
Yuan Xie, University of California,
Santa Barbara
Moustafa Amin Youssef,
Alexandria University
Carlo A. Zaniolo. University
of California, Los Angeles
Lidong Zhou,

Microsoft Research Asia

ACM will formally recognize its 2019 Fellows at the annual Awards Banquet in San Francisco on June 20, 2020. Additional information about the 2019 ACM Fellows, as well as previously named ACM Fellows, is available on the ACM Fellows site at https:// awards.acm.org/fellows.