ACM named Yael Tauman Kalai the recipient of the 2022 ACM Prize in Computing for breakthroughs in verifiable delegation of computation and fundamental contributions to cryptography. Kalai’s contributions have helped shape modern cryptographic practices and provided a strong foundation for further advancements.

The ACM Prize in Computing recognizes early-to-mid-career computer scientists whose research contributions have fundamental impact and broad implications. The award carries a prize of $250,000, from an endowment provided by Infosys Ltd.

Verifiable Delegation of Computation

Kalai has developed methods for producing succinct proofs that certify the correctness of any computation. This method enables a weak device to offload any computation to a stronger device in a way that enables the results to be efficiently checked for correctness. Such succinct proofs have been used by numerous blockchain companies (including Ethereum) to certify transaction validity and thereby overcome key obstacles in blockchain scalability, enabling faster and more reliable transactions. Kalai's research has provided essential definitions, key concepts, and inventive techniques to this domain.

More specifically, Kalai's work pioneered the study of “doubly efficient” interactive proofs, which ensure that the computational overhead placed on the strong device is small (nearly linear in the running time of the computation being proved). In contrast, previous constructions incurred an overhead that is super-exponential in the space of the computation. Kalai’s work transformed the concept of delegation from a theoretical curiosity to a reality in practice. Her subsequent work used cryptography to develop certificates of computation, eliminating the need for back-and-forth interaction. This work used insights from quantum information theory, specifically "non-signaling" strategies, to construct a one-round delegation scheme for any computation. These schemes have led to a body of work on delegation including theoretical advancements, applied implementations, and real-world deployment.

Additional Contributions to Cryptography

Kalai’s other important contributions include her breakthrough work on the security of the "Fiat-Shamir paradigm," a general technique for eliminating interaction from interactive protocols. This paradigm is extensively utilized in real-world applications including in the most prevalent digital signature scheme (ECDSA) which is used by all iOS and Android mobile devices. Despite its widespread adoption, its security has been poorly understood. Kalai's research established a solid foundation for understanding the security of this paradigm. In addition, she co-pioneered the field of leakage resilient cryptography and solved a long-standing open problem in interactive coding theory, showing how to convert any interactive protocol into one that is resilient to a constant fraction of adversarial errors while increasing the communication complexity by at most a constant factor and the running time by at most a polynomial factor. Kalai's extensive work in the field of cryptography has helped shape modern cryptographic practices and provided a strong foundation for further advancements.

“As data is the currency of our digital age, the work of cryptographers, who encrypt and decrypt coded language, is essential to keeping our technological systems secure and our data private, as necessary,” said ACM President Yannis Ioannidis. “Kalai has not only made astonishing breakthroughs in the mathematical foundations of cryptography, but her proofs have been practically useful in areas such as blockchain and cryptocurrencies. Her research addresses complex problems whose solution opens new directions to where the field is heading—focusing on keeping small computers (such as smartphones) secure from potentially malicious cloud servers. A true star all around, she has also established herself as a respected mentor, inspiring and cultivating the next generation of cryptographers.”

“We are pleased to see one of the world’s leading cryptographers recognized,” said Salil Parekh, Chief Executive Officer, Infosys. “Kalai’s technical depth and innovation of her work has definitely made a tremendous mark in this field and will inspire aspiring cryptographers. We are thankful for her contributions to date and can only imagine what she has in store in the coming years. Infosys has been proud to sponsor the ACM Prize since its inception. Recognizing the achievements of young professionals is especially important in computing, as bold innovations from people early in their careers have a tremendous impact on our field.”

Kalai will be formally presented with the ACM Prize in Computing at the annual ACM Awards Banquet, which will be held this year on Saturday, June 10 at the Palace Hotel in San Francisco.

ACM named Pieter Abbeel the recipient of the 2021 ACM Prize in Computing for contributions to robot learning, including learning from demonstrations and deep reinforcement learning for robotic control. Abbeel pioneered teaching robots to learn from human demonstrations (“apprenticeship learning”) and through their own trial and error (“reinforcement learning”), which have formed the foundation for the next generation of robotics. Abbeel is a Professor at the University of California, Berkeley and the Co-Founder, President and Chief Scientist at Covariant, an AI robotics company.

Early in his career, Abbeel developed new apprenticeship learning techniques to significantly improve robotic manipulation. As the field matured, researchers were able to program robots to perceive and manipulate rigid objects such as wooden blocks or spoons. However, programming robots to manipulate deformable objects, such as cloth, proved difficult because the way soft materials move when touched is unpredictable. Abbeel introduced new methods to enhance robot visual perception, physics-based tracking, control, and learning from demonstration. By combining these new methods, Abbeel developed a robot that was able to fold clothes such as towels and shirts ─ an improvement over existing technology that was considered an important milestone at the time.

Abbeel’s contributions also include developing robots that can perform surgical suturing, detect objects, and plan their trajectories in uncertain situations. More recently, he has pioneered “few-shot imitation learning,” where a robot is able to learn to perform a task from just one demonstration after having been pre-trained with a large set of demonstrations on related tasks.

Another especially promising area where Abbeel has made important contributions is in deep reinforcement learning for robotics. Reinforcement learning is an area of machine learning where an agent (e.g., a computer program) seeks to progress towards a reward (e.g., winning a game). While early reinforcement learning programs were effective, they could only perform simple tasks. The innovation of combining reinforcement learning with deep neural networks ushered in the new field of deep reinforcement learning, which can solve far more complex problems than computer programs developed with reinforcement learning alone.

Abbeel’s key breakthrough contribution in this area was developing a deep reinforcement learning method called Trust Region Policy Optimization. This method stabilizes the reinforcement learning process, enabling robots to learn a range of simulated control skills. By sharing his results, posting video tutorials, and releasing open-source code from his lab, Abbeel helped build a community of researchers that has since pushed deep learning for robotics even further ─ with robots performing ever more complicated tasks.

Abbeel has also made several other pioneering contributions including: generalized advantage estimation, which enabled the first 3D robot locomotion learning; soft-actor critic, which is one of the most popular deep reinforcement learning algorithms to-date; domain randomization, which showcases how learning across appropriately randomized simulators can generalize surprisingly well to the real world; and hindsight experience replay, which has been instrumental for deep reinforcement learning in sparse-reward/goal-oriented environments.

“Teaching robots to learn could spur major advances across many industries ─ from surgery and manufacturing to shipping and automated driving,” said ACM President Gabriele Kotsis. “Pieter Abbeel is a recognized leader among a new generation of researchers who are harnessing the latest machine learning techniques to revolutionize this field. Abbeel has made leapfrog research contributions, while also generously sharing his knowledge to build a community of colleagues working to take robots to an exciting new level of ability. His work exemplifies the intent of the ACM Prize in Computing to recognize outstanding work with ‘depth, impact, and broad implications.’”

“Infosys is proud of our longstanding collaboration with ACM, and we are honored to recognize Pieter Abbeel for the 2021 ACM Prize in Computing,” said Salil Parekh, Chief Executive Officer, Infosys. “The robotics field is poised for even greater advances, as innovative new ways are emerging to combine robotics with AI, and we believe researchers like Abbeel will be instrumental in creating the next great advances in this field.”

Abbeel will be formally presented with the ACM Prize in Computing at the annual ACM Awards Banquet, which will be held this year on Saturday, June 11 at the Palace Hotel in San Francisco.

ACM named Scott Aaronson the recipient of the 2020 ACM Prize in Computing for groundbreaking contributions to quantum computing. Aaronson is the David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin.

The goal of quantum computing is to harness the laws of quantum physics to build devices that can solve problems that classical computers either cannot solve, or not solve in any reasonable amount of time. Aaronson showed how results from computational complexity theory can provide new insights into the laws of quantum physics, and brought clarity to what quantum computers will, and will not, be able to do.

Aaronson helped develop the concept of quantum supremacy, which denotes the milestone that is achieved when a quantum device can solve a problem that no classical computer can solve in a reasonable amount of time. Aaronson established many of the theoretical foundations of quantum supremacy experiments. Such experiments allow scientists to give convincing evidence that quantum computers provide exponential speedups without having to first build a full fault-tolerant quantum computer.

“Few areas of technology have as much potential as quantum computation,” said ACM President Gabriele Kotsis. “Despite being at a relatively early stage in his career, Scott Aaronson is esteemed by his colleagues for the breadth and depth of his contributions. He has helped guide the development of this new field, while clarifying its possibilities as a leading educator and superb communicator. Importantly, his contributions have not been confined to quantum computation, but have had significant impact in areas such as computational complexity theory and physics.”

Notable Contributions

Boson Sampling: In the paper “The Computational Complexity of Linear Optics,” Aaronson and co-author Alex Arkhipov gave evidence that rudimentary quantum computers built entirely out of linear-optical elements cannot be efficiently simulated by classical computers.

Aaronson has since explored how quantum supremacy experiments could deliver a key application of quantum computing, namely the generation of cryptographically random bits.

Fundamental Limits of Quantum Computers: In his 2002 paper “Quantum lower bound for the collision problem,” Aaronson proved the quantum lower bound for the collision problem, which was a major open problem for years. This work bounds the minimum time for a quantum computer to find collisions in many-to-one functions, giving evidence that a basic building block of cryptography will remain secure for quantum computers.

Classical Complexity Theory: Aaronson is well-known for his work on “algebrization”, a technique he invented with Avi Wigderson to understand the limits of algebraic techniques for separating and collapsing complexity classes.

Making Quantum Computing Accessible: Beyond his technical contributions, Aaronson is credited with making quantum computing understandable to a wide audience. Through his many efforts, he has become recognized as a leading spokesperson for the field. He maintains a popular blog, Shtetl Optimized, where he explains timely and exciting topics in quantum computing in a simple and effective way. His posts, which range from fundamental theory questions to debates about current quantum devices, are widely read and trigger many interesting discussions.

Aaronson also authored Quantum Computing Since Democritus, a respected book on quantum computing, written several articles for a popular science audience, and presented TED Talks to dispel misconceptions and provide the public with a more accurate overview of the field.

“Infosys is proud to fund the ACM Prize in Computing and we congratulate Scott Aaronson on being this year’s recipient,” said Pravin Rao, COO of Infosys. “When the effort to build quantum computation devices was first seriously explored in the 1990s, some labeled it as science fiction. While the realization of a fully functional quantum computer may still be in the future, this is certainly not science fiction. The successful quantum hardware experiments by Google and others have been a marvel to many who are following these developments. Scott Aaronson has been a leading figure in this area of research and his contributions will continue to focus and guide the field as it reaches its remarkable potential.”

ACM named David Silver the recipient of the 2019 ACM Prize in Computing for breakthrough advances in computer game-playing. Silver is a Professor at University College London and a Principal Research Scientist at DeepMind, a Google-owned artificial intelligence company based in the United Kingdom. Silver is recognized as a central figure in the growing and impactful area of deep reinforcement learning.

Silver’s most highly publicized achievement was leading the team that developed AlphaGo, a computer program that defeated the world champion of the game Go, a popular abstract board game. Silver developed the AlphaGo algorithm by deftly combining ideas from deep-learning, reinforcement-learning, traditional tree-search and large-scale computing. AlphaGo is recognized as a milestone in artificial intelligence (AI) research and was ranked by New Scientist magazine as one of the top 10 discoveries of the last decade.

AlphaGo was initialized by training on expert human games followed by reinforcement learning to improve its performance. Subsequently, Silver sought even more principled methods for achieving greater performance and generality. He developed the AlphaZero algorithm that learned entirely by playing games against itself, starting without any human data or prior knowledge except the game rules. AlphaZero achieved superhuman performance in the games of chess, Shogi, and Go, demonstrating unprecedented generality of the game-playing methods.

Computer Game-Playing and AI
Teaching computer programs to play games, against humans or other computers, has been a central practice in AI research since the 1950s. Game playing, which requires an agent to make a series of decisions toward an objective—winning—is seen as a useful facsimile of human thought processes. Game-playing also affords researchers results that are easily quantifiable—that is, did the computer follow the rules, score points, and/or win the game?

At the dawn of the field, researchers developed programs to compete with humans at checkers, and over the decades, increasingly sophisticated chess programs were introduced. A watershed moment occurred in 1997, when ACM sponsored a tournament in which IBM’s DeepBlue became the first computer to defeat a world chess champion, Gary Kasparov. At the same time, the objective of the researchers was not simply to develop programs to win games, but to use game-playing as a touchstone to develop machines with capacities that simulated human intelligence.

“Few other researchers have generated as much excitement in the AI field as David Silver,” said ACM President Cherri M. Pancake. “Human vs. machine contests have long been a yardstick for AI. Millions of people around the world watched as AlphaGo defeated the Go world champion, Lee Sedol, on television in March 2016. But that was just the beginning of Silver’s impact. His insights into deep reinforcement learning are already being applied in areas such as improving the efficiency of the UK’s power grid, reducing power consumption at Google’s data centers, and planning the trajectories of space probes for the European Space Agency.”

“Infosys congratulates David Silver for his accomplishments in making foundational contributions to deep reinforcement learning and thus rapidly accelerating the state of the art in artificial intelligence,” said Pravin Rao, COO of Infosys. “When computers can defeat world champions at complex board games, it captures the public imagination and attracts young researchers to areas like machine learning. Importantly, the frameworks that Silver and his colleagues have developed will inform all areas of AI, as well as practical applications in business and industry for many years to come. Infosys is proud to provide financial support for the ACM Prize in Computing and to join with ACM in recognizing outstanding young computing professionals.”

Silver is credited with being one of the foremost proponents of a new machine learning tool called deep reinforcement learning, in which the algorithm learns by trial-and-error in an interactive environment. The algorithm continually adjusts its actions based on the information it accumulates while it is running. In deep reinforcement learning, artificial neural networks—computation models which use different layers of mathematical processing—are effectively combined with the reinforcement learning strategies to evaluate the trial-and-error results. Instead of having to perform calculations of every possible outcome, the algorithm makes predictions leading to a more efficient execution of a given task.

Learning Atari from Scratch
At the Neural Information Processing Systems Conference (NeurIPS) in 2013, Silver and his colleagues at DeepMind presented a program that could play 50 Atari games to human-level ability. The program learned to play the games based solely on observing the pixels and scores while playing. Earlier reinforcement learning approaches had not achieved anything close to this level of ability.

Silver and his colleagues published their method of combining reinforcement learning with artificial neural networks in a seminal 2015 paper, “Human Level Control Through Deep Reinforcement Learning,” which was published in Nature. The paper has been cited nearly 10,000 times and has had an immense impact on the field. Subsequently, Silver and his colleagues continued to refine these deep reinforcement learning algorithms with novel techniques, and these algorithms remain among the most widely-used tools in machine learning.

AlphaGo
The game of Go was invented in China 2,500 years ago and has remained popular, especially in Asia. Go is regarded as far more complex than chess, as there are vastly more potential moves a player can make, as well as many more ways a game can play out. Silver first began exploring the possibility of developing a computer program that could master Go when he was a PhD student at the University of Alberta, and it remained a continuing research interest.

Silver’s key insight in developing AlphaGo was to combine deep neural networks with an algorithm used in computer game-playing called Monte Carlo Tree Search. One strength of Monte Carlo Tree Search is that, while pursuing the perceived best strategy in a game, the algorithm is also continually investigating other alternatives. AlphaGo’s defeat of world Go champion Lee Sedol in March 2016 was hailed as a milestone moment in AI. Silver and his colleagues published the foundational technology underpinning AlphaGo in the paper “Mastering the Game of Go with Deep Neural Networks and Tree Search” that was published in Nature in 2016.

AlphaGo Zero, AlphaZero and AlphaStar
Silver and his team at DeepMind have continued to develop new algorithms that have significantly advanced the state of the art in computer game-playing and achieved results many in the field thought were not yet possible for AI systems. In developing the AlphaGo Zero algorithm, Silver and his collaborators demonstrated that it is possible for a program to master Go without any access to human expert games. The algorithm learns entirely by playing itself without any human data or prior knowledge, except the rules of the game and, in a further iteration, without even knowing the rules.

Later, the DeepMind team’s AlphaZero also achieved superhuman performance in chess, Shogi, and Go. In chess, AlphaZero easily defeated world computer chess champion Stockfish, a high-performance program designed by grandmasters and chess programming experts. Just last year, the DeepMind team, led by Silver, developed AlphaStar, which mastered the multiple-player video game StarCraft II, which had been regarded as a stunningly hard challenge for AI learning systems.

The DeepMind team continues to advance these technologies and find applications for them. Among other initiatives, Google is exploring how to use deep reinforcement learning approaches to manage robotic machinery at factories.

ACM named Shwetak Patel of the University of Washington and Google the recipient of the 2018 ACM Prize in Computing for contributions to creative and practical sensing systems for sustainability and health. Before Patel’s work, most systems for monitoring energy and health required expensive and cumbersome specialized devices, precluding practical widespread adoption. Patel and his students found highly creative ways to leverage existing infrastructure to make affordable and accurate monitoring a practical reality. Patel quickly turned his team’s research contributions into real-world deployments, founding companies to commercialize their work.

The ACM Prize in Computing recognizes early-to-mid-career computer scientists whose research contributions have fundamental impact and broad implications. The award carries a prize of $250,000, from an endowment provided by Infosys Ltd.

“Despite the fact that he is only 37, Shwetak Patel has had significant impact on the field of ubiquitous computing for nearly two decades,” said ACM President Cherri M. Pancake. “His work has ushered in some really exciting possibilities in the areas of sustainability and health. The widespread adoption of systems where individuals can monitor their health with smartphones could revolutionize health care—especially in the developing world. Shwetak Patel certainly exemplifies the ACM Prize’s goal of recognizing work with ‘fundamental impact and broad implications.’”

“Infosys is proud to support the ACM Prize in Computing, which this year recognizes Shwetak Patel for his trailblazing work in ubiquitous computing,” said Pravin Rao, COO of Infosys. “Beyond breaking new conceptual ground through research in many areas, Shwetak Patel is especially adept at rapidly bringing his ideas to the public via new products that are accessible and affordable. Patel’s vision for ubiquitous computing is to enhance our everyday world with sensing, data processing and computation. The way in which his digital health initiatives combine AI with sensors and mobile computing is also very exciting and will likely have a significant impact on health care around the world for many years to come.”

Patel’s research closed the gap between science fiction and reality in many applications in ubiquitous computing for sustainability and health.

Monitoring Energy and Water Usage in the Home

With the emergence of embedded computing systems over the past few decades, a longstanding goal has been to use embedded devices to gain a more fine-grained understanding of home water and energy usage than is available by simply reading a monthly utility bill. In industry, one proposed solution has been to develop “smart appliances” in which items such as refrigerators or televisions would be fitted with special meters so that that their energy consumption could be monitored. Rather than having smart devices throughout the home, each with its own meter, Patel recognized that a home’s electrical system (and later its plumbing system) can be reconsidered as a network capable of capturing and transmitting information. Patel’s insight was that each appliance, as it uses power, generates and transmits information as “noise” (perturbations) on the circuit. Patel then developed a method to “disambiguate” (separate and catalog) which rooms, appliances, and times of day energy was being used. Patel engineered the system so that an entire home could be monitored with just one meter for electricity and one meter for plumbing. Zensi, Inc., the startup he formed to commercialize his work, was sold to Belkin, which subsequently opened a 25-person R&D lab in Seattle to conduct further sustainability research alongside Patel in his team. In developing these products, Patel also became an electrician and plumber.

Low-Powered Home Sensors

Building on his work on sustainability in residential environments, Patel next developed a new approach for wireless sensor nodes in the home, which dramatically reduced power consumption of each node while continuing to cover the whole home. Patel’s Sensor Nodes Utilizing Powerline Infrastructure (SNUPI) nodes contain an ultra-low-power transmitter that extends its range by coupling its wirelessly transmitted signal to the existing powerlines. SNUPI was a core component of Patel’s next startup, WallyHome. Through its network of low-powered sensors WallyHome monitors temperature, humidity and any potential water leakages. For example, if an event(such as a dishwasher leak) occurs in the home, the homeowner will receive an instant text on their mobile phone. While WallyHome was purchased by Sears Holding Company in 2015, Patel’s research in smart home sensing has informed much of the growing smart home industry, including companies like Google, Next, and Samsung.

Digital Health

More recently, Patel has leveraged sensors already on mobile phones (such as cameras and microphones) for physiological sensing and the management of chronic diseases. These technologies include SPiroSmart and CoughSense, which monitor lung function; BiliCam, which detects neonatal jaundice in newborns; HemaApp, which monitors hemoglobin levels; OsteoApp, to screen for osteoporosis; and BPSense, which monitors blood pressure. Patel has been working closely with Bill Gates and the Gates Foundation to share these technologies throughout the developing world. His work using a microphone for respiratory monitoring has already been deployed in parts of India and Bangladesh, and HemaApp is being used in Peru to screen for childhood anemia. He also commercialized some of these technologies, which were acquired by Google.

Biographical Background

Shwetak N. Patel is the Washington Research Foundation Entrepreneurship Endowed Professor in Computer Science and Engineering at the University of Washington, where he directs the Ubicomp Lab, which develops innovative sensing systems for real-world applications in health, sustainability and novel interactions. He is also a director at Google working on health care.

Patel earned his Bachelor’s and PhD degrees in Computer Science from Georgia Institute of Technology. His numerous honors include receiving a MacArthur Fellowship, a Sloan Fellowship, a Presidential Early Career Award for Scientists and Engineers (PECASE), MIT TR-35 Award, and a National Academy of Engineering Gilbreth Award. Patel is a Fellow of ACM.

Patel will formally receive the ACM Prize in Computing at ACM’s annual awards banquet on June 15, 2019 in San Francisco.

ACM named Dina Katabi of the Massachusetts Institute of Technology’s Computer Science and Artificial Intelligence Laboratory (MIT CSAIL) the recipient of the 2017 ACM Prize in Computing for creative contributions to wireless systems. Recognized as one of the most innovative researchers in the field of networking, Katabi applies methods from communication theory, signal processing and machine learning to solve problems in wireless networking. Among her contributions, she is cited for co-authoring several highly influential papers on overcoming interference in wireless networks to improve the flow of data traffic.  And in inventing a device that seems to be lifted out of the pages of science fiction, she and her team pioneered the use of wireless signals in applications that can sense humans behind walls, determine their movements and even surmise their emotional states. These trailblazing human-sensing technologies hold out promise for use in several applications of daily life including helping the house-bound elderly, and perhaps determining survivors within buildings during search and rescue operations.

The ACM Prize in Computing recognizes early-to-mid-career contributions that have fundamental impact and broad implications. The award carries a prize of $250,000. Financial support is provided by an endowment from Infosys Ltd.

“Innovations which help facilitate communications across mobile networks certainly address an important need,” explained ACM President Vicki L. Hanson. “One recent report estimated that worldwide mobile data traffic grew 18-fold between 2011 and 2016. Dina Katabi’s work has contributed to a seamless increase in traffic, as well as the ever-increasing volumes of data that are shared over mobile systems. The official citation for the ACM Prize in Computing cites Katabi’s creative contributions because she is known for reimagining longstanding challenges in original ways.”

“Infosys is proud to support the ACM Prize in Computing, which this year honors Dina Katabi for her groundbreaking achievements in mobile systems,” said Salil S. Parekh, CEO of Infosys. “By 2020, experts predict that there will be 11.6 billion mobile-connected devices in the world. Our use of these devices, and the underlying networks that they rely upon, will play an increasingly important role in every aspect of life—from the way we communicate with friends and family, to our jobs, to the health of the world economy. By recognizing Katabi’s contributions, we educate the public about the technologies they use every day but may take for granted. Hopefully, we might also inspire the next generation to work in this exciting and very impactful area of computing science and practice.” 

Wireless Network Coding
Wired networks simply route (or forward) signals from one point to another, and early wireless networks were based on this blueprint. Wireless networks, however, are fundamentally different from wired networks and at times face challenges including inadequate mobile support, dead spots, and low throughput—or the amount of data that can be moved from one point to another in a given time. As wireless technology developed, many proposed a new unifying design paradigm called network coding in which each node in a network would perform some computation. At each node, the transmission could be mixed (encoded), or re-mixed (re-encoded), in order to be unmixed (decoded) at its final destination. Katabi was a leader in presenting ideas to make the theory of network coding practical as a way to improve network performance. The papers in which she introduced concrete methods to make network coding practical received awards at major conferences and remain staples of the reading lists in wireless classes.

Interference Mitigation
Following up on her work in network coding, Katabi and her collaborators have written several research papers on the fundamental problem of interference in wireless networks, which occurs when multiple nodes transmit concurrently. In these papers, she modeled how wireless signals mix in the air as code, and then outlined algorithms that allow the receiver to decode these interference-based codes. Katabi’s methods were not only shown to overcome interference in wireless transmissions, but in some instances can be exploited to increase the amount of data that can move over the network.

Sensing and Wireless Signals
At ACM SIGCOMM 2013, Katabi presented a highly influential paper, “See through Walls with Wi-Fi!” She demonstrated how Wi-Fi-based devices and their variants can be used to detect people behind walls, their movements, and even their emotional states. The device works by transmitting wireless radio signals that traverse a wall and reflect off a person’s body back to the device. While the data that comes back from these reflections is very minimal, Katabi and her team developed a series of algorithms that separate the meaningful signals from the random noise produced by the walls and other reflections. The technology can identify a person’s silhouette and detect gestures as subtle as the rise and fall of a person’s chest from the other side of a house. Her lab has recently advanced the technology to remotely monitor a person’s heart rate and other vital signs, to infer, among other indicators, their emotional states. The work has generated a huge amount of interest and was one of the invited demonstrations at President Obama’s White House Demo Day.

Sparse Fast Fourier Transform
In computing, the Discrete Fourier Transform (DFT) is a mathematical technique that is used for processing streams of data in a range of computational tasks including audio/image processing, biochemistry, astronomy, and even GPS. Traditionally, the Fast Fourier Transform (FFT) was the algorithm that was used to process data for a wide range of computational tasks. Katabi, along with MIT colleague Piotr Indyk and students, developed a new algorithm, the Sparse Fast Fourier Transform (SFFT) that processes data 10 to 100 times faster than the FFT. Among its many other benefits, Katabi’s faster transform means that computers need less power to process the same amount of data.

Background
A native of Damascus, Syria, Dina Katabi is the Andrew and Erna Viterbi Professor of Computer Science and Director of the Center for Wireless Networks and Mobile Computing at the Massachusetts Institute of Technology (MIT). She received a PhD and MS in Computer Science from MIT, and a BS in Electrical Engineering from Damascus University, Syria.

Katabi is the author or co-author of over 100 scholarly publications covering a wide range of topics in networks and data communications. Her papers have been cited more than 20,000 times by researchers. She has been recognized with several honors including a MacArthur Fellowship, the ACM Grace Murray Hopper Award, several ACM SIGCOMM Best Paper Awards, an ACM SIGCOMM Test of Time Award and a National Science Foundation Career Award. Katabi is an ACM Fellow and was elected to the National Academy of Engineering.

ACM will present the 2017 ACM Prize in Computing at its annual Awards Banquet on June 23, 2018 in San Francisco, California.

ACM named Alexei A. Efros of the University of California, Berkeley  the recipient of the 2016 ACM Prize in Computing. Efros was cited for groundbreaking data-driven approaches to computer graphics and computer vision. A focus of his work has been to understand, model and recreate the visual world around us. Efros is a pioneer in combining the power of huge image datasets drawn from the Internet with machine learning algorithms to foster powerful image transformations and valuable research findings. He has also made fundamental contributions in texture synthesis, a technique that ushered in new horizons in computer graphics and is widely used in the film industry.

The ACM Prize in Computing recognizes early-to-mid-career contributions that have fundamental impact and broad implications. Infosys Ltd. provides financial support for the $250,000 annual award. Efros will formally receive the ACM Prize at ACM’s annual awards banquet on June 24, 2017 in San Francisco.

“It’s estimated that 1.8 billion images are uploaded to social media platforms worldwide every day,” explained ACM President Vicki L. Hanson. “This ocean of visual data provides great opportunities and some obvious challenges. In the area of artificial intelligence, for example, the ability to rapidly process huge quantities of photos or video stills can help a computer to recognize and identify patterns. Alexei Efros has consistently found pioneering ways to understand and create images using data-based tools that he has developed. His work underscores the exciting possibilities of this field and wonderfully exemplifies the criteria of ‘fundamental contributions’ and ‘broad implications’ that the ACM Prize award committee looks for.”

“Infosys is proud through its support of the ACM Prize in Computing to recognize Dr. Alexei Efros as a researcher who is passionate about understanding, reimagining and recreating the visual world around us,” said Dr. Vishal Sikka, CEO of Infosys. “In an increasingly digital world, Dr. Efros is showing us how artificial intelligence, machine learning, and data-driven computing are fundamentally reshaping the way the world is perceived by computers, and as a result, amplifying the way we as human beings understand our world. The new insights that his research has produced present a seemingly limitless number of potential applications in areas like computer graphics and computational photography, as well as robotics, visual data mining, and even the interaction between the visual arts and the humanities. Dr. Efros’ relentless pursuit of finding the great new problems of our digital future can inspire all of us to be more, and to see more, in everything that we do.”

Efros first gained wide recognition in the area of computer graphics with his 1999 paper, “Texture synthesis by non-parametric sampling,” co-authored with Thomas K. Leung. Texture synthesis is the process of taking a small sample of a digital image and then applying an algorithm to the sample’s structural content to enlarge the image, create background images, or perhaps fill in holes. Prior to Efros’ paper, the methods of synthesizing digital textures involved complicated mathematics and didn’t often produce visually appealing results. Efros and Leung showed that a new “non-parametric” approach could be used to easily produce visually appealing textures. Non-parametric modeling has revolutionized the field, being cited in nearly 3,000 research papers and benefiting the entertainment industry, where Efros’ insights have been employed in 3-D computer graphics, digital image editing, and post production of films.

Among the many other areas in which Efros has developed a groundbreaking approach to research that others have followed, is the development of algorithms to scan vast collections of photographs from the Internet. In their 2008 paper, “Scene Completion Using Millions of Photographs,” Efros and James Hays presented a new algorithm that patches up holes in images by finding similar images drawn from a database of millions of photographs gathered from the Web. This approach was revolutionary, and today researchers regularly use algorithms to scan millions of images drawn from social media platforms for image processing and recognition research.

Continuing in this vein of research, Efros has undertaken several deep learning projects that have shown a high success rate of translating an image of one kind to another. For example, in their recent paper “Colorful Image Colorization,” Efros, along with Richard Zhang and Phillip Isola, presented a new algorithm that automatically translates black-and-white photographs into color. Using the input of a black-and-white photo, the algorithm is trained on 1 million images from the Imagenet dataset to make a plausible estimate of the color of the different elements in a photograph. And in the paper “Image to Image Translation with Conditional Adversarial Nets,” Efros, along with Phillip Isola, Jun-Yan Zhou and Tinghui Zhou showed that the interplay of two networks—one continually drawing new images and another judging whether the images generated look natural—can produce surprising image translations. For example, accurate street maps can be created using aerial photographs, and virtual photographs of handbags can be produced from an outline drawing.

Other well-received projects employing similar techniques include: “A Century of Portraits: A Visual Historical Record of American High School Yearbooks,” wherin Efros, Shiry Ginosar and co-authors trained an algorithm on 37,000 photographs to examine the defining style elements, trends and social norms of various decades. In the Communications of the ACM article What Makes Paris Look Like Paris?, Efros and co-authors outlined a machine vision approach to developing a program that could scan thousands of photographs of close-up architectural details of a city, identify very subtle differences between the architectural details, and determine the city in which a given photo was taken.

ACM will present the 2016 ACM Prize in Computing at its annual Awards Banquet on June 24, 2017 in San Francisco, California.

Jeff Dean and Sanjay Ghemawat led the conception, design, and implementation of much of Google's revolutionary software infrastructure, which has transformed the practice and understanding of Internet-scale computing.