Skip to main content

“Every single one of you has what it takes to do great things”: A tribute to the Allen School Class of 2021

Katherine Turner

Last week marked the end of an academic year unlike any other — and the culmination of all of the hard work, hopes and dreams of a graduating class unlike any other. With the resumption of in-person pomp and circumstance precluded due to ongoing pandemic-related restrictions at the University of Washington, the Allen School marked this important milestone with a virtual tribute highlighting the Class of 2021’s commitment to excellence and service — and acknowledging their perseverance in the face of multiple, significant challenges over the past year.

Professor Magdalena Balazinska, director of the Allen School, led the tribute with a video message congratulating the graduates on rising to the occasion and completing their degrees under difficult circumstances. And now that they had, she urged them to use what they have learned to make the world a better place — and continue working to make computing a more inclusive field.

“As you graduate, you have the opportunity to make an impact in a variety of ways. Take it. Be bold,” Balazinska said. “Find ways to help the community and the world around you. Work on addressing humanity’s greatest challenges. Develop technology that serves everyone, not just those who look like you or share the same background or abilities. Strive to have diverse teams where everyone feels welcome and included.

“Making the world better is not only your opportunity, but it is your responsibility,” she continued. “Because if you don’t do it, then who will?”

Balazinska’s remarks were followed by a series of congratulatory messages to the graduates from her fellow faculty members, many of whom also contributed to a Class of 2021 Kudoboard that included messages from friends, family and classmates to the newly minted graduates. The Allen School also took the opportunity to recognize members of the graduating class who had particularly distinguished themselves through their academic achievements, leadership, and service contributions with its annual student awards

Portraits of Skyler Hallinan, Joy He-Yueya, Parker Ruth
From left: Skyler Hallinan, Joy He-Yueya and Parker Ruth

Skyler Hallinan is one of three graduates to receive the Allen School’s Outstanding Senior Award, which honors students with exceptional academic performance who exemplify leadership, good citizenship, and the pursuit of knowledge. Hallinan, who majored in computer science, applied & computational mathematical sciences, and bioengineering, was recognized for his undergraduate research in natural language processing under the guidance of Allen School professors Yejin Choi and Noah Smith, including techniques for analyzing misinformation and media bias and advancing commonsense reasoning. He also worked on the development of an orally ingestible hydrogel that would act as a substitute for a functional kidney in patients with chronic kidney disease and served as a teaching assistant (TA) in the Allen School for multiple quarters.

Joy He-Yueya and Parker Ruth each earned an Outstanding Senior Award and the Allen School’s Best Senior Thesis Award. He-Yueya, who earned her bachelor’s in computer science, worked with Allen School professor Tim Althoff in the Behavioral Data Science Group on research that led to her award-winning thesis, “Assessing the Relationship Between Routine and Schizophrenia Symptoms with Passively Sensed Measures of Behavioral Stability.” She also contributed to a project at the Max Planck Institute for Software Systems that used reinforcement learning to generate personalized curriculum for students learning to program. He-Yueya has served in multiple tutoring and peer mentoring roles — including helping other undergraduates to get their start in research. 

Portraits of Eric Fan and Eunia Lee
Eric Fan (left) and Eunia Lee

Ruth — who previously received the Dean’s Medal for Academic Excellence from the College of Engineering — was recognized by the Allen School for his many contributions in undergraduate research as a member of the UbiComp Lab, where he advanced mobile health tools that screen for conditions such as osteoporosis and stroke; enable continuous physiological sensing; and monitor threats to public health. That work formed the basis of his award-winning senior thesis, “Design Principles for Mobile and Wearable Health Technologies,” advised by professor Shwetak Patel.

The Allen School honored two other graduating seniors — Eric Fan and Eunia Lee — with Undergraduate Service Awards. This award recognizes students who have gone above and beyond in supporting the many events and activities that contribute to a vibrant school community. Fan has helped build that sense of community both in and out of the classroom, whether in person or remote. He served as TA coordinator for the Allen School’s introductory programming series, the entré into computer science for many students in and outside of the major. He also served as an officer of the UW chapter of the Association for Computing Machinery (ACM) and a member-at-large of the Allen School’s Student Advisory Council. After earning his bachelor’s in computer engineering, Fan is continuing his studies in the Allen School’s combined B.S./M.S. program.

Lee, who earned her degree in computer science, has taken on multiple leadership roles in the Allen School’s K-12 and campus-level outreach, with a focus on strengthening diversity and inclusion. Her contributions have included service as a lead Ambassador to high schools and lead TA for the direct-to-major seminar that assists freshmen entering the Allen School. She also chaired the UW chapter of ACM and was instrumental in the formation of the Allen School’s Diversity & Access team.

Portraits of Taylor Ka and Andrew Wei
Taylor Ka (left) and Andrew Wei

In addition to the awards to graduating students, the Allen School also commended half a dozen students who served as TAs in the past year with its Bob Bandes Memorial Awards for Excellence in Teaching. Service Award winner Eric Fan was among the Bandes Award recipients. Students appreciated Fan, who was a TA nine times, for being approachable and open to communication, including with those who took the course asynchronously: “Eric was a TA that contributed to my learning greatly, especially in a quarter that didn’t have the best circumstances surrounding it.”

One of Fan’s fellow Bandes Award winners, Taylor Ka, served as a TA for eight quarters of one of the courses in the introductory series, Computer Programming II. A faculty member called Ka, who earned her bachelor’s in computer science on the way to enrolling in the Allen School’s combined B.S./M.S. program,  “easily the best TA I have had across all courses at UW” and highlighted her knowledge, kindness, and approachability. A student recommended another award recipient, Andrew Wei, for his generosity and patience, and recalled how Wei would stay up late multiple nights per week to work with students who were struggling with assignments. Wei, who graduated from the B.S./M.S. program, assisted with no fewer than eight courses over 12 quarters.

The Allen School bestowed Bandes Award Honorable Mentions on three TAs: undergraduate Kyrie Dowling, and Ph.D. students Liang He and Edward Misback. Dowling, who has assisted with Systems Programming and The Hardware/Software Interface, stood out for her high energy, skillful explanation of concepts, and the fact that “it is very evident she cares about the learning of all of her students.” Meanwhile, He was recognized for his “positivity and creative encouragement” in supporting students in studio-oriented courses that typically feature physically-oriented lectures and coursework in the remote learning environment — including soldering, preparing and packaging more than 50 kits for delivery to students wherever they happened to be. Last but not least, Misback was recognized for guiding students through the “numerous technical pitfalls” of networking and web serving while encouraging them to discover solutions for themselves. As one faculty nominator suggested, “He will make an excellent teacher if he chooses that path.”

Portraits of Kyrie Dowling, Liang He, and Edward Misback
Left to right: Kyrie Dowling, Liang He and Edward Misback

This year’s Bandes Award honorees were selected from among 185 TAs nominated by faculty and students. A total of 670 students served as TAs during the academic year, assisting faculty and their fellow students to make the most of remote learning. Thanks in part to their efforts, an estimated 635 Allen School students earned their degrees in 2020-2021.

As she commended the graduates for achieving their educational goals, Balazinska noted this was not the end of their journey, but rather the beginning.

“Whatever your next steps are, an Allen School degree opens so many opportunities for you. I encourage you to be courageous. Continue to reach for the stars,” said Balazinska. “Go out and make your mark on the world. Every single one of you has what it takes to do great things.”

Congratulations to all of our graduates! We look forward to seeing what you do next — and to welcoming you back as alumni!

Editor’s note: Although the Allen School will award an estimated 635 degrees for the 2020-2021 academic year, only those students who opted into having their information displayed publicly are included in the online tribute.

June 18, 2021

Allen School’s Richard Anderson receives ACM Eugene L. Lawler Award for humanitarian contributions through computing

Portrait of Richard Anderson
Credit: Dana Brooks/University of Washington

Allen School professor Richard Anderson earned the ACM Eugene L. Lawler Award for Humanitarian Contributions within Computer Science and Informatics from the Association for Computing Machinery for his work bridging computer science, education and global health. Anderson, who co-directs the Information and Communication Technology for Development (ICTD) Lab, has devoted himself over the past two decades to advancing computing innovations that improve quality of life for people in rural and low-income communities around the globe.

After beginning his research and teaching career focused on theoretical computer science, Anderson embraced the opportunity to generate a tangible impact on underserved populations by helping to build up the emerging field of ICTD beginning in the early 2000s. One of his earliest contributions was to community-led education via the Digital StudyHall project, which brought high-quality teaching and interactive content to rural classrooms in India via facilitated video instruction. He subsequently teamed up with Seattle-based global health organization PATH on Projecting Health, an initiative aimed at using digital communications to help people in low-resource areas, including those with low literacy, to learn about and practice health-oriented behaviors to support maternal and child health. To date, Projecting Health has reached an estimated 190,000 people across 180 villages through local-produced videos addressing topics such as nutrition, immunization, and family planning.

“Through empowering community teams with this novel simplified filming and editing process to develop messaging for their own communities, Richard and our team achieved what rarely is achieved in global health — full ownership of a process by the very communities who would then use the output,” said Dr. Kiersten Israel-Ballard, the team lead for Maternal, Newborn, Child Health and Nutrition at PATH and an affiliate professor in the UW Department of Global Health. “As a global health specialist, it is rare to work with a visionary like Richard, who bridges fields and cultures to create innovative solutions. Our work is better having learned from him and his team.”

For the past six years, Anderson has led the development and deployment of open-source software tools for mobile data collection and analysis known as the Open Data Kit (ODK). Initially the brainchild of Anderson’s late friend and colleague Gaetano Borriello, ODK started out as a customizable survey tool designed to be “easy to try, easy to use, easy to modify and easy to scale.” Governments and non-profit organizations in more than 130 countries have relied on successive versions of ODK — including a second-generation version of the toolkit developed under Anderson’s leadership that enabled non-linear workflows and longitudinal surveys — to advance public health, wildlife conservation, election monitoring, essential infrastructure, and more. 

Shortly after taking the helm, Anderson and his collaborators managed the successful transition of ODK from a UW initiative to a stand-alone enterprise. Anderson and his team subsequently extended the original software’s capabilities with the release of ODK-X, which enables users such as PATH, the World Mosquito Program and the International Federation of Red Cross and Red Crescent Societies to build customized Javascript-based apps for managing and visualizing data in the field in addition to the traditional survey forms. Recent applications of ODK-X include vaccine cold-chain management, vector-borne disease monitoring, and humanitarian response.

Anderson has also led the charge to bring secure digital financial services to areas that lack access to traditional banking. In 2016, Anderson and other members of the ICTD Lab joined forces with the Allen School’s Security and Privacy Research Lab to launch the Digital Financial Services Research Group (DFSRG) with the goal of making financial products such as mobile payments and savings accounts more accessible to underserved communities. With funding from the Bill & Melinda Gates Foundation, the DFSRG addresses fundamental challenges to the development and large-scale adoption of digital financial products to benefit some of the lowest-income people in the world to enable them to participate in digital commerce and ensure that, in Anderson’s own words, “an event like an accident or a pregnancy doesn’t send them over the edge.” 

As one of the founding champions of the ICTD movement, Anderson has been instrumental in uniting various communities under the umbrella of ACM COMPASS — short for Computing and Sustainable Societies — and organizing conferences, workshops, and tutorials to engage more researchers, practitioners and students in this work. He has also been a vocal proponent of diversifying host countries to include conference sites such as Ecuador, Ghana and Pakistan. In conjunction with his research and community leadership, Anderson has been credited with demonstrating how to build effective collaborations between computer scientists and non-governmental organizations (NGOs). By combining the former’s technical expertise with the latter’s geographical and domain expertise, Anderson has forged partnerships that ensure solutions developed in the lab can be effectively deployed in the field by people without computing experience — and that they actually address the real-world problems of the people they aim to serve.

“Richard is a top-notch computer scientist and a more than capable teacher, but his real contribution is creating an environment in which CS innovation can be brought to bear on the real problems of real people in developing regions,” said Eric Brewer, a professor of computer science at the University of California, Berkeley who is also Fellow and VP Infrastructure at Google. “His work is inspiring to students across many disciplines, especially when they see the impact of his work on others.”

Anderson joined the Allen School faculty in 1986 after completing a postdoc at the Mathematical Sciences Research Institution in Berkeley, California. He earned his Ph.D. in computer science from Stanford University and his bachelor’s in mathematics from Reed College. Anderson is the first Allen School faculty member to receive the ACM Eugene L. Lawler Award, which is typically given once every two years in honor of an individual or group who has made a significant humanitarian contribution through the application of computing technology.

Read the ACM citation here, and learn more about the Eugene L. Lawler Award here.

Congratulations, Richard!

June 9, 2021

Allen School researchers discover medical AI models rely on “shortcuts” that could lead to misdiagnosis of COVID-19 and other diseases

Chest x-ray
Source: National Institutes of Health Clinical Center*

Artificial intelligence promises to be a powerful tool for improving the speed and accuracy of medical decision-making to improve patient outcomes. From diagnosing disease, to personalizing treatment, to predicting complications from surgery, AI could become as integral to patient care in the future as imaging and laboratory tests are today. 

But as Allen School researchers discovered, AI models — like humans — have a tendency to look for shortcuts. In the case of AI-assisted disease detection, such shortcuts could lead to diagnostic errors if deployed in clinical settings.

In a new paper published in the journal Nature Machine Intelligence, a team of researchers in the AIMS Lab led by Allen School professor Su-In Lee examined multiple models recently put forward as potential tools for accurately detecting COVID-19 from chest radiography (x-ray). They found that, rather than learning genuine medical pathology, these models rely instead on shortcut learning to draw spurious associations between medically irrelevant factors and disease status. In this case, the models ignored clinically significant indicators in favor of characteristics such as text markers or patient positioning that were specific to each dataset in predicting whether an individual had COVID-19. 

According to graduate student and co-lead author Alex DeGrave, shortcut learning is less robust than genuine medical pathology and usually means the model will not generalize well outside of the original setting.

Portrait of Alex Degrave
Alex DeGrave

“A model that relies on shortcuts will often only work in the hospital in which it was developed, so when you take the system to a new hospital, it fails — and that failure can point doctors toward the wrong diagnosis and improper treatment,” explained DeGrave, who is pursuing his Ph.D. in Computer Science & Engineering along with his M.D. as part of the University of Washington’s Medical Scientist Training Program (MSTP). 

Combine that lack of robustness with the typical opacity of AI decision-making, and such a tool could go from potential life-saver to liability.  

“A physician would generally expect a finding of COVID-19 from an x-ray to be based on specific patterns in the image that reflect disease processes,” he noted. “But rather than relying on those patterns, a system using shortcut learning might, for example, judge that someone is elderly and thus infer that they are more likely to have the disease because it is more common in older patients. The shortcut is not wrong per se, but the association is unexpected and not transparent. And that could lead to an inappropriate diagnosis.”

The lack of transparency is one of the factors that led DeGrave and his colleagues in the AIMS Lab to focus on explainable AI techniques for medicine and science. Most AI is regarded as a “black box” — the model is trained on massive data sets and spits out predictions without anyone really knowing precisely how the model came up with a given result. With explainable AI, researchers and practitioners are able to understand, in detail, how various inputs and their weights contributed to a model’s output.

Portrait of Joseph Janizek
Joseph Janizek

The team decided to use these same techniques to evaluate the trustworthiness of models that had recently been touted for what appeared to be their ability to accurately identify cases of COVID-19 from chest radiography. Despite a number of published papers heralding the results, the researchers suspected that something else may be happening inside the black box that led to the models’ predictions. Specifically, they reasoned that such models would be prone to a condition known as worst-case confounding, owing to the paucity of training data available for such a new disease. Such a scenario increased the likelihood that the models would rely on shortcuts rather than learning the underlying pathology of the disease from the training data.

“Worst-case confounding is what allows an AI system to just learn to recognize datasets instead of learning any true disease pathology,” explained co-lead author Joseph Janizek, who, like DeGrave, is pursuing a Ph.D. in the Allen School in addition to earning his M.D. “It’s what happens when all of the COVID-19 positive cases come from a single dataset while all of the negative cases are in another.

“And while researchers have come up with techniques to mitigate associations like this in cases where those associations are less severe,” Janizek continued, “these techniques don’t work in situations you have a perfect association between an outcome such as COVID-19 status and a factor like the data source.” 

The team trained multiple deep convolutional neural networks on radiography images from a dataset that replicated the approach used in the published papers. They tested each model’s performance on an internal set of images from that initial dataset that had been withheld from the training data and on a second, external dataset meant to represent new hospital systems. The found that, while the models maintained their high performance when tested on images from the internal dataset, their accuracy was reduced by half on the second, external set — what the researchers referred to as a generalization gap and cited as strong evidence that confounding factors were responsible for the models’ predictive success on the initial dataset. The team then applied explainable AI techniques, including generative adversarial networks (GANs) and saliency maps, to identify which image features were most important in determining the models’ predictions. 

Figure from paper showing three x-ray images paired with color-coded saliency maps indicating weight of factors in model prediction
The team used explainable AI to visualize the image factors that influenced neural network models’ predictions of COVID-19 status based on chest radiography. Here, saliency maps reveal the models’ tendency to emphasize diagnostically irrelevant features such as laterality tokens, image corners or the patient’s diaphragm in addition to — or instead of — the lung fields when making their predictions.^

When the researchers trained the models on the second dataset, which contained images drawn from a single region and was therefore presumed to be less prone to confounding, this turned out to not be the case; even those models exhibited a corresponding drop in performance when tested on external data. These results upend the conventional wisdom that confounding poses less of an issue when datasets are derived from similar sources — and reveal the extent to which so-called high-performance medical AI systems could exploit undesirable shortcuts rather than the desired signals.

Despite the concerns raised by the team’s findings, DeGrave said it is unlikely that the models they studied have been deployed widely in the clinical setting. While there is evidence that at least one of the faulty models – COVID-Net – was deployed in multiple hospitals, it is unclear whether it was used for clinical purposes or solely for research.

“Complete information about where and how these models have been deployed is unavailable, but it’s safe to assume that clinical use of these models is rare or nonexistent,” he noted. “Most of the time, healthcare providers diagnose COVID-19 using a laboratory test (PCR) rather than relying on chest radiographs. And hospitals are averse to liability, making it even less likely that they would rely on a relatively untested AI system.”

Janizek believes researchers looking to apply AI to disease detection will need to revamp their approach before such models can be used to make actual treatment decisions for patients.

“Our findings point to the importance of applying explainable AI techniques to rigorously audit medical AI systems,” Janizek said. “If you look at a handful of x-rays, the AI system might appear to behave well. Problems only become clear once you look at many images. Until we have methods to more efficiently audit these systems using a greater sample size, a more systematic application of explainable AI could help researchers avoid some of the pitfalls we identified with the COVID-19 models,” he concluded.

Janizek, DeGrave and their AIMS Lab colleagues have already demonstrated the value of explainable AI for a range of medical applications beyond imaging. These include tools for assessing patient risk factors for complications during surgery, which appeared on the cover of Nature Biomedical Engineering, and targeting cancer therapies based on an individual’s molecular profile, as described in a paper published in Nature Communications.

Su-In Lee holding pen with coffee mug and laptop
Su-In Lee

“My team and I are still optimistic about the clinical viability of AI for medical imaging. I believe we will eventually have reliable ways to prevent AI from learning shortcuts, but it’s going to take some more work to get there,” Lee said. “Going forward, explainable AI is going to be an essential tool for ensuring these models can be used safely and effectively to augment medical decision-making and achieve better outcomes for patients.”

The team’s paper, “AI for radiographic COVID-19 detection selects shortcuts over signal,” is one of two from the AIMS Lab to appear in the current issue of Nature Machine Intelligence. Lee is also the senior and corresponding author on the second paper, “Improving performance of deep learning models with axiomatic attribution priors and expected gradients,” for which she teamed up with Janizek, his fellow M.D.–Ph.D. student Gabriel Erion, Ph.D. student Pascal Sturmfels, and affiliate professor Scott Lundberg (Ph.D., ‘19) of Microsoft Research to develop a robust and flexible set of tools for encoding domain-specific knowledge into explainable AI models through the use of attribution priors. Their framework supports the widespread adoption of techniques that will improve model performance and increase computational efficiency in AI for medicine and other areas of applied machine learning. 

Also see a related GeekWire article here.

* Image sourced from the National Institutes of Health (NIH) Clinical Center and used with permission: Wang, X. et al. “ChestX-ray8: Hospital-scale chest X-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.” In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2017. https://nihcc.app.box.com/v/ChestXray-NIHCC

^ Figure 2a (bottom) adapted with permission from Winther, H. et al. COVID-19 image repository. figshare. https://doi.org/10.6084/m9.figshare.12275009

June 1, 2021

Anna Karlin receives ACM Paris Kanellakis Theory and Practice Award

Collage of award recipients' portraits with ACM logo
Top, from left: Yossi Azar, Andrei Broder and Anna Karlin; bottom, from left: Michael Mitzenmacher and Eli Upfal

Professor Anna Karlin and a team of collaborators have received the ACM Paris Kanellakis Theory and Practice Award from the Association for Computing Machinery for their work on balanced allocations, also known as the “power of two choices.” Karlin, a member of the Allen School’s Theory of Computation group, first introduced the balanced allocations paradigm with co-authors Yossi Azar of Tel Aviv University, Andrei Broder of Google Research, and Eli Upfal of Brown University at the 1994 ACM Symposium on Theory of Computing (STOC) in what the ACM has described as “elegant theoretical results” that continue to have a demonstrable impact on the practice of computing. 

The team’s paper considers a basic “balls-in-bins” problem: It has long been known that when n balls are tossed one at a time into n bins, independently and uniformly at random, the expected value of the maximum load is about log(n)/loglog(n). Karlin and her colleagues showed that balancing the allocation of the balls by first selecting not one, but two bins at random, and then placing the ball in the bin that has the lesser load between the two reduces the expected maximum load across all the bins to loglog(n) — an exponential improvement.

Fellow honoree Michael Mitzenmacher of Harvard University later significantly extended these initial results.

“Since bins and balls are the basic model for analyzing data structures, such as hashing or processes like load balancing of jobs in servers, it is not surprising that the power of two choices that requires only a local decision rather than global coordination has led to a wide range of practical applications,” the ACM observed in a press release. “These include i-Google’s web index, Akamai’s overlay routing network, and highly reliable distributed data storage systems used by Microsoft and Dropbox, which are all based on variants of the power of two choices paradigm.”

Karlin’s Allen School colleague, Paul Beame, recalls that it was “stunning and unexpected” that such a simple change in the algorithm would yield such a dramatic improvement — one that has proven to have an enduring impact within the field.

“One can easily ensure balanced allocations if one has prior knowledge about the pattern of requests or some form of centralized control but, without that, finding good balance becomes difficult. The typical solution before the work of Anna and her co-authors allocated each request based on a single random choice of a resource. However, unless the system is vastly over-provisioned, this will result in a somewhat bad overall imbalance,” explained Beame. “What Anna and the team showed is that a simple adjustment — making two random choices rather than just one, and keeping the better of the two — results in an exponential improvement in the overall balance, effectively at most a small constant for all reasonable data sizes.

“In the last couple of decades, their paper has led to much follow-on research,” Beame noted. “The ‘power of two choices’ has since become one of the essential new paradigms in the design of dynamic data structures and algorithms and is regularly taught in graduate courses worldwide.”

Prior to winning the ACM Paris Kanellakis Award, Karlin recently became the first Allen School faculty member to be elected to the National Academy of Sciences for career contributions to algorithms and algorithmic game theory. She is one of two Allen School faculty members to be recognized with ACM technical awards this week, as Shyam Gollakota received the ACM Grace Murray Hopper Award for his work on wireless sensing and communication. 

Read the ACM announcement here, and learn more about the Paris Kanellakis Theory and Practice Award here.

Congratulations, Anna!

May 26, 2021

Shyam Gollakota wins ACM Grace Murray Hopper Award

Portrait of Shyam Gollakota

Allen School professor Shyam Gollakota received the ACM Grace Murray Hopper Award from the Association for Computing Machinery for “contributions to the use of wireless signals in creating novel applications, including battery-free communications, health monitoring, gesture recognition, and bio-based wireless sensing.” Each year, the ACM Grace Murray Hopper Award honors an early-career professional in computing who has made a major technical or service contribution to the field before the age of 35. 

As director of the Allen School’s Networks & Mobile Systems Lab, Gollakota advances big ideas in compact, energy-efficient form factors to expand the Internet of Things (IoT). Among his earliest contributions was ambient backscatter, a groundbreaking technique he pioneered with Allen School colleague and electrical engineering professor Joshua Smith. Backscatter essentially produces power out of thin air by harvesting television, WiFi, and other wireless signals to enable battery-free computation and communication. The team later refined and expanded their work to enable transmissions over greater distances and via embedded devices with long-range backscatter, and even produced a prototype of the world’s first battery-free cellphone. Gollakota also showed how backscatter communication could be accomplished without electronics with the introduction of 3D printed smart objects. The researchers started a venture-backed company, Jeeva Wireless, to commercialize their work.

Gollakota has also tapped into the sensing capabilities of smartphones to develop a series of health screening and monitoring tools in collaboration with clinicians at UW Medicine. These include a non-invasive app for detecting fluid in the ear — a symptom of ear infection and one of the most common reasons for visits to the pediatrician — and one for detecting obstructive sleep apnea that was subsequently commercialized by ResMed. He also showed how smartphones can be powerful tools for tackling broader public health crises with Second Chance, an app that employs sonar to monitor a person’s breathing and movements for signs of a potential opioid overdose. Gollakota and his colleagues have since explored how other smart devices, such as Amazon’s Alexa smart speaker, can be used for home health monitoring. To that end, he and his team have developed new smart speaker skills to detect if a person has an irregular heart rhythm or is experiencing a cardiac emergency and also to monitor a baby’s breathing during sleep. He co-founded two companies, Sound Life Sciences and Wavely Diagnostics, to commercialize this work.

A common thread running throughout Gollakota’s research is his creativity in addressing real-world problems while pushing the limits of what was previously thought possible through technology.

“Simply put, Shyam is amazing — he is easily the most creative person I have ever met,” said Allen School professor Thomas Anderson. “He repeatedly invents and builds prototypes that, before you see them demonstrated, you would have thought impossible. I do not know of any junior faculty member, in any area of computer science, whose work has had greater practical impact on our understanding of how to build useful systems.”

Lately, those systems have bridged the digital and natural worlds in Gollakota’s efforts to enable wireless sensing and computation to take off — literally as well as figuratively. In a series of projects that can be described as “living IoT,” Gollakota and his colleagues attached sensors to bees to demonstrate a system for wireless data transmission with applications in agriculture and environmental monitoring; outfitted a beetle with a steerable robotic camera that can be used to track moving objects and live-stream images to a smartphone; and developed a lightweight sensor that can be transported to hard-to-reach locations by moths in a step towards creating the Internet of Biological Things. Gollakota also has taken inspiration from nature to build insect-sized robots capable of wireless flight in a collaboration with mechanical engineering professor Sawyer Fuller.

“His work has revolutionized and re-imagined what can be done using wireless systems and has a feel of technologies depicted in science fiction novels,” the ACM said of Gollakota in a press release.

The ACM Grace Murray Hopper Award is accompanied by a monetary prize of $35,000, which Gollakota has opted to donate in support of LGBTQIA+ students in the Allen School.

“We are extremely proud of Shyam and his research group. They produce incredibly creative and innovative technology that also strives to address fundamental environmental and societal problems,” said Magdalena Balazinska, professor and director of the Allen School. “On a personal level, I am proud to call Shyam a colleague and am very happy to see him recognized with this award not only for his technical contributions, but also for his service as a mentor and role model for future innovators in our field.”

Gollakota is the second Allen School faculty member to receive the Grace Murray Hopper Award. The ACM previously recognized professor Jeffrey Heer in 2017 for his work on leading-edge visualization tools for exploring and understanding data.

Read the ACM announcement here, and learn more about the Grace Murray Hopper Award here. In addition, see our story on professor Anna Karlin receiving the ACM Paris Kanellakis Theory and Practice Award, also announced today, for her work on balanced allocation or the “power of two choices.”

Congratulations, Shyam!

May 26, 2021

Shayan Oveis Gharan receives EATCS Presburger Award for groundbreaking contributions to the Traveling Salesperson Problem

Portrait of Shayan Oveis Gharan

Professor Shayan Oveis Gharan, a member of the Allen School’s Theory of Computation group, earned the 2021 Presburger Award for Young Scientists from the European Association for Theoretical Computer Science (EATCS) for his research on the Traveling Salesperson Problem (TSP). Each year, the EATCS bestows the Presburger Award on an early-career scientist who has made outstanding contributions in the field of theoretical computer science. In its unanimous selection of Oveis Gharan for this year’s honor, the award committee heralded his “creative, profound, and ambitious” work on a fundamental problem that has advanced scientists’ understanding of the design and analysis of algorithms.

“Shayan is a leader in the application of algebraic and spectral methods to classical problems in combinatorial optimization, and he’s the architect of a series of surprising and profound developments in the theory of algorithms,” said Allen School professor James Lee. “He exhibits a remarkably consistent ability to make progress on important problems that had remained open for decades.”

That progress began when Oveis Gharan was a Ph.D. student at Stanford University, where he and his collaborators produced an approximation algorithm that offered the first asymptotic improvement on TSP in the asymmetric case in three decades. It has culminated — so far, at least — in the first performance improvement on metric TSP in nearly half a century. In between, Oveis Gharan also contributed to the first improvement over Christofides’ 3/2-approximation for the symmetric graph case of TSP, first put forward in 1976, in what the Presburger Award committee describes as a “remarkable tour de force.” Over the course of his career, Oveis Gharan has continued to develop and expand the concept of “negative dependence” between the presence of edges in a certain distribution on random spanning trees of a graph — a tool he first applied to great effect in his initial contribution to TSP as a student — to push the field forward. 

For his latest milestone, Oveis Gharan worked with Allen School Ph.D. student Nathan Klein and faculty colleague Anna Karlin to devise an approximation algorithm capable of returning a solution that surpasses 50% of the optimum for the very first time. The team will receive a Best Paper Award at the Association for Computing Machinery’s upcoming Symposium on the Theory of Computing (STOC 2021) for their groundbreaking achievement. According to Karlin, Oveis Gharan stands out not only for his technical contributions, but also for the way he approaches his research.

“Shayan is an exceptionally brilliant, ambitious and fearless researcher,” said Karlin. “What blows my mind is that, on top of all of that, he is also one of the kindest, most generous people I know. Every meeting with Shayan and our students lifts my spirits because he brings such enthusiasm, warmth and positivity to his work.”

The central question of TSP — how to determine the shortest and most efficient route between multiple destinations and back to the starting point — is more than a theoretical problem. It has multiple real-world applications across a variety of domains, from planning and scheduling, to supply chain logistics, to microchip manufacturing. It also has provided an ideal vehicle for Oveis Gharan to apply his expertise in analysis, probability and combinatorics to push the theoretical limits of computation and enable progress in other fields while providing the inspiration and the tools for other young researchers to follow his lead.

“Shayan’s enthusiasm for what he does is infectious, and he has helped me gain a new appreciation of computer science. He communicates to his students a strong sense that we are not here just to solve problems but to learn, grow, and discover new ideas,” Klein said. “He also has a great ability to zoom out and synthesize. For example, during the TSP project I came to him with a mess of proofs of a dozen probabilistic lemmas we needed. He immediately recognized a common theme and extracted an elegant theorem that characterized all of these lemmas and more. This theorem ended up being quite useful in guiding our understanding for the remainder of the project.”

While the challenge of TSP may hold particular fascination for Oveis Gharan, it is not the only open problem on which he has made notable progress in recent years. In 2019, he earned a STOC Best Paper Award for his work with Allen School Ph.D. student Kuikui Liu and collaborators on the first fully polynomial randomized approximation scheme (FPRAS) for counting the bases of a matroid. Drawing from several seemingly unrelated areas of mathematics and theoretical computer science — namely Hodge theory for combinatorial geometries, analysis of Markov chains, and high dimensional expanders — the team applied a novel theory of spectral negative dependence to prove a conjecture by Mihail and Vazirani that had remained an open question for 30 years. As a follow-up, members of that team applied some of those same insights to sampling an independent set from the hardcore model. Their results addressed a 25-year-old open problem concerning the mixing time of Glauber dynamics by proving that, for any graph, they mix in polynomial time up to the tree uniqueness threshold.

Since his arrival at the University of Washington in 2015, Oveis Gharan has earned a Sloan Research Fellowship, a CAREER Award from the National Science Foundation, an ONR Young Investigator Award from the Office of Naval Research, and a Google Faculty Research Award. In 2016, Science News magazine named him one of “10 Scientists to Watch” for his work on TSP. Oveis Gharan will collect his latest honor virtually during the upcoming annual meeting of the EATCS, the International Colloquium on Automata, Languages and Programming (ICALP 2021), in July.

Read the EATCS announcement here, and learn more about the Presburger Award here.

Congratulations, Shayan!

May 20, 2021

GeekWire recognizes Allen School’s Lauren Bricker as STEM Educator of the Year

Portrait of Lauren Bricker

Allen School teaching professor and alumna Lauren Bricker (Ph.D., ’98) received a STEM Educator of the Year Award from GeekWire for her leadership in advancing computer science education. Bricker is one of three local education leaders to be recognized with the award, which GeekWire created this year to honor innovative educators in the Pacific Northwest who are inspiring students to achieve more in the areas of science, technology, engineering and math.

“If Pacific Northwest computer science education was a solar system, Lauren Bricker could arguably play the role of the sun,” GeekWire’s Lisa Stiffler wrote in an article highlighting the honorees. “Her efforts to reach students from K-12 to college have shone a light into far-reaching and diverse stretches of the educational system.”

Bricker’s orbit extends far beyond the classroom to encompass the design of computer science courses for the Washington State Academic Redshirt (STARS) program at the University of Washington, outreach to K-12 classrooms through the UW in the High School and Allen School ambassadors programs, curriculum development for Code.org, and leadership and advocacy in her role as President of the Puget Sound Computer Science Teachers Association (CSTA). According to Bricker’s colleague Dan Grossman, professor and vice director of the Allen School, only a fraction of her role fits into the conventional mold of a UW teaching professor; in fact, he says, Bricker joined the faculty in 2017 in part to be a major conduit between the Allen School and K-12 educators across Washington state.

“Lauren is an unheralded hero of computer science education in the Pacific Northwest, filling a role that improves high-school computing education, improves university computing education, and connects the two in totally unique and crucial ways,” said Grossman. “What’s more, Lauren approaches all of her work through the lens of diversity, equity, and inclusion. To her, access to computing courses is but the starting point, where the real goal is for everyone — particularly those who never saw themselves as computer scientists — to thrive.”

To that end, one of Bricker’s signature contributions has been her leadership of multiple efforts aimed at expanding support at UW for students from low-income, first-generation, and underserved backgrounds to be successful in computer science and other engineering-related disciplines. Bricker developed and teaches the introductory computer science course for the College of Engineering’s STARS program, which supports incoming engineering and computer science students by strengthening academic preparation for core mathematics and science prerequisites as well as building the skills and support systems they need to excel in college-level work. Bricker also works closely with students in the Allen School’s Startup program. Each year, Startup provides ongoing support to incoming freshmen who were admitted directly into the computer science or computer engineering major and who are from underserved communities and/or have had limited programming experience.

As the faculty lead for Startup, Bricker has been instrumental in crafting the curriculum for the program’s intensive, four-week pre-autumn course that immerses students in learning foundational computer science concepts, building their critical thinking and problem solving skills, and preparing them for the transition from high school to college. She also has contributed to workshops designed to reinforce core concepts for students during their freshman year. Bricker, whose own journey to higher education included plans to enroll in medical school before she eventually became “hooked” on computers, is motivated in part by a recognition that many students do not enjoy the same advantages she had growing up.

“I lived in a college town. I went to an academically focused high school. I had access to computers and advanced math classes,” Bricker explained. “I also had access to a once-a-week outreach event to encourage women in the medical fields, and my parents encouraged me in the areas I wanted to study. I realize what a privilege that was and how not everyone gets those privileges. I just want to share the good fortune I had.”

A self-described “geek generator,” Bricker brings a personal touch — not just a pedagogy — that has made a difference for students just starting out in computer science. Said one former Startup student of Bricker’s, “I’d go to office hours sometimes and she’d explain the concept to me in a different way so I could understand it better. I really appreciated having her as my professor, she’s the best I’ve had!”

Another former student who later served as a teaching assistant for Startup noted that Bricker’s willingness to meet students where they are, with lessons and examples that are personally meaningful to them, has been especially important in the context of remote learning during the Covid-19 pandemic.

“I’ve had the opportunity to work with Lauren as a TA during online learning and seen her adapt in a way that keeps students engaged,” sophomore Karman Singh said. “She takes the time to walk through exercises so that everyone can understand. She lets students control their learning by having them participate in interactive activities, lead group projects, and create demonstration videos.”

Group of smiling students posing on concrete stairwell with trees and the Paul G. Allen Center in the background
Students in the Allen School’s 2019 Startup cohort on the UW Seattle campus

According to Singh’s classmates Kashish Aggarwal and Jessica Louie, Bricker helps students do more than grasp the material — she also instills a level of comfort and confidence that they can carry with them throughout the remainder of their time at the UW. 

“I was constantly reminded of how skilled Professor Bricker was in her field, but also how incredible she was with working with students,” recalled Aggarwal. “Always encouraging and working with her students, she always had a smile on her face, never giving up on anyone. She helped me gain more confidence in my abilities and resilience in my work.”

“She is great at breaking down difficult topics to digestible and easy-to-learn parts,” Louie said of Bricker’s teaching style. “She is also super approachable and down to earth, which helped me overcome a fear of speaking with professors. I admire her knowledge and ability to make students feel comfortable around her.”

Startup co-instructor Leslie Ikeda, an academic adviser in the Allen School, credits Bricker with playing a key role in the growth and success of the program since the latter first became involved in 2018.

“Lauren is a fierce innovator and educator, and she is relentless in her commitment to supporting students who have been historically underrepresented in computing,” Ikeda said. “Lauren fosters inquiry and creativity through her curriculum and thinks intentionally about how our Startup students can bring themselves — their identities, experiences, values and interests — into their technical projects. Her enthusiasm and passion for teaching is felt by each of her students, and I am grateful to have had the opportunity to work alongside Lauren and witness her incredible work.”

Sonya Cunningham, executive director of the STARS program, agreed, noting that students are inspired by Bricker in part because they can tell she genuinely cares about them as individuals.

“If a student really wants to learn about computer science, Lauren never gives up on them. She will spend as much extra time as needed to help them succeed,” said Cunningham. “I have seen her do this several times with STARS students who were really struggling. As a result of her patience and willingness to go the extra mile, I’ve witnessed amazing turnarounds in our students’ confidence as well as their enthusiasm and love for computer science.

“By teaching students how to learn, how to embrace change, and how to remain flexible and adaptable, Lauren inspires our students to work hard and bring their best,” Cunningham continued. “Under her guidance, STARS students do really well in the computer science gateway courses. We feel lucky to have Lauren as a part of the STARS team!”

In addition to her teaching and K-12 outreach on behalf of the Allen School, Bricker has co-led multiple teacher training workshops for Code.org and contributed to the development of the organization’s Computer Science Discoveries curriculum currently in use by tens of thousands of middle school students around the world. Before joining the Allen School faculty, Bricker spent 20 years in industry in various software engineering, management and consulting roles and 10 years as a teacher at Seattle’s Lakeside School, where she developed and taught honors-level computer science courses to students in grades 9–12 as well as advanced courses in mobile, web and Arduino development and 3D printing and modeling. While at Lakeside, Bricker also spent three years restructuring and teaching a course that introduced students to programming in the 7th grade. 

Bricker herself has learned some valuable lessons over the years when it comes to strategies for engaging more underrepresented students in STEM education and careers.

“We should ‘decenter’ the curriculum by allowing students’ voices to be heard through projects that engage with their own interests. Moreover, make that curriculum relevant by connecting it to real-world problems,” Bricker explained. “We also need to expand representation in the classroom. It’s critically important that we encourage teachers from diverse backgrounds to learn how to teach STEM fields and to feel confident in teaching them.”

Bricker and fellow STEM Educator of the Year honorees Cathi Rodgveller and Kim Williams will be recognized during the 2021 GeekWire Awards celebration on May 20th. Rodgveller founded the organization IGNITE Worldwide to engage more women and girls in STEM education and careers. Williams is a science teacher who serves as the department head and Science Club faculty advisor at Cougar Mountain Middle School in the Bethel School District.

“I am grateful to know Lauren as a student, teaching assistant, and as someone I can connect with at any time,” Singh said. “She puts so much effort into her teaching and making sure all students can understand various concepts. She takes inclusion, equity, individual learning, and growth mindset to heart.

“I can honestly say that she is one of the best teachers I have met.”

Read more about the STEM Educator of the Year Awards and listen to a podcast featuring the honorees discussing the future of learning courtesy of GeekWire.

Way to go, Lauren!

May 14, 2021

Professor Anna Karlin elected to the National Academy of Sciences

Portrait of Anna Karlin

Professor Anna Karlin of the University of Washington’s Theory of Computation group recently became the first Allen School faculty member to be elected a member of the National Academy of Sciences. Karlin, who holds the Bill & Melinda Gates Chair in Computer Science & Engineering and serves as Associate Director for Graduate Studies at the Allen School, was honored for her significant contributions to algorithms and algorithmic game theory. She joins a distinguished community of scholars elected by their peers to advise the nation on matters related to science and technology while promoting education and research.

Much of Karlin’s early research was focused on online and probabilistic algorithms and analysis. Online algorithms receive a series of inputs over time, and must make decisions as each input arrives, without the benefit of information about future inputs. Karlin and her collaborators Mark Manasse, Larry Rudolph and Daniel Sleator coined the phrase “competitive algorithm” to describe an online algorithm that achieves the provably best possible performance compared to the clairvoyant optimal result — in other words, performs nearly as well as if decisions were made with full knowledge of the future. 

A useful abstraction and simple illustrative example is the ski rental problem. “When you start out skiing, you don’t know if you’ll love it or hate it or how many times you will end up going,” Karlin explained. “And yet, each time you head out, you have to make a decision: should you rent or should you buy?

“If you rent until the total amount you’ve spent equals the cost of buying skis,” she went on, “you will never pay more than twice what the optimal clairvoyant would have paid. More interesting is that using randomization reduces this factor of 2 down to e/(e-1), which is about 1.58. And it turns out that both of these bounds are provably optimal.”

Karlin and various co-authors applied this style of analysis to achieve optimally competitive algorithms for a number of problems including memory management, load balancing, and transmission control protocol (TCP) acknowledgement. 

Her research on paging and caching naturally led her into collaborations with systems researchers on various other memory management problems. For example, in work with Pei Cao, Edward Felten (Ph.D., ‘93) and Kai Li that received a Best Paper Award at the 1995 ACM SIGMETRICS Conference, she studied optimal integrated strategies for prefetching and caching. The team complemented its theoretical analysis with simulations showing that the new strategies proposed were able to reduce the running time of applications by up to 50%. Karlin and her student Tracy Kimbrel (Ph.D., ‘97) subsequently extended the theoretical results to prefetching and caching from multiple parallel disks. In another example, Karlin worked with Alec Wolman (Ph.D., ‘02), Geoff Voelker (Ph.D., ‘00), Nitin Sharma (M.S., ‘98), Neal Cardwell (M.S., ‘00) and faculty colleague Hank Levy to demonstrate the limitations of web proxy cache sharing among organizations.

A favorite topic of Karlin’s throughout her career has been probabilistic algorithms and analysis. One of her most impactful results in this area emerged from a collaboration with Yossi Azar, Andrei Broder and Eli Upfal on “Balanced Allocations,” which has come to be known as the “power of two choices.” This paper considers a basic “balls-in-bins” problem: It has long been known that when n balls are tossed one at a time into n bins, independently and uniformly at random, the expected value of the maximum load is about log(n)/loglog(n). Karlin and her co-authors showed that if, when placing each of the n balls into a bin, two random bins are selected and then the ball is placed in the less loaded bin, this maximum load drops to loglog(n) — an exponential improvement. 

“Balls-in-bins problems are ubiquitous in computer science,” said Karlin, “and the ‘power of two choices’ paradigm has turned out to be useful in a variety of applications, from hashing and load balancing to network and data center management.”

In 1999, Karlin became excited by work on “Competitive Auctions and Digital Goods” that her student Jason Hartline (Ph.D., ‘03) had done with Andrew Goldberg and Andrew Wright during a summer internship at InterTrust Technologies’ STAR Lab. That work, which recently earned the 2021 SIGECOM Test of Time Award for “initiating a long and fruitful line of work in approximately revenue-optimal auction design in prior free settings,” inspired Karlin to turn her attention to auction theory and, more generally, the field of mechanism design. Mechanism design applies the tools of game theory to design systems in which rational participants intent on maximizing their own self-interest will also achieve the designer’s intended goal. Potential applications run the gamut from network traffic routing and scheduling tasks in the cloud, to ecommerce and search engine advertising — all of them enabled by the rise of the internet.

“Nowadays, pretty much any real algorithmic problem that arises in a distributed setting is in fact a mechanism design problem,” Karlin noted.

The implications of Karlin’s work in this area extends to multiple industries in which the provision of goods and services depends on finding the ideal balance between pricing and profit given available resources and consumer motivations. For example, in joint work with Shuchi Chawla, Nikhil Devanur and Balasubramanian Sivan, she considered the design of “pay-per-play” pricing of songs, apps, video games and other software for consumers whose value for such a digital good evolves as they use it according to a stochastic process known as a martingale. In contrast to the standard approach to selling goods, where the buyer purchases an item and then can use it an unlimited number of times, in this form of pricing the buyer pays a little bit each time they want to use it. This enables a seller to extract different amounts of money from different consumer types based on how long and to what extent they remain interested in the product, as opposed to the one-price-fits-all model. 

“We showed that using a free trial period followed by a fixed posted price for each use yields near-optimal profit for such digital goods — and one which is, generally speaking, significantly higher than that obtained using other pricing methods,” Karlin said. “Pay-per-play has the added advantage of being risk-free to the consumer, since they can stop buying that app, game or song whenever they lose interest.”

In another paper, Karlin worked with Kira Goldner (Ph.D. ‘19), Amos Fiat and Elias Koutsoupias to solve the “FedEx problem,” wherein the seller has to balance maximizing revenue with customer expectations related to service quality and cost. Sellers tend to have a variety of options available to them for responding to price sensitivity and other customer-driven factors, including market segmentation, differential pricing, or lower-cost (and presumably lower-quality) versions of a product or service. Karlin and her collaborators came up with the optimal approach for the seller to extract maximum revenue in instances where customer values such as desired delivery time or other factors are drawn from known probability distributions.

Despite its name, like many of the questions Karlin has tackled in her career, the results on the FedEx problem are more broadly applicable to a variety of domains. This also holds true for her work on novel algorithmic mechanisms for maximizing social welfare in the pricing of goods with the prospect of resale with Goldner, Fiat, Alon Eden and Michal Feldman. In this case, the team addressed a scenario known as the interdependent value setting, which captures the fact that information one prospective buyer has about goods being sold may significantly affect the value other buyers have for those goods. The researchers used the example of auctioning off oil drilling rights on a piece of land, where geologic surveys done by one prospective buyer contain information that could significantly sway the interests of another prospective buyer. 

Anna Karlin and Kira Goldner, the latter wearing Ph.D. regalia
Karlin with newly-minted Ph.D. Kira Goldner at the Allen School’s 2019 graduation celebration

The decades-old economics literature on this problem had yielded strong impossibility results, even in extremely simple scenarios such as selling a single item. Karlin and her co-authors were able to circumvent these negative results using a combination of randomization and approximation, obtaining the first positive results for a broad class of combinatorial auctions — and earning the award for Best Paper with a Student Lead Author at the 20th Conference on Economics and Computation (EC ‘19)

Other problems Karlin has considered include pricing and resource allocation in the cloud, sponsored search auction design and analysis, minimizing cost in procurement auctions such as “buying” a shortest path in a network or a spanning tree, strategic behavior of Bitcoin miners, and the design of auctions that achieve near-optimal performance in the presence of a Bayesian prior without actually knowing the prior. Inspired by the Mechanism Design for Social Good initiative, initially founded by her former student Goldner and Rediet Abebe, going forward, Karlin aims to build on past work and apply her expertise in mechanism design and modern matching markets to domains such as health care, energy, and the gig economy.

Along with advancing new algorithms for mechanism design, Karlin is also interested in pushing the field forward by addressing long-standing problems that underpin the theory and practice of computing. In what is likely to be the most influential result of her career, last year she worked with current Ph.D. student Nathan Klein and faculty colleague Shayan Oveis Gharan to achieve the first improved approximation algorithm for the Traveling Salesperson Problem (TSP) in over 40 years. TSP — which aims to find the most efficient route across multiple points and back to the start — is a fundamental question with real-world implications ranging from transportation and logistics, to genomics and circuit board design. TSP is also a cornerstone problem in theoretical computer science, the study of which has led to the development of many foundational algorithmic techniques.

“TSP is NP-complete, so the holy grail has been to design an efficient approximation algorithm that is guaranteed to get a nearly optimal solution,” Karlin explained. “In the 70s, researchers discovered an algorithm that always guarantees a solution whose cost is never more than 50% higher than optimum. Nathan, Shayan and I were finally able to surpass the 50% threshold, which hopefully will pave the way for even greater progress down the road.”

According to Oveis Gharan, Karlin stands out not only for being a gifted theoretician but also for her eagerness to embrace unfamiliar ideas and learn alongside her students.

“I have worked with a few senior researchers in my career, but Anna is perhaps the only one who gets so excited and spends a significant amount of time learning new ideas and new techniques outside of her comfort zone,” Oveis Gharan said. “This is a great motivation for graduate students who are just starting out to learn new techniques together with their advisor and to build their self-confidence as researchers.”

Karlin’s enthusiasm for helping students to explore new ideas inspired her to co-author the book Game Theory, Alive with mathematician Yuval Peres. Published by the American Mathematical Society in 2017, the book presents the mathematical concepts that underpin game theory in an approachable and engaging way, including anecdotes, illustrations, and profiles of the individual mathematicians, statisticians, and economists credited with advancing the field.

“Game theory’s influence is felt in a wide range of disciplines, and the authors deliver masterfully on the challenge of presenting both the breadth and coherence of its underlying world-view,” Cornell professor Jon Kleinberg wrote. “The book achieves a remarkable synthesis, introducing the reader to the blend of economic insight, mathematical elegance, scientific impact, and counter-intuitive punch that characterizes game theory as a field.”

Cover of Game Theory, Alive!

Karlin’s research career began at Stanford University, where she earned her bachelor’s degree in applied mathematics before earning her Ph.D. in computer science. Following a postdoc at Princeton University, Karlin spent six years as a principal scientist at DEC’s Systems Research Center. While it became clear early on that she would be a “rock star” in the field of computing, Karlin was also an actual rock star wannabe; in 1993, she took part in the first musical performance to be live-streamed on the internet with the band Severe Tire Damage — although, as Karlin herself says with a smile, “just because we were first doesn’t mean we were any good.” 

Shortly thereafter, she left Palo Alto for Seattle to join the UW as a visiting professor in 1994. She made the move permanent two years later.

“I’m so honored to receive this recognition,” said Karlin. “All I can say is that my good fortune is due to the many brilliant colleagues and students I’ve had the pleasure of collaborating with during my career.”

Karlin is one of 120 leading scholars and scientists to be elected full members of the NAS and among a record-high 59 women recognized in the 2021 class. The Academy elected another 30 non-voting international members, bringing the total honorees to 150.

“We are incredibly proud of Anna for being elected to the National Academy of Sciences,” said Magdalena Balazinska, professor and director of the Allen School. “Anna is a tremendously talented researcher. She’s also a dedicated colleague and deeply caring teacher and mentor. She’s an inspiration to all of us.”

Karlin was previously elected Fellow of the American Academy of Arts & Sciences and of the Association for Computing Machinery. She is the fifth Allen School faculty member to be elected a member of the National Academies, joining professors Tom Anderson, Ed Lazowska, and Hank Levy and professor emeritus Susan Eggers — all of whom were inducted into the National Academy of Engineering.

Read the NAS announcement here.

Congratulations, Anna!

May 4, 2021

Taskar Center researchers offer a roadmap for more robust modeling of pedestrian mobility on a city-wide scale

Side by side maps of Seattle color-coded based on normalized sidewalk reach between normative walking profile and manual wheelchair user profile. The map on the left shows more extensive NSR for the normative walking profile compared to the map on the right.

Many approaches to measuring and supporting city-wide mobility lack the level of detail required to truly understand how pedestrians navigate the urban landscape, not to mention the quality of their journey. Transit apps can direct someone to the nearest bus stop, but they may not account for obstacles or terrain on the way to their destination. Neighborhood walkability scores that measure proximity to amenities like grocery stores and restaurants “as the crow flies” are useful if traveling by jetpack, but they are of limited benefit on the ground. Even metrics designed to assist city planners in complying with legal requirements such as the Americans with Disabilities Act are merely a floor for addressing the needs of a broad base of users — a floor that often fails to account for a wide range of mobility concerns shared by portions of the populace.

Now, thanks to the Allen School’s Taskar Center for Accessible Technology, our ability to envision urban accessibility is taking a significant turn. In a paper recently published in the journal PLOS ONE, Allen School postdoc and lead author Nicholas Bolten and Taskar Center director Anat Caspi propose a framework for modeling how people with varying needs and preferences navigate the urban environment. The framework — personalized pedestrian network analysis, or PPNA — offers up a roadmap for city planners, transit agencies, policy makers, and researchers to apply rich, user-centric data to city-scale mobility questions to reflect diverse pedestrian experiences. The team’s work also opens up new avenues of exploration at the intersection of mobility, demographics, and socioeconomic status that shape people’s daily lives.

Portrait of Anat Caspi outdoors standing in front of foliage
Anat Caspi

“Too often, we think about environments and infrastructure separately from the people who use them,” explained Caspi. “It’s also the case that conventional measures of pedestrian access are derived from an auto-centric perspective. But whereas cars are largely homogeneous in their interactions with the environment, humans are not. So what we tend to get is a high-level picture of pedestrian access that doesn’t adequately capture the needs of diverse users or reflect the full range of their experiences. PPNA offers a new approach to pedestrian network modeling that reflects how humans actually interact with the environment and is a more accurate depiction of how people move from point A to point B.”

The PPNA framework employs a weighted graph-based approach to parameterize individual pedestrians’ experiences in navigating a city network for downstream analysis. The model accounts for the variability in human experience by overlaying the existing network infrastructure with constraints based on pedestrian mobility profiles, or PMPs, which represent the ability of different users to reach or traverse elements of the network. 

To illustrate, the team applied PPNA to a section of downtown Seattle streets using PMPs for a stereotypical normative walking profile and one representing powered wheelchair users to determine their walkshed. A walkshed is a network-based estimation of pedestrian path reachability often used by transit agencies to define a service area in relation to a particular point of interest. But whereas the typical walkshed analysis applies a one-size-fits-all approach to evaluate access, PPNA enables multiple estimates tailored to the needs and constraints of each pedestrian profile. In this case, the researchers revealed roughly one-third of the normative walking walkshed to be inaccessible to users of powered wheelchairs. 

Based on their analysis, the team introduced the concept of normalized sidewalk reach, an alternative measure of sidewalk network accessibility designed to overcome biases inherent in walkshed analysis and other conventional approaches. This new, improved analysis accounts not only for the infrastructure present in the environment, but also its applicability to the humans who use it. According to Bolten, the proliferation of user data combined with new technologies have made it possible to perform such analyses at a greater level of detail than ever before.

Portrait of Nicholas Bolten standing outside with water and pebbly beach in the background
Nicholas Bolten

“Crowdsourcing efforts like the OpenStreetMap initiative and emerging computer vision techniques are improving our ability to collect detailed pedestrian network data at scale. In addition, growing use of location tracking technologies and detailed surveys are enhancing our ability to model pedestrian behaviors and needs,” explained Bolten, who began working with Caspi while earning his Ph.D. from the University of Washington Department of Electrical & Computer Engineering. “By combining more detailed pedestrian network data with more robust characterizations of pedestrian preferences, we will be able to account for needs that may have been overlooked in the past while supporting the investigation of complex urban research questions.”

Among these potential questions is how connectivity for specific pedestrian profiles intersects with demographics and/or unequal access to services and amenities. For example, the authors envision that PPNA could be applied to identify where poor connectivity for one group of users overlaps with areas designated as food deserts. 

While the authors focused primarily on pedestrian mobility, given that such concerns tend to be overlooked or dealt with only superficially, they note that their approach could be expanded to cover other aspects of the pedestrian experience. Additional criteria could include the perceived pleasantness of a trip, how crowded a route may be, noise levels, and more.

Side-by-side map showing results of walkshed analysis for two pedestrian profiles, color-coded to indicate accessible paths for each. The map on the left has roughly one-third more paths designated accessible compared to the map on the right.
PPNA-based walkshed analysis of downtown Seattle for a stereotypical normative walking profile (left) and powered wheelchair user (right). The blue lines indicate the paths accessible to each category of user.

“When it comes to understanding how people traverse their communities, there is a vast range of user needs and preferences that are ripe for investigation to help decision-makers move beyond a one-size-fits-many approach,” observed Caspi. “By introducing quantitative measures of diverse pedestrian concerns, we can gain deeper insights into which needs are being considered and which are not across a city’s network. We hope to continue to grow our engagement with the Disability community along with city and transportation planners, to increase use of data-driven methods towards building sustainable, accessible communities.”

This latest work is a natural outgrowth of the Taskar Center’s OpenSidewalks project, which focuses on understanding and improving the pedestrian experience through better data collection. Caspi and her team also recently launched the Transportation Data Equity Initiative in collaboration with the Washington State Transportation Center (TRAC) and other public and private partners to improve data standards and extend the benefits of new mobility planning tools to underserved groups.

Read the PLOS ONE paper here, and learn more about the Transportation Data Equity Initiative here. Stakeholders who are interested in learning more or contributing to this ongoing work can contact the team here.

April 2, 2021

Allen School faculty honored by the Association for Computing Machinery for advancing probabilistic robotics, internet-scale systems, and more

Association for Computing Machinery logo

Allen School professors Dieter Fox and Arvind Krishnamurthy recently attained the status of Fellows of the Association for Computing Machinery in honor of their influential contributions to robotics and computer vision and to systems and networking, respectively. Each year, the ACM bestows the designation of Fellow on a select group of members to recognize their impact through research and service based on nominations submitted by their peers in the computing community.

According to ACM President Gabriele Kotsis, in 2020 the organization received a record number of nominations from around the world aiming to highlight individuals who have made “pivotal contributions to technologies that are transforming whole industries, as well as our personal lives.” The ACM’s recognition of Krishnamurthy and Fox brings the number of Allen School faculty members elevated to Fellow to 26. Allen School affiliate professor Meredith Ringel Morris, an expert in human-computer interaction and accessibility at Microsoft Research, and former Allen School professor Steve Gribble, now a distinguished engineer focused on networked systems at Google, joined Fox and Krishnamurthy among the 95 researchers worldwide to be recognized for their achievements in the new class of Fellows.

Dieter Fox

Portrait of Dieter Fox

Dieter Fox was elevated to the status of ACM Fellow for “contributions to probabilistic state estimation, RGB-D perception, and learning for robotics and computer vision.” Fox’s work, which spans roughly 25 years, has had an influential impact across multiple areas, opened up new avenues of research, and helped establish the University of Washington as a leader in robotics and artificial intelligence research.

Fox currently serves as director of the Allen School’s Robotics and State Estimation Laboratory and senior director of robotics research at NVIDIA. He joined the UW faculty in 2000 after earning his Ph.D. from the University of Bonn in Germany and completing a postdoc at Carnegie Mellon University. Fox was among the pioneers of probabilistic robotics, for which he co-authored a textbook of the same name, which aims to address problems in perception and control to endow robots with the ability to interact with people and their environment in an intelligent way. 

Among Fox’s contributions is a series of novel techniques for Bayesian state estimation that have resulted in significant advancements across a variety of domains, including object manipulation, human activity recognition, and localization and mapping. For the latter — one of the fundamental problems in robotics — Fox’s early work on Markov localization in dynamic environments is considered to be a significant milestone. He and his colleagues built on that work with the introduction of Monte-Carlo Localization, a technique that broke new ground with its use of sampling-based methods that proved to be more accurate, more computationally efficient, and easier to implement than previous approaches. MCL subsequently became the preferred approach in the field, and today localization is widely regarded as a solved problem in robotics.

In another series of firsts, Fox contributed to new systems for achieving robust 3D-mapping capabilities using RGB-D cameras and advancing robot learning by incorporating model-based information into deep learning approaches. In a paper that combined insights from robotics and computer vision, Fox and colleagues in the Allen School’s Graphics & Imaging Laboratory (GRAIL) presented DynamicFusion, the first dense simultaneous localization and mapping (SLAM) system capable of producing detailed and complete reconstructions of subjects in motion, and in real time. Fox and collaborators subsequently leveraged that capability to automate the generation of robust visual training data from RGB-D video in order to take advantage of new deep learning techniques. The resulting framework enabled robots to learn rich visual features of objects and people in their environment in a self-supervised way. Self-supervised learning has since emerged as a highly active area of robotics research.

Over the course of his career, Fox has earned multiple Best Paper and Test of Time Awards at the preeminent research conferences in artificial intelligence, robotics, computer vision, and ubiquitous computing. Prior to his election as a Fellow of the ACM, Fox attained the status of Fellow of both the Association for the Advancement of Artificial Intelligence (AAAI) and the Institute for Electrical and Electronics Engineers (IEEE). Last year, Fox earned the IEEE Robotics & Automation Society’s RAS Pioneer Award in acknowledgment of his groundbreaking contributions to state estimation, robot perception and machine learning as well as his efforts to bridge academic and industrial research through his many collaborations with Intel, NVIDIA, and other partners.

Arvind Krishnamurthy

Portrait of Arvind Krishnamurthy

Arvind Krishnamurthy was named a Fellow of the ACM for “contributions to networks and distributed computer systems.” Krishnamurthy’s research advances state-of-the-art approaches for building robust and efficient computer systems to support data center operations and internet-scale computing. His work encompasses topics such as internet measurement and reliability, peer-to-peer data sharing, data center performance, network routing, and systems for bridging the gap between machine learning and hardware innovation. 

After earning his Ph.D. at the University of California, Berkeley in 1999, Krishnamurthy began his career as a faculty member at Yale University. Since joining the Allen School faculty in 2005, Krishnamurthy has focused on advancing new network primitives, protocols and services to make the internet more reliable and resilient and to optimize distributed and networked systems inside data centers. Krishnamurthy ‘s work has earned multiple awards at the preeminent conferences in operating and networked systems, including five Best Paper or Best Student Paper designations at the Symposium on Networked Systems Design and Implementation (NSDI). 

One of Krishnamurthy’s contributions to be singled out by NSDI was Reverse Traceroute, the first tool for diagnosing internet performance issues that expanded upon existing capabilities for tracing packets from source to destination to include their asymmetric return paths. The tool gained popularity for troubleshooting performance problems within corporate internal networks as well as on the internet. Three years later, Krishnamurthy and his collaborators presented their award-winning paper describing F10, a fault-tolerant network designed explicitly for the data-center setting to improve the reliability and performance of applications in the cloud. Consisting of a novel network topology and failover protocols designed to cascade and complement each other, F10 proved capable of reestablishing connectivity and load balance almost instantaneously, even in the presence of multiple failures.

Krishnamurthy was also a member of the team behind a novel operating system designed to address recent application and hardware trends that are hampered by the traditional operating-system model. In proposing Arrakis, which earned the Best Paper Award at the 2014 conference on Operating Systems Design and Implementation (OSDI), Krishnamurthy and his collaborators re-engineered the OS kernel to provide network and disk protection without requiring mediation of every operation. As a result, most applications are able to bypass the kernel entirely in favor of direct access to virtualized input/output (I/O) devices. By reimagining the traditional role of the OS kernel, the researchers demonstrated that high performance and protection could go hand in hand.

More recently, Krishnamurthy co-led a team of researchers that created TVM, a framework that enabled researchers and practitioners to take advantage of emerging machine learning capabilities — and their attendant productivity gains — by making it easy to deploy the latest deep learning applications on a range of devices without sacrificing battery power or speed. Krishnamurthy and colleagues subsequently earned a Best Paper from IEEE Micro for introducing an extension to TVM, the Versatile Tensor Accelerator (VTA), that offered a customizable deep learning architecture designed to be extensible in the face of evolving workloads while preserving the efficiency gains achieved by hardware specialization. Together, TVM and VTA provided the blueprint for an end-to-end deep learning system for supporting experimentation, optimization, and hardware-software co-design. The team later transitioned TVM to Apache and launched a related startup company, OctoML, for which Krishnamurthy serves as an advisor.

Meredith Ringel Morris

Portrait of Meredith Ringel-Morris

Allen School affiliate professor Meredith “Merrie” Ringel Morris is a senior principal researcher and the research area manager for Interaction, Accessibility and Mixed Reality at Microsoft Research, where she founded the Ability Research Group. An internationally renowned researcher with expertise spanning collaborative technologies, gesture interfaces, social media, crowdsourcing, accessible technologies, universal design, human-centered AI, and more, Morris was named a Fellow of the ACM for “contributions to human-computer interaction, information retrieval, computer-supported cooperative work and accessibility.”

Morris first joined Microsoft Research in 2006 after earning her Ph.D. from Stanford University. She holds more than 20 U.S. patents, and her work has influenced many of Microsoft’s products and services in her 15 years with the company. Morris has authored or co-authored more than 100 research publications, including multiple papers that have been recognized with Best Paper Awards or Lasting Impact Awards at major conferences in the field. Last year, Morris was elected to the CHI Academy by the ACM Special Interest Group on Computer-Human Interaction (SIGCHI) in recognition of her many and varied contributions to HCI research, including establishing the field of collaborative web search, initiating the study of friendsourced information seeking, advancing surface computing and gesture design, and furthering research into accessible social media and communications technologies. Previously, she was recognized as one of Technology Review’s “Innovators under 35” for her work on SearchTogether, a browser plugin that enables collaborative web search. 

Steve Gribble

Portrait of Steve Gribble

Former professor Steve Gribble, who spent 13 years on the Allen School faculty before leaving for industry, was named a Fellow of the ACM for “contributions to virtualization technology across clusters, servers, and networks.” Now a distinguished engineer at Google, Gribble’s current work involves designing, building, and deploying host-side networking systems, I/O offload hardware infrastructure for Google’s cloud, and software-defined networking (SDN) systems that make the company’s planetary-scale networks available, debuggable, and safe to operate.

Gribble joined the UW faculty in 2000 after earning his Ph.D. from the University of California, Berkeley. Together with Allen School colleagues, in 2006 he co-founded Skytap, a venture-backed startup company that provides cloud-based software development, test and deployment platforms. Gribble has authored or co-authored more than 70 research publications, including seven that earned Best Paper or Best Student Paper Awards at major systems conferences. During his time at the Allen School, Gribble received an Alfred P. Sloan Research Fellowship and a National Science Foundation CAREER Award for his work on the design and operation of robust, scalable internet infrastructure and services, mobile computing, virtual machine monitors, operating systems, and networks.

The new Fellows will be formally inducted at the ACM awards banquet in June. Learn more about the 2020 class of ACM Fellows here.

Congratulations to Dieter, Arvind, Merrie and Steve!

February 17, 2021

« Newer PostsOlder Posts »