News

Berkeley computer theorists show path to verifying that quantum beats classical

UC Berkeley computer theorists led by CS Prof. Umesh Vazirani,  published a proof of random circuit sampling (RCS) as a verification method to prove quantum supremacy in a paper published Monday, Oct. 29, in the journal Nature Physics.  Quantum supremacy is the term that describes a quantum computer’s ability to solve a computational task that would be prohibitively difficult for any classical algorithm.  “Besides being a milestone on the way to useful quantum computers, quantum supremacy is a new kind of physics experiment to test quantum mechanics in a new regime. The basic question that must be answered for any such experiment is how confident can we be that the observed behavior is truly quantum and could not have been replicated by classical means. That is what our results address,” said Vazirani.

IP paper wins 2018 ACM SenSys Test of Time Award

A paper written by CS Prof. David Culler and alumnus Jonathan Hui (M.S. '05/Ph.D. '08) in 2008 titled "IP is Dead, Long Live IP for Wireless Sensor Networks" has won the Association of Computing Machinery (ACM) Conference on Embedded Networked Sensor Systems (SenSys) 2018 Test of Time Award.  The paper dispelled the notion that IP cannot run on wireless embedded sensors and made a long term impact  on standards like 6LoWPAN and platforms like Thread.  The award recognizes papers that are at least 10 years old and have had long lasting impact on networked embedded sensing system science and engineering.  Culler previously won this award in both 2014 and 2015.

Barbara Simons: Making Votes Count

2005 CS Distinguished Alumna Barbara Simons (Ph.D. '81) is the subject of a Berkeley Engineering profile celebrating the 150th anniversary of U.C. Berkeley.  Simons, who is a past president of the Association for Computing Machinery (ACM), has been drawing attention to the pitfalls of electronic voting since 2003.  She's a vocal critic of electronic ballots and is board chair of Verified Voting, a non-partisan organization that advocates for reliable and secure voting practices, as well as the author of a book titled “Broken Ballots: Will Your Vote Count?”   She is also a long-time champion for programs to increase diversity in computer science and engineering.

Berkeley is #1 university open source contributor

UC Berkeley is the top ranked university in the third annual Octoverse Report list of "Open source contributions made by employees of different organizations," with 2700 contributions.  Berkeley is the fourth ranked organization overall--after Microsoft, Google, and Red Hat.  The Octoverse Report is a roundup of GitHub data across global repositories from the last 12 months.  Four other universities made the top ten:  the University of Washington  (6th place with 1800 contributions), MIT (8th place with 1700), UMich and Stanford (tied 9th with 1600 contributions each) .  

Urmila Mahadev Solves Quantum Verification Problem

CS postdoctoral researcher Urmila Mahadev (advisor: Umesh Vazirani) has come up with an interactive protocol by which users with no quantum powers of their own can employ cryptography to put a harness on a quantum computer and drive it wherever they want, with the certainty that the quantum computer is following their orders.  Her work, which addressed the question "How do you know whether a quantum computer has done anything quantum at all?" was awarded the “best paper” and “best student paper” prizes when it was presented at the Symposium on Foundations of Computer Science this month.  CIT computer scientistThomas Vidick calls her result “one of the most outstanding ideas to have emerged at the interface of quantum computing and theoretical computer science in recent years.”

Jun-Yan Zhu wins ACM SIGGRAPH Outstanding Doctoral Dissertation Award

CS alumnus Jun-Yan Zhu (Ph.D. '17, advisor: Alexei Efros) has won the Association for Computing Machinery (ACM) Special Interest Group on Computer Graphics and Interactive Techniques (SIGGRAPH) Outstanding Doctoral Dissertation Award. Zhu is a pioneer in the use of modern machine learning in computer graphics. His dissertation is arguably the first to systematically attack the problem of natural image synthesis using deep neural networks. As such, his work has already had an enormous impact on the field, with several of his contributions, most notably CycleGAN, becoming widely-used tools not just for researchers in computer graphics and beyond, but also for visual artists.

PerfFuzz wins ISSTA18 Distinguished Paper Award

"PerfFuzz: Automatically Generating Pathological Inputs," written by graduate students Caroline Lemieux and Rohan Padhye, and Profs. Koushik Sen and Dawn Song, will receive a Distinguished Paper Award from the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) 2018 in Amsterdam in July.  PerfFuzz is a method to automatically generate inputs for software programs via feedback-directed mutational fuzzing.  These inputs exercise pathological behavior across program locations, without any domain knowledge.   The authors found that PerfFuzz outperforms prior work by generating inputs that exercise the most-hit program branch 5x to 69x times more, and result in 1.9x to 24.7x longer total execution paths.

Aviad Rubinstein wins 2017 ACM Doctoral Dissertation Award

CS alumnus Aviad Rubinstein (Ph.D. ' 17, advisor: Christos Papadimitriou) is the recipient of the Association for Computing Machinery (ACM) 2017 Doctoral Dissertation Award for his dissertation “Hardness of Approximation Between P and NP.”  In his thesis, Rubinstein established the intractability of the approximate Nash equilibrium problem and several other important problems between P and NP-completeness—an enduring problem in theoretical computer science.  His work was featured in a Quanta Magazine article titled "In Game Theory, No Clear Path to Equilibrium" in July. After graduating, Rubinstein became a Rabin Postdoc at Harvard and will join Stanford as an Assistant Professor in the fall.

HäirIÖ: Human Hair as Interactive Material

CS Prof. Eric Paulos and his graduate students in the Hybrid Ecologies Lab, Sarah Sterman, Molly Nicholas, and Christine Dierk, have created a prototype of a wearable color- and shape-changing braid called HäirIÖ.  The hair extension is built from a custom circuit, an Arduino Nano, an Adafruit Bluetooth board, shape memory alloy, and thermochromic pigments.  The bluetooth chip allows devices such as phones and laptops to communicate with the hair, causing it to change shape and color, as well as respond when the hair is touched. Their paper "Human Hair as Interactive Material," was presented at the ACM International Conference on Tangible, Embedded and Embodied Interaction (TEI) last week. They have posted a how-to guide and instructable videos which include comprehensive hardware, software, and electronics documentation, as well as information about the design process. "Hair is a unique and little-explored material for new wearable technologies," the guide says.  "Its long history of cultural and individual expression make it a fruitful site for novel interactions."

Making computer animation more agile, acrobatic — and realistic

Graduate student Xue Bin “Jason” Peng (advisors Pieter Abbeel and Sergey Levine) has made a major advance in realistic computer animation using deep reinforcement learning to recreate natural motions, even for acrobatic feats like break dancing and martial arts. The simulated characters can also respond naturally to changes in the environment, such as recovering from tripping or being pelted by projectiles.  “We developed more capable agents that behave in a natural manner,” Peng said. “If you compare our results to motion-capture recorded from humans, we are getting to the point where it is pretty difficult to distinguish the two, to tell what is simulation and what is real. We’re moving toward a virtual stuntman.”  Peng will present his paper at the 2018 SIGGRAPH conference in August.