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.
Milestones
ACM Recognizes 2019 Fellows