Allen School News

After several years of Covid-induced online career fairs, the Allen School returned to an in-person format this fall!

On October 4 and 6, more than 50 companies — members of the Allen School’s Industry Affiliates program — came to campus to recruit students for full-time, part-time, and internship positions. On each day, the first half of the session was devoted to Allen School students; UW students in related majors joined for the second half. In all, more than 1,000 students participated across the two days.

The fall career fairs are instrumental in connecting students with career opportunities in the local technology community. In 2021-22, the Allen School alone sent more than 60 graduates to full-time positions at Amazon, more than 50 to Google, and more than 40 each to Facebook and Microsoft. Allen School students accepted full-time positions at more than 100 tech companies in total — the vast majority in the Puget Sound region.

The Allen School will host a virtual career fair on October 12, followed by the in-person Data Science career fair, hosted by the Allen School in conjunction with the UW eScience Institute, on October 20. Read more →

When bees leave the hive, they can spend all day flying and foraging on a single “charge” owing to their ability to convert fats and carbohydrates that store significantly more energy than batteries. When other insects traverse the landscape, the structure of their retinas combined with the motion of their heads enable them to efficiently take in and process visual information. And when dandelions shed their seeds, structural variations ensure that they are dispersed through the air over short and long distances to cover maximum ground. 

Allen School professor Vikram Iyer is not a biologist, but he takes inspiration from these and other biological phenomena to engineer programmable systems and devices that can go where computers have been unable to go before — and solve problems more efficiently and safely than previously thought possible. During his time as a University of Washington Ph.D. student, Iyer imagined how the so-called internet of biological and bio-inspired things could transform domains ranging from agriculture to wildlife conservation. His results recently inspired the Association for Computing Machinery’s Special Interest Group on Mobility of Systems, Users, Data, and Computing to recognize him with the SIGMOBILE Doctoral Dissertation Award for “creative and inspiring work that shows how low-power sensing, computing and communication technologies can be used to emulate naturally-occurring biological capabilities.”

“Building bio-inspired networking and sensing systems requires expertise across multiple disciplines spanning computer science, electrical engineering, mechanical engineering and biology,” said Allen School professor Shyam Gollakota, Iyer’s Ph.D. advisor. “I think this thesis breaks new ground by designing programmable technologies that not only mimic nature but also takes the crucial step of integrating electronics with living organisms.”

Gollakota and Iyer worked together on a series of projects that gave new meaning to the term “computer bug” — but in this case, they took their lessons from the kind of bugs with legs and wings. For one of their early projects, Living IoT, the team developed a scaled down wireless sensing and communication platform that was light enough to be worn by bumblebees in flight. The tiny sensor backpacks incorporate a rechargeable power source, localization hardware, and backscatter communication to relay data once the bee returns to the hive in a form factor topping out at a mere 102 micrograms. Later, when the northern giant hornet — colloquially referred to as the “murder hornet” — was sighted in northwest Washington, the state’s Department of Agriculture enlisted Iyer’s help in designing and affixing tiny tracking devices onto a live specimen so that agency staff could track it back to the nest. 

After seeing their concept of on-board sensors for insects take flight, Iyer and his colleagues came back down to earth to develop a tiny wireless camera inspired by insect vision. Their system, which they dubbed “Beetlecam,” offered a fully wireless, autonomously powered, mechanically steerable vision system that imitates the head motion of insects. By affixing the camera onto a moveable mechanical arm, the team could mimic insect head motion to capture a wide-angle view of the scene and track the movement of objects while expending less energy — and at a higher resolution. The complete vision system, which can be controlled via smartphone, is small enough to mount on the back of a live beetle or insect-sized terrestrial robots such as their own prototype built to demonstrate the capabilities.

Many sensors, including those designed by Iyer and his collaborators, still require a method of transportation, be it beetle, bee, or robot. Iyer and his collaborators wondered if they could design sensors capable of delivering themselves. The answer, to borrow a phrase from singer/songwriter Bob Dylan, was blowing in the wind — in the form of dandelion seeds. Iyer and the team developed a wireless, solar-powered sensing and communication system that can be carried aboard flexible, thin shapes. The shapes are designed to carry the sensors through air and land upright 95% of the time, relying on a structure reminiscent of the bristle-like shape of dandelion seeds — with some necessary modifications to accommodate the weight of the attached sensor. The team also demonstrated that, by modulating the porosity and diameter of the structures, they can ensure the sensors are dispersed at various distances like the seeds.

Unlike many miniaturized systems, Iyer’s flora- and fauna-inspired projects favor designs that rely on off-the-shelf parts instead of requiring custom-built circuits.

“In addition to showing how we can take lessons from nature to advance a new category of bioinspired computing, my work demonstrates how we can use programmable general-purpose components to rapidly develop these novel miniaturized wireless systems,” Iyer explained. “This approach has the potential to exponentially increase innovation in domains such as smart agriculture, biological tracking, microrobots, and implantable devices. My goal is to enable anyone with a computer engineering background to advance miniaturized systems without the need to also develop custom silicon.”

Iyer, who earned his Ph.D. from the UW Department of Electrical & Computer Engineering before joining the Allen School faculty last year, previously earned a Paul Baran Young Scholar Award from the Marconi Society and his work was voted Innovation of the Year in the 2021 GeekWire Awards. He is the third student researcher advised by Gollakota to win this award in recent years, following in the footsteps of Allen School alum Rajalakshmi Nandakumar (Ph.D., ‘20), now a faculty member at Cornell University, and ECE alum Vamsi Talla (Ph.D., ‘16), who was co-advised by Allen School and ECE professor Joshua Smith and is currently CTO of UW spinout Jeeva Wireless.

Congratulations, Vikram!

Photo credit: Mark Stone/University of Washington Read more →

For Allen School professor Maya Cakmak, the future of robotics hinges on the human element. Since the early days of her research career, Cakmak has been leveraging advances in human-computer interaction and accessibility to shift robotics research from primarily technology-centric approaches toward a more user-centric approach. She is also known for putting people first through her support for programs and policies aimed at increasing participation in computing by women and people with disabilities. For her efforts, the Computing Research Association’s Committee on Widening Participation in Computing Research (CRA-WP) recently recognized Cakmak with its 2022 Anita Borg Early Career Award — named in honor of another woman in computing who wasn’t afraid to break new ground and lead by example.

Cakmak holds the Robert E. Dinning Career Development Professorship in the Allen School, where she directs the Human-Centered Robotics Lab. There, she and her collaborators develop robots that can be programmed by users with diverse needs and preferences to assist with everyday tasks — in her own words, “empowering users to decide what their robots will do for them.” 

Even before she joined the University of Washington faculty in 2013, Cakmak had already begun building a reputation in robotics circles for her human-centric approach. As a Ph.D. student at Georgia Tech, Cakmak showed that many data-driven methods for programming by demonstration were ill-suited to novice users, proposing instead to employ interaction-driven approaches that incorporate user studies — a novel idea at the time that has since entered the mainstream. She also was an early evangelist of active learning in robotics, which enables robots to acquire new knowledge and skills via queries instead of just passively receiving data from humans.

After her arrival at the Allen School in 2013, Cakmak sought to expand end-user programming capabilities for robots beyond conventional programming by demonstration by drawing upon techniques from HCI. She also pursued new connections between robotics and programming languages, uniting two of the Allen School’s strengths to usher in a new and growing area of interdisciplinary research. For example, Cakmak and Ph.D. student Sonya Alexandrova teamed up with faculty colleague Zachary Tatlock in the Programming Languages & Software Engineering (PLSE) group on RoboFlow, an intuitive visual programming language to enable users to program robots to perform mobile manipulation tasks in various real-world environments. She also worked with then-student Justin Huang (Ph.D., ‘18) and Allen School alum Tessa Lau (Ph.D., ‘01), who at the time served as CTO and “Chief Robot Whisperer” at Savioke, Inc., to create a rapid programming system for mobile service robots. That system, which the team dubbed CustomPrograms, featured a cloud-based graphical interface to support the rapid prototyping and development of custom applications by experts as well as inexperienced programmers. 

Cakmak and Huang followed that up with Code3, a suite of user-friendly tools for perception, manipulation and high-level programming that enables rapid, end-to-end programming of robots such as the PR2 and Fetch to perform mobile manipulation tasks. As with many of her projects, Code3 was designed to appeal to experts and novice users alike. In 2016, Cakmak received a CAREER Award from the National Science Foundation for her project titled “End-user programming of general-purpose robots” to continue this line of research.

According to her Allen School robotics colleague Dieter Fox, Cakmak’s human-centric approach has been hugely influential within the robotics community.

”Human-robot interaction has grown tremendously over the past decade, and Maya has been at the forefront of the field,” said Fox, director of the UW’s Robotics and State Estimation Lab and senior director of robotics research at NVIDIA. “Her work has also had real-world impact through her collaborations with multiple robotics companies that ship their robots with end-user tools that she developed.”

Fox knows all about the potential impact of such academic-industry collaboration. He and his colleagues at NVIDIA recently teamed up with Cakmak to develop new capabilities in human-robot handovers — an essential skill for robots to safely and reliably assist humans with everyday tasks. The team’s system, which demonstrated smooth human-to-robot handover of arbitrary objects commonly found in people’s homes, earned the Best Paper Award in HRI at the International Conference on Robotics and Automation (ICRA 2021). Cakmak also collaborated with Anat Caspi, director of the Allen School’s Taskar Center for Accessible Technology, and researchers in the Personal Robotics Lab led by professor Sidd Srinivasa to explore user preferences and community-centered design principles to inform the development of robot-assisted feeding systems for people with mobility impairments. 

Whatever problem she aims to solve, Cakmak has been eager to take her cue from the people who have the potential to benefit most from her work.

“I deeply care about the relevance and usefulness of my research,” Cakmak explained in her Early Career Spotlight talk at the 2018 Robotics: Science & Systems (RSS) conference. “To that end, I try to evaluate systems I develop with a realistic and diverse set of tasks, I put these systems in front of real potential users with diverse backgrounds and abilities, and I take every opportunity to demonstrate and deploy them in the real world.”

Cakmak’s contributions to accessibility go far beyond her projects and papers; she is also a vocal proponent of making the act of research — and the conferences and other events where research careers are made — more inclusive of people with disabilities and women. This includes making it easier for women who are new mothers to participate, inspired by her personal experience. In one specific example, Cakmak successfully lobbied for changes in one organization’s reimbursement policies to cover childcare expenses for invited speakers. 

“When I had my first child, I received a transitional grant from the UW ADVANCE Center for Institutional Change to cover expenses of taking my infant along for work travel,” Cakmak said. “Continuing to go to conferences was critical for me to stay active in my research community and help my graduate students network. But it did more than that. Colleagues would often approach me, not just to play with the baby but to ask questions about the logistics of taking your baby to a conference or how to manage starting a family while being on tenure-track. Many were amazed to hear about the ADVANCE grant and went back to ask for similar initiatives at their institutions.

“In an academic career system where young parents are disadvantaged, we are learning how to make it work from one another, while also pushing for positive institutional change,” she continued. “This is why representation matters so much. We owe many privileges we now take for granted to the hard work of those who were disadvantaged back in the day.”

Back on campus, Cakmak served as a co-principal investigator on the National Science Foundation-funded AccessEngineering initiative to incorporate topics such as universal design into engineering courses and to make labs and maker spaces accessible to students with diverse abilities. In an effort to engage more people with disabilities in computing and, in particular, robotics, Cakmak designed and taught a course for high school students over multiple summers as part of the UW DO-IT Center’s Scholars program. The course provided participants with hands-on experience in programming robots while encouraging them to think about how the field can help solve real-world problems. She developed a similar workshop for AccessComputing’s OurCS@UW program for undergraduate women with disabilities. Cakmak’s contributions inspired the DO-IT Center to recognize her with its 2021 Trailblazer Award. 

In addition to these activities, Cakmak developed a seminar to provide second-year students with the foundational skills to participate in research. She also served as the UW faculty representative for the fourth cohort of the LEAP Alliance, a program that seeks to diversify the professoriate by supporting underrepresented students in pursuing academic careers. She also organized a rejuvenated RSS Women in Robotics Workshop, including raising funds for travel grants that enabled women roboticists from around the world to participate, and later supported its expansion to include researchers from other underrepresented groups.

“Maya is a stellar researcher who is a leader in her field of research, and she has dedicated an immense amount of time and effort to broadening participation by women and students with disabilities — directly and indirectly impacting many students,” Fox said. “I cannot imagine a more deserving recipient of the Anita Borg Award.”

The award includes a $5,000 prize, which Cakmak donated to the Allen School to support more women to pursue undergraduate research.

“This award means so much to me because it recognizes things I did in my career beyond my research that I did not expect to be recognized for,” Cakmak said. “I have been so fortunate to have many amazing role models, mentors, advocates, and supporters; I was just trying to pay it forward. I am honored especially because I have been so inspired by Anita Borg.”

Indeed, Cakmak’s work embodies Borg’s famous quote: “If we want technology to serve society rather than enslave it, we have to build systems accessible to all people — be they male or female, young, old, disabled, computer wizards or technophobes.”

Cakmak is the second Allen School faculty member to earn the Borg Early Career Award in the past five years, following professor Yejin Choi’s recognition in 2018. Allen School alumni Martha Kim (Ph.D., ’08), a faculty member at Columbia University; A.J. Bernheim Brush (Ph.D., ’02), Partner Group Program Manager at Microsoft; and Gail Murphy (Ph.D., ’96), Vice President of Research and Innovation and a faculty member at the University of British Columbia, are also past recipients of the award.

Congratulations, Maya! Read more →

For millions of people who participate in activities such as snorkeling and scuba diving each year, hand signals are the only option for communicating safety and directional information underwater. While recreational divers may employ around 20 signals, professional divers’ vocabulary can exceed 200 signals on topics ranging from oxygen level, to the proximity of aquatic species, to the performance of cooperative tasks.

The visual nature of these hand signals limits their effectiveness at distance and in low visibility. Two-way text messaging is a potential alternative, but one that requires expensive custom hardware that is not widely available. 

Researchers at the University of Washington show how to achieve underwater messaging on billions of existing smartphones and smartwatches using only software. The team developed AquaApp, the first mobile app for acoustic-based communication and networking underwater that can be used with existing devices such as smartphones and smartwatches.

“Smartphones rely on radio signals like WiFi and Bluetooth for wireless communication. Those don’t propagate well underwater, but acoustic signals do,” said co-lead author Tuochao Chen, a Ph.D. student in the Allen School. “With AquaApp, we demonstrate underwater messaging using the speaker and microphone widely available on smartphones and watches. Other than downloading an app to their phone, the only thing people will need is a waterproof phone case rated for the depth of their dive.”

The AquaApp interface enables users to select from a list of 240 pre-set messages that correspond to hand signals employed by professional divers, with the 20 most common signals prominently displayed for easy access. Users can also filter messages according to eight categories, including directional indicators, environmental factors, and equipment status. 

In building the app, Chen and his collaborators — co-lead author and fellow Ph.D. student Justin Chan and professor Shyam Gollakota — had to overcome a variety of technical challenges that they haven’t previously encountered on dry land.

“The underwater scenario surfaces new problems compared to applications over the air,” explained Chan. “For example, fluctuations in signal strength are aggravated due to reflections from the surface, floor and coastline. Motion caused by nearby humans, waves and objects can interfere with data transmission. Further, microphones and speakers have different characteristics across smartphone models. We had to adapt in real time to these and other factors to ensure AquaApp would work under real-world conditions.”

Those other factors include the tendency for devices to rapidly shift position and proximity in the current and the various noise profiles the app might encounter due to the presence of vessels, animals, and even low-flying aircraft. 

The team created an algorithm that allows AquaApp to optimize, in real time, the bitrate and acoustic frequencies of each transmission based on certain parameters, including distance, noise and variations in frequency response across devices. When one user wants to send a message to another device, their app first sends a quick note, called a preamble, to the other device. AquaApp on the second device runs the algorithm to determine the best conditions to receive the preamble; it then tells the first device to use those same conditions to send the actual message.

The researchers developed a networking protocol to share access to the underwater network, akin to how WiFi networks referee internet traffic, to support messaging between multiple devices. AquaApp can accommodate up to 60 unique users on its local network at one time. 

The team tested the real-world utility of the AquaApp system in half a dozen locations offering a variety of water conditions and activity levels, including under a bridge in calm water, at a popular waterfront park with strong currents, next to the fishing dock of a busy lake, and in a bay with strong waves. In a series of experiments, they evaluated AquaApp’s performance at distances of up to 113 meters and depths of up to 12 meters.

“Based on our experiments, up to 30 meters is the ideal range for sending and receiving messages underwater, and 100 meters for transmitting SoS beacons,” Chen said. “These capabilities should be sufficient for most recreational and professional scenarios.” 

The researchers also measured AquaApp’s impact on battery life by continuously running the system on two Samsung Galaxy S9 smartphones at maximum volume and with screens activated. The app reduced the devices’ battery power by just 32% over the course of four hours, which is within the maximum recommended dive time for recreational scuba diving.

“AquaApp brings underwater communication to the masses,” said Gollakota, who directs the Mobile Intelligence Lab and holds the Torode Family Career Development Professorship in the Allen School. “The state of underwater networking today is similar to ARPANET, the precursor of the internet, in the 1970s, where only a select few had access to the internet. AquaApp has the potential to change that status quo by democratizing underwater technology and making it as easy as downloading software on your smartphone.”

Gollakota and his co-authors presented their paper describing AquaApp last week at SIGCOMM 2022, the flagship peer-reviewed conference of the Association for Computing Machinery’s Special Interest Group on Data Communications. The team’s data and open-source Android code are available on the AquaApp website. Watch a video demonstrating AquaApp here.

The researchers are supported by the Moore Inventor Fellowship award #10617 and the National Science Foundation.

Photo credits: University of Washington. Sarah McQuate in the UW News Office contributed to this story. Read more →

In the spring of 2020, people took to the streets — and to the tweets — in protest after a white police officer murdered George Floyd, a Black man, in Minneapolis by kneeling on his neck and back for over nine minutes. Black Lives Matter, a movement spawned seven years earlier following the shooting death of Trayvon Martin, an unarmed Black teenager, in Florida and the killer’s subsequent acquittal, emerged as the online and offline rallying cry against police brutality and racist violence perpetrated against Black people. 

Following Floyd’s death, Twitter users flooded the social media platform with hundreds of millions of posts expressing a range of emotions concerning Black Lives Matter and the campaign for racial justice. A team led by Allen School professor Yulia Tsvetkov sought to facilitate a greater understanding of the connection between those emotional expressions and the narrative surrounding Black Lives Matter and its supporters — and how that connection could also shed light on the role of social media messaging in online activism and large-scale social movements, more generally. To that end, the researchers applied recent advances in natural language processing to analyze the content of 34 million original English-language tweets about BLM posted in 2020 between May 24 and June 28 to identify the prevailing emotions expressed on social media about the movement and associated protests. 

The researchers shared their findings in a paper published this week in the Proceedings of the National Academy of Sciences (PNAS) — findings that counter a harmful yet persistent narrative about the emotional tenor of the BLM movement and the people behind it.

“While we identified high levels of anger and disgust across all posts in our dataset, what jumped out at us was the prevalence of positive emotions in posts containing pro-BLM hashtags such as #BlackLivesMatter, #JusticeforFloyd and #NoJusticeNoPeace, and correlating with on-the-ground protests,” said co-lead author and Stanford University postdoc Anjalie Field, who worked on the project as a visiting UW student and Ph.D. candidate at Carnegie Mellon University. “Positive emotions like hope and optimism are more prevalent in posts with explicitly pro-BLM hashtags than other subsets of the data, which contradicts the stereotype of BLM supporters as promoting anger and outrage.”

To perform their analysis, Field, Tsvetkov and their collaborators developed a neural classification model based on the six core emotions identified by psychologist Paul Ekman: anger, disgust, fear, surprise, positivity — what Ekman refers to as “joy” — and sadness. Consistent with prior work applying Ekman’s taxonomy, the researchers treated each category as a superset of finer grained emotions such as the aforementioned hope and optimism (positivity), disapproval and rage (anger), vigilance and apprehension (fear), confusion and curiosity (surprise), and grief and remorse (sadness). Because neural models trained on a pre-collected data set may perform poorly when used to infer meaning from text gathered in a different domain, the team opted for a domain adaptation approach. By combining task-adaptive pre-training with few-shot learning techniques, their methodology permits the re-use of existing annotated datasets to train the model on different domains, rather than going through the effort and expense of collecting and annotating new datasets. They trained their model on two large, pre-existing social media datasets annotated for expressed emotions and adapted it to tweets relating to Black Lives Matter.

As Field noted, anger was the prevailing emotion identified by the model, which detected its presence in 40% or more of the tweets posted over the course of the month. Disgust and positivity alternated as the second-most prevalent emotions, with surprise, sadness and fear rarely approaching 10%. When the researchers analyzed the subset of 6.5 million tweets containing pro-BLM hashtags, they found that positivity consistently outweighed the other categories starting around four days in — on some days, more than double the negative emotions. 

Drilling down into the dataset according to date enabled the team to identify instances where emotions spiked, presumably in connection with events. For example, anger and sadness peaked in tweets with pro-BLM hashtags in the days following Floyd’s death and prior to the first weekend of protests. Positivity, meanwhile, rose in the days leading up to that weekend and afterward became the most frequently expressed emotion through the rest of the month. Positivity peaked on the Juneteenth holiday, present in 60% of tweets carrying pro-BLM hashtags. By analyzing location data, the researchers also found that the volume of tweets expressing positive emotions positively correlated with users’ proximity to on-the-ground protests.

Such rich analysis from the team’s adaptive neural model contrasts with that of conventional social science analyses, which typically rely on more rigid lexicon-based approaches using a set list of words associated with an emotion to determine whether content reflects that emotion.  

“Lexicon-based models are easy to use, but they aren’t particularly good at capturing broader connotations or adapting to new contexts,” explained co-lead author Chan Young Park, a visiting UW student who is pursuing a Ph.D. from CMU. “For example, one popular model connotes the word ‘police’ with the terms ‘fear,’ ‘positive’ and ‘trust’ — emotions that are unlikely to factor into protests against police brutality. Our framework offers a more robust method for extracting accurate social meaning from text data that can be adapted to different contexts and language varieties.”

The meaning the team extracted from posts using its computational model is consistent with findings from previous social psychology studies; while moral outrage and anger can prompt people to become involved in social movements, positive emotions are necessary to sustain that involvement over time.

“Words and emotions are powerful tools for online activism. Emerging NLP techniques are also powerful tools that can help us understand how those words and emotions contribute to building and sustaining social movements,” said Tsvetkov. “In doing so, they can help us also to dispel negative stereotypes about marginalized communities that lead to physical, social and economic harm.”

Additional contributors to the paper include co-lead author and then-student Antonio Theophilo, who recently earned his Ph.D. from the Institute of Computing at the University of Campinas in Brazil, and Jamelle Watson-Daniels, a Ph.D. student at Harvard University and Director of Research at Data for Black Lives.

Read the full paper here, and a related story by CMU here. Read more →

For people around the world, technology eases the friction of everyday life: bills paid with a few clicks online, plans made and sometimes broken with the tap of a few keys, professional and social relationships initiated and sustained from anywhere at the touch of a button. But not everyone experiences technology in a positive way, because technology — including built-in safeguards for protecting privacy and security — isn’t designed with everyone in mind. In some cases, the technology community’s tendency to develop for a “default persona” can lead to harm. This is especially true for people who, whether due to age, ability, identity, socioeconomic status, power dynamics or some combination thereof, are vulnerable to exploitation and/or marginalized in society.

Researchers in the Allen School’s Security & Privacy Research Lab have partnered with colleagues at the University of Florida and Indiana University to provide a framework for moving technology design beyond the default when it comes to user security and privacy. With a $7.5 million grant from the National Science Foundation through its Secure and Trustworthy Cyberspace (SaTC) Frontiers program, the team will blend computing and the social sciences to develop a holistic and equitable approach to technology design that addresses the unique needs of users who are underserved by current security and privacy practices.

“Technology is an essential tool, sometimes even a lifeline, for individuals and communities. But too often the needs of marginalized and vulnerable people are excluded from conversations around how to design technology for safety and security,” said Allen School professor and co-principal investigator Franziska Roesner. “Our goal is to fundamentally change how our field approaches this question to center the voices of marginalized and vulnerable people, and the unique security and privacy threats that they face, and to make this the norm in future technology design.”

To this end, Roesner and her collaborators — including Allen School colleague and co-PI Tadayoshi Kohno — will develop new security and privacy design principles that focus on mitigating harm while enhancing the benefits of technology for marginalized and vulnerable populations. These populations are particularly susceptible to threats to their privacy, security and even physical safety through their use of technology: children and teenagers, LGBTQ+ people, gig and persona workers, people with sensory impairments, people who are incarcerated or under community supervision, and people with low socioeconomic status. The team will tackle the problem using a three-prong approach, starting with an evaluation of how these users have been underserved by security and privacy solutions in the past. They will then examine how these users interact with technology, identifying both threats and benefits. Finally, the researchers will synthesize what they learned to systematize design principles that can be applied to the development of emerging technologies, such as mixed reality and smart city technologies, to ensure they meet the privacy and security needs of such users.

The researchers have no intention of imposing solutions on marginalized and vulnerable communities; a core tenet of their proposal is direct consultation and collaboration with affected people throughout the duration of the project. They will accomplish this through both quantitative and qualitative research that directly engages communities in identifying their unique challenges and needs and evaluating proposed solutions. The team will apply these insights as it explores how to leverage or even reimagine technologies to address those challenges and needs while adhering to overarching security and privacy goals around the protection of people, systems, and data.

The team’s approach is geared to ensuring that the outcomes are relevant as well as grounded in rigorous scientific theory. It’s a methodology that Roesner, Kohno, and their colleagues hope will become ingrained in the privacy and security community’s approach to new technologies — but they anticipate the impact will extend far beyond their field.

“In addition to what this will mean in terms of a more inclusive approach to designing for security and privacy, one of the aspects that I’m particularly excited about is the potential to build a community of researchers and practitioners who will ensure that the needs of marginalized and vulnerable users will be met over the long term,” said Kohno. “Our work will not only inform technology design, but also education and government policy. The impact will be felt not only in the research and development community but also society at large.”

Kohno and Roesner are joined in this work by PI Kevin Butler and co-PIs Eakta Jain and Patrick Traynor at the University of Florida, co-PIs Kurt Hugenberg and Apu Kapadia at Indiana University, and Elissa Redmiles, CEO & Principal Researcher at Human Computing Associates. The team’s proposal, “Securing the Future of Computing for Marginalized and Vulnerable Populations,” is one of three projects selected by NSF in its latest round of SaTC Frontiers awards worth a combined $24.5 million. The other projects focus on securing the open-source software supply chain and extending the “trusted execution environment” principle to secure computation in the cloud.

Read the NSF announcement here and the University of Florida announcement here. Read more →

After graduating from the University of Washington in December with degrees in computer science and chemical engineering, Allen School alum Isaiah Lemmon (B.S., ‘21) took on a software engineering role at Amazon Web Services. There, he intends to put his education to work advancing energy efficient solutions for the datacenter, inspired in part by his experience as an undergraduate researcher during his time at UW. That experience, combined with his rigorous coursework and achievements inside and outside of the classroom, recently earned him a 2022 Dean’s Medal for Academic Excellence from the College of Engineering — affirming his decision to pursue research across multiple disciplines to prepare himself to make a positive difference in the world.

“I’m honored to have been chosen for this award, and I’m really excited about the opportunity the combination of these two degrees has opened to me,” Lemmon said. “The amount of applicable knowledge and skills that different engineering disciplines have to offer each other is incredible, and I’d strongly encourage other students to pursue interdisciplinary research for that exposure.”

From his early days as an undergraduate student, Lemmon displayed a talent and passion for research and discovery. He applied both to great effect working with professor Jim Pfaendtner, chair of the UW Department of Chemical Engineering, on projects that enabled him to explore his dual interests in molecular science and computation. One such project involved studying interactions between titanium dioxide and water at the solid/liquid interface via ab initio molecular dynamics, for which Lemmon performed programming and data analysis using the UW’s HYAK supercomputing cluster.

“Isaiah approached me when he was fresh out of high school, and I quickly realized that he was an incredibly rare student,” said Pfaendtner. “Before long, Isaiah was a regular in our research group and made impressive gains on several projects related to catalysis, interfacial phenomena and ab initio molecular dynamics. However, it was in his work as a de facto software engineer for my team, during his third year of study, that we really saw Isaiah shine.”

At that time, Pfaendtner was eager to keep Lemmon engaged with his lab by supporting him in his quest to combine his knowledge and skills from both majors. He decided to hire Lemmon to assist lab members with turning their prototype software into usable products that could be deployed in the real world. In one instance, Lemmon rewrote a complex piece of reaction engineering software in Python from scratch to make it more robust and useful for a broader range of projects in the lab. He subsequently collaborated with then-Ph.D. student Sarah Alamdari to make modifications to a community software package that enabled Pfaendtner’s group to make their algorithms more widely available within the research community. Lemmon’s mentor characterized this work as evidence that he had already achieved a level of ability and independence more akin to that of a fourth or fifth  year Ph.D. student than an undergraduate.

Lemmon also did not shy away from tackling advanced coursework, including material that would typically be the preserve of graduate students. For example, he excelled in Pfaendtner’s Mass Transfer and Separations course and Allen School professor Tom Anderson’s Distributed Systems course — two offerings considered by students to be among the most difficult and intellectually challenging within their respective majors. In his final quarter at the UW, Lemmon enrolled in a new and similarly challenging Datacenter Systems course that explores the technologies that go into the construction and operation of large-scale datacenters — described by Anderson as “among the most complex systems that people have ever built.” Even so, Lemmon was undaunted by the subject matter. For the open-ended class project, he and his partners built a system for mapping the wiring layout for a datacenter that surprised and delighted their professor.

“As part of their project, Isaiah and his partners built a truly impressive visualization tool that showed how the different layers of switches could be organized as the size of the datacenter scaled up,” Anderson recalled. “Even though Isaiah was still just an undergrad, I thought his work was among the most ambitious and most interesting in a class of 80 students.”

“For me, it was my passion for programming and clean energy that led to where I am — finding a meaningful way to overlap those fields has been my dream,” Lemmon said. “I’m still trying to find the exact niche I want to settle in and am not yet sure if that will be in industry or academia, but my hope is some combination of the two so I can continue to do impactful research.”

Lemmon is one of two students in the College of Engineering honored with a Dean’s Medal this year; the other is Taylor Juenke, a student in the Department of Materials Science & Engineering. Learn more about the 2022 Dean’s Medalists here.

Congratulations, Isaiah! Read more →

The Association for Computing Machinery’s Special Interest Group on the Management of Data honored Allen School professor Dan Suciu with its 2022 Edgar F. Codd Innovations Award in recognition of his “lasting contributions to the foundations of novel data management trends.” The award recognizes a member of the ACM SIGMOD community who has made enduring and highly significant contributions to the development, understanding or use of databases and database systems over the course of their career. In the same week he was recognized for his influential body of work, Suciu also collected a Best Paper Award for his latest contribution — an indication that he has no intention of resting on his laurels.

Throughout his career, Suciu has shown a propensity for drawing deep connections between logic, database theory, algorithms and systems. According to Dan Olteanu, professor and head of the Data Systems and Theory Group at the University of Zurich, Suciu’s approach to advancing new data management paradigms has also set a new standard for research in the field.

“Dan Suciu is the most prominent researcher bridging database systems and theory,” said Olteanu. “His numerous contributions to the theory and practice of databases have fundamentally transformed a wide range of areas of research, such as semistructured data, data security, querying unreliable and inconsistent sources, probabilistic databases, data pricing, distributed and parallel query processing, and causality inference. They established clean formal foundations and practical and elegant data processing techniques. They further changed how younger generations of computer science researchers, including myself, approach research problems, and we relentlessly strive to meet the bar set by his work.”

Suciu, who holds the Microsoft Endowed Professorship in the Allen School, has been setting the bar high ever since he joined the University of Washington nearly 22 years ago. For example, in a paper appearing at the 2002 Symposium on Principles of Database Systems (PODS) Suciu and then-student Gerome Miklau (Ph.D., ‘05), now a faculty member at the University of Massachusetts Amherst, examined the complexity of containment and equivalence for a core fragment of the XPath query language for XML applications. The fragment in question covers attributes that are frequently applied in practice, specifically queries that contain branching, label wildcards and can express descendant relationships between nodes. Whereas prior work had established that efficient containment algorithms exist for any combination of two of those, Suciu and Miklau established — to their own surprise — that the problem of checking containment of all three is coNP-complete. Based on their findings, the duo designed an efficient containment algorithm capable of running in polynomial time for several cases with practical significance that involve all three. Their paper was singled out for its impact with the PODS Alberto O. Mendelzon Test of Time Awards in 2012 — one of two PODS Test of Time Awards that Suciu has received in his career so far.

In another paper that combined rigorous theoretical evaluation with real-world concerns — in this case, those of every individual who has purchased a product or service or surfed online — Suciu and his collaborators introduced a framework for the pricing of private data. This work, published in 2017, conceived of a market balancing the interests of individuals in safeguarding their personal information with the sometimes incompatible interests of companies and organizations seeking to extract value from said data for the purposes of offering more personalized services, targeting their marketing to specific interests, and direct sale to third parties. To find that elusive balance, Suciu, Miklau, and co-authors Chao Li and Daniel Yang Li drew from and expanded upon elements of differential privacy and data markets to construct a framework in which a “market maker” acts as an intermediary between individual data owners and institutional data buyers. In this scenario, the market maker responds to queries from the latter and sets prices to compensate the former based on a variety of factors, including the amount of perturbation — or noise — in the data, the option to source data from less expensive query sources, and individuals’ own risk tolerance for potential privacy loss. Suciu and the team earned a Best Paper Award at the 16th International Conference on Database Theory (ICDT 2013) for this work.

Around the same time, against the backdrop of the rapid rise in cloud computing and big data, Suciu tackled the algorithmic aspects of parallel data processing over large-scale distributed systems such as the MapReduce framework and UW’s own Myria system. Working with colleague Paul Beame of the Allen School’s Theory of Computation group and former student Paraschos Koutris (Ph.D., ‘15), now a faculty member at the University of Wisconsin-Madison, Suciu introduced a new theoretical model, Massively Parallel Computation (MPC), that separates the cost of computation from that of communication. By focusing the cost of parallel processing exclusively on the latter based on the amount of communication and the number of communication rounds, Suciu and his collaborators led a paradigm shift in how the community analyzed the complexity of distributed large-scale data queries — from run-time or the number of disk input/output operations, to the amount of data being reshuffled while maintaining server-load balance. Suciu and Koutris subsequently applied the MPC in a comprehensive survey of algorithms for different data processing tasks in collaboration with Semih Salihoglu, a faculty member at University of Waterloo.

In addition to publishing nearly 300 conference or journal papers, Suciu has contributed to multiple highly-cited books in data management. One of those, published in 2011, was an authoritative work on probabilistic databases he co-authored with Olteanu; former student Christopher Ré (Ph.D., ‘09), now a faculty member at Stanford University; and Christoph Koch, a faculty member at the École Polytechnique Fédérale de Lausanne. In the book, Suciu and his collaborators put forward novel representation formalisms and query processing techniques for modeling and processing probabilistic data used in information extraction, scientific data management, data cleaning, and other use cases that involve large volumes of uncertain data.

Three of Suciu’s aforementioned student collaborators — Miklau, Ré and Koutris — earned the ACM SIGMOD Doctoral Dissertation Award working with him. According to his UW Database Group colleague Magdalena Balazinska, Suciu’s impact in advancing new paradigms in data management is rooted not only in his vision and leadership in bridging theory and practice, but also in his devotion to developing the next generation of researchers to carry that work forward.

“As a database researcher myself, I have appreciated Dan’s approach to breaking new intellectual ground while offering a path to practical implementation,” said Balazinska, professor and director of the Allen School. “He has a knack for setting new directions for theoreticians to explore while also guiding engineers in the actual development of systems aligned with emerging trends. Not only is Dan a leader in the database research community, but he is a wonderful mentor to all who have the privilege of studying with him in addition to being a treasured colleague and friend.”

In his award talk at the SIGMOD/PODS conference in Philadelphia, Pennsylvania earlier this month, Suciu credited one of his own early mentors, Val Tannen, with “teaching me, and teaching me how to teach” and setting him on the path to his life’s work. It was Tannen who first introduced Suciu, back when he was a college student in Romania, to a new kind of mathematics that featured lattices, category theory and universal algebras — elements that Suciu found compelling and “strangely relevant” to his newfound passion for programming. Suciu later followed Tannen to the University of Pennsylvania, where he began his career in database research as a Ph.D. student working to redesign query languages grounded in mathematics — collecting the first of his many conference paper awards, at ICDT 1995, in the process.

Fast forward 27 years later, and Suciu collected his latest Best Paper Award, this time from PODS, for his work on “Convergence of Datalog over (Pre-) Semirings.” In the winning paper, Suciu and his co-authors — Mahmoud Abo Khamis and Hung Q. Ngo at RelationalAI, Reinhard Pichler at TU Wien, and Allen School Ph.D. student Remy Wang  — make progress on an open problem related to enabling recursive queries beyond Boolean space as required by modern data processing and tensor computations that power applications ranging from program analysis and machine learning, to graph algorithms and linear algebra. To enable this progress, the team introduced datalog^o, a powerful language for expressing recursive computations over general semi-rings. 

This latest accolade brings Suciu’s career tally at influential database, data management, and related conferences to six Best Paper or Distinguished Paper Awards, three Best Demo Awards, and five Test of Time or Influential Paper Awards.

Congratulations, Dan! Read more →

After two successive years of asynchronous, online tributes to graduates, the Allen School finally welcomed members of the classes of 2020, 2021 and 2022 to an in-person graduation celebration to mark the culmination of their academic journeys at the University of Washington. An estimated 3,000 faculty, staff, family and friends converged on Hec Edmundson Pavilion at the Alaska Airlines Arena on June 10th to honor the graduates’ achievements and recognize the impact that an Allen School education can have — not just on the lives of those who crossed the stage, but also on the world at large.

“We are counting on you”

Magdalena Balazinska, professor and director of the Allen School, acknowledged the immense challenges overcome by this group of graduates to reach this milestone. She expressed her pride in all that they had accomplished during their time at the school—and her belief in what they can accomplish in the future.

“Today, we at the Allen School are thrilled to join your families and friends in celebrating this momentous achievement. But tomorrow, we are counting on you,” said Balazinska. “The world needs your generation with your passion, your technical skills, your energy, and your commitment to your community and to the world. You now have the skills and knowledge to make the world a better place.

“Go out there, be brave, be kind, and do great things.”

Next stop: the north pole

Longtime friend to the Allen School Ron Howell, retired CEO of the Washington Research Foundation, joined in the celebration as the featured graduation speaker. In candid remarks, he shared the lessons he learned from his personal journey navigating severe depression for decades while building and maintaining a successful career in technology.

Howell used the metaphor of a sphere, the surface of which represented the various feelings, or “affects,” that people might experience throughout their lives. The very top of this sphere — the north pole — is a place of optimism, calmness, confidence, competence and resilience, while the south pole is home to the opposite. Howell offered the graduates his roadmap to the north pole. Some of the directions took the form of practical advice — eat right (“mostly vegetables”), exercise, meditate — while others served as reminders to extend grace to themselves as well as those they encounter along the way.

“Practice kindness and gratitude and forgiveness….and start with yourself,” he advised the graduates. “The stories that you tell yourself, and the voices that you use to tell yourself things, matter.”

Howell’s parting words were, perhaps, particularly relevant to those about to enter an industry characterized by constant striving. “Your success is not as important as you. You are more important than your success. Remember that,” he said.

“I’ll see you at the north pole.”

Making the world a better place

One of the Allen School’s graduation traditions is recognizing accomplished alumni who exemplify the qualities of technical excellence, leadership and service. While the pandemic disrupted these plans over the past two years, professor Ed Lazowska, the Bill & Melinda Gates Chair Emeritus at the Allen School, was finally able to reprise his customary role in the program to recognize 2020 recipients Emma Brunskill and Kirk Glerum, and 2022 recipients Brad Calder and Heather Underwood.

“You’re joining a long line of men and women who have built on their Allen School education to go out and make the world a better place,” Lazowska informed the graduates.

Emma Brunskill (B.S., ‘00)

Emma Brunskill earned bachelor’s degrees in Computer Engineering and Physics from the UW before earning a Rhodes Scholarship to Oxford University, where she obtained a master’s degree in neuroscience on her way to earning her Ph.D. from MIT. Brunskill subsequently completed a postdoc at University of California Berkeley before joining the faculty of Carnegie Mellon University. She later moved to Stanford University, where her research focuses on the development of robust artificial intelligence systems for use in health care and education that make good decisions despite being inherently data-limited.

“Emma has already amassed an amazing collection of accomplishments and contributions, and unlike me, has decades of them still ahead of her,” Lazowska said with a smile.

Kirk Glerum (B.S., ‘83)

“Customers hate crashes.” Those words, and what followed them in a two-page memo Kirk Glerum wrote back in 1998, would end up revolutionizing software reliability. Glerum was a member of the Microsoft Office team, which he joined a few years after graduating from the UW with degrees in Computer Science and Mathematics. With web-based communication becoming more common, he envisioned a way to save future customers from the sight of the dreaded dialog box by introducing a crash reporting system to enable the company’s developers to issue fixes. Glerum’s solution was, Lazowska noted, “a game-changer for Microsoft which ultimately became common across the industry.”

Glerum spent 22 years at Microsoft. Now “happily retired,” he and his family have supported his alma mater in multiple ways, including creation of the Glerum Family Endowed Scholarship and Glerum Family Endowed Fellowship to support Allen School undergraduate and graduate students who demonstrate financial need.

Brad Calder (B.S., ‘91)

Brad Calder is another who earned degrees in both Computer Science and Mathematics from the UW, after which he went on to earn his Ph.D. from the University of Colorado at Boulder. From Digital Equipment Corporation’s Western Research Lab, to the University of California San Diego faculty, to Microsoft and, now, Google, “Brad has truly done it all,” observed Lazowska. 

Before leaving academia for industry, Calder graduated 14 Ph.D. students and published over 100 research papers on systems, architecture and compilers. At Microsoft, Calder was a member of the team that founded the company’s Azure cloud project in 2006. Now, at Google, he serves as Vice President and General Manager of Google Cloud Platform and Technical Infrastructure. In this role, he oversees product and engineering for hardware, compute, networking, storage, databases, and data analytics.

Heather Underwood (B.S., ‘09)

Heather Underwood is a prime example of the almost limitless paths open to holders of a computer science degree. Her research has spanned computer science, global health, human-centered design, education and international development. While working on her Ph.D. at CU Boulder advised by fellow Allen School alum John Bennett (Ph.D., ‘88), Underwood developed PartoPen, a digital pen application used to monitor maternal labor and reduce birthing complications in the developing world. After serving on the faculty of CU Boulder and as executive director of Denver BioLabs, she served as a Biodesign Fellow at Stanford University on the way to becoming a full-fledged medical device and health technology entrepreneur.

Currently CEO of EvoEndo, which has developed a safer and more affordable single-use alternative to sedated endoscopy, “Heather, like all of our Alumni Impact Award recipients, is changing the world,” Lazowska concluded.

Recognizing the next generation of leaders and innovators…

Outstanding Senior Awards

The Allen School recognized two graduating students with Outstanding Senior Awards for demonstrating superior scholarship, leadership potential and the ability to create and apply new knowledge in the field of computing.

Honoree Joseph Schafer earned a bachelor’s degree in Computer Science with a minor in Ethics. As a social media data analyst in the UW Center for an Informed Public, Schafer has made significant contributions to qualitative and quantitative research to understand and respond to the spread of mis/disinformation on social media on topics related to politics, elections and the COVID-19 pandemic. Schafer also served as a teaching assistant (TA) and as an officer of the Student Advisory Council. He recently earned a Graduate Research Fellowship from the National Science Foundation to continue his research as a Ph.D. student in UW’s Department of Human Centered Design & Engineering.

Recent Computer Engineering graduate Peter Michael (B.S., ‘21) was honored for his research contributions at the intersection of computer graphics, vision, and machine learning, with a particular emphasis on machine learning-based virtual green screen algorithms — similar to those used in Zoom’s background replacement feature — through a year-long collaboration between UW and Runway ML. He also served as a TA for courses focused on all three subjects and in linear algebra. Michael, who completed his bachelor’s degree last fall and went on to earn his fifth-year master’s from the Allen School in just two quarters, will pursue a Ph.D. at Cornell University next year.

Undergraduate Service Awards

The Undergraduate Service Awards recognize outstanding graduating seniors who have taken an active role in building community by contributing to Allen School activities and events. This year, the school honored four graduates for their service.

Nayha Auradkar was described as “fiercely dedicated to making the communities around her more inclusive.” After serving as president of Huskies Who Stutter, Auradkar founded and led Ability, an Allen School student group focused on connecting students with disabilities and raising awareness of accessibility issues. She also spent nearly two and a half years as chair of ACM-W focused on cultivating a community for women in computing.

Neha Jagathesan “goes above and beyond in everything she does.” This holds particularly true for her work with the Allen School’s Diversity & Access team, for which she has served as an ambassador and lead ambassador helping to build high school students’ interest in computing, and her contributions to the school’s five-year strategic plan for increasing diversity, equity, inclusion and access throughout our community.

Lucy Jiang is known as a “phenomenal student leader” who has taken on many roles in service to the Allen School community. As chair of the UW student chapter of the Association for Computing Machinery (ACM), she oversaw the organization’s first-ever fundraisers to support local causes such as the University District Food Bank, Code.org, and Seattle Children’s Hospital. She also represented the student voice on the school’s Diversity Committee and Curriculum Committee.

Aerin Malana co-founded and chaired GEN1, an Allen School student group that offers support for those who are the first in their families to pursue a U.S. bachelor’s degree. “Committed to bringing visibility and fostering community” among first-generation students, Malana helped surface a college experience that, too often, can be an invisible one. She has also served as an officer of ACM-W and handled logistics for the DubHacks collegiate hackathon.

Best Honors Thesis Award

Each year, the Allen School recognizes a graduating senior who has completed an outstanding independent research project working with a faculty advisor as part of the requirements for Allen School honors. The 2022 Best Honors Thesis Award went to Lucy Jiang for “Flipping the Script: Co-Designing Systems to Support Blind and Low Vision Audio Description Scriptwriters,” completed under the supervision of professor emeritus Richard Ladner. Audio description is an essential function for making videos accessible to BLV audiences, but those audiences are typically excluded from the AD creation pipeline. Jiang conducted interviews and user studies with BLV audiences and AD writers to understand the barriers to accessibility and then applied those insights to the design of AccessbleAD, a system for making AD writing more accessible to BLV users.

…And honoring those who inspired them

Bob Bandes Memorial Award

The Bob Bandes Memorial Award recognizes outstanding teaching assistants (TAs) in the Allen School for their contributions to the classroom and their fellow students’ success. This year, the school selected three winners and three honorable mentions out of approximately 200 TAs nominated by faculty and the students who learned from them.

Winner Shreya Jayaraman has served as a TA for a total of 8 quarters for Foundations of Computing I and II, as both an undergraduate and a graduate student in the Allen School’s BS/MS program. According to one faculty member who worked with her, “Shreya was one of the best TA’s I’ve ever worked with: knowledgeable, responsible, and a natural teacher.”

Fellow winner Soham Pardeshi has been a TA as both an undergraduate and a graduate student in the BS/MS program for a near-record 14 quarters spanning five different courses: Computer Programming II, Intermediate Data Programming, Foundations of Computing I, Software Design and Implementation, and Introduction to Algorithms. According to one student, “Soham is by far the best TA I have had at UW. It is obvious he cares about the wellbeing and success of his students.”

Last but not least, winner Allie Pfleger, who is about to enter the Allen School’s BS/MS program, is also about to enter her 7th quarter as a TA this summer. As an undergraduate, she assisted with multiple quarters of Foundations of Computing I, Systems Programming and The Hardware/Software Interface. According to one of her former students, “She deserves more than this award, she deserves part of my degree when I eventually earn it!”

The Honorable Mention recipients were Dylan Hartono, Abhishek Shah, and Nicolas Suhardi. Students who studied with Hartono, an undergraduate TA for five quarters, lauded him for being “efficient, thorough, knowledgeable, and kind.” Shah, a student in the BS/MS program, has served as a TA for four quarters and was recognized for going the extra mile to help students while offering “an engaging and welcoming learning experience.” Suhardi, an undergraduate who has assisted with five quarters of the Introduction to Programming course, was recognized for doing his best to help students develop “a thorough understanding and love of CS.”

ACM Teaching Awards

Lucy Jiang, president of UW ACM, announced the recipients of the ACM Teaching Awards highlighting faculty excellence. This year, the students broke from tradition by opting to recognize three faculty members for their contributions to the student experience in the Allen School.

Teaching professor and Allen School alum Hunter Schafer (B.S., ‘16, M.S., ‘18) was honored for his contributions to 100-level courses, including Introduction to Computer Programming and Intermediate Data Programming. “Students both within the Allen School and from other majors appreciate his dedication to making computer science more approachable.”

Teaching professor Robbie Weber (Ph.D., ‘20) is another alum who, despite not having taught for very long, has already made an impact. In 300-level courses such as Foundations of Computing I and II and Data Structures and Parallelism, Weber is known for having “crystal clear and enjoyable lectures that students are excited to attend.”

Finally, UW ACM recognized professor Tadayoshi Kohno, the Allen School’s Associate Director for Diversity, Equity, Inclusion and Access and co-director of the Security & Privacy Research Laboratory. In addition to his commitment to creating a welcoming and supportive environment, Kohno is credited for making the topics in his 400-level courses “accessible and entertaining…he has even re-inspired students’ love for computing as a field.”

During the program, the Allen School also took the opportunity to recognize in person the award recipients from 2020 and 2021. The Allen School awarded approximately 700 degrees in the 2021-2022 academic year.

Congratulations to our award recipients and all of our graduates! Please keep in touch! Read more →

Professor Shayan Oveis Gharan, a member of the Allen School’s Theory of Computation group, was named a 2022 Simons Investigator by the Simons Foundation for his innovative approach to fundamental problems in algorithm design and combinatorial optimization. The Simons Investigator Award is designed to support outstanding theoretical scientists in mathematics, physics, astrophysics and computer science as they pursue creative new research directions, mentor junior scientists, and provide leadership within their respective fields.

Oveis Gharan is perhaps best known in theoretical computer science circles for his devotion to the Traveling Salesperson Problem — a devotion that has propelled him to achieve state-of-the-art results on a core research question in combinatorial optimization with practical applications in many other domains. His impact stretches back to his time as a Ph.D. student, when he worked with his advisor, Stanford University professor Amin Saberi, and McGill University professor Mohit Singh to produce the first improved approximation algorithm for the special case of metric TSP called graphic TSP in 35 years. Their simple yet powerful algorithm, which drew upon ideas from probability theory, graph theory and polyhedral theory, earned the Best Paper Award at the 52nd annual IEEE Symposium on Foundations of Computing (FOCS 2011).

After his arrival at the University of Washington in 2015, Oveis Gharan continued to make progress on his favorite problem. After a decade of effort that began during his Ph.D., he and Allen School colleague Anna Karlin and Ph.D. student Nathan Klein managed to extend the 2011 result and design the first improvement over the Christofides algorithm for any metric in more than 40 years. In addition to the temporal significance, the result was hugely symbolic: Oveis Gharan and his co-authors had devised the first algorithm capable of producing a solution that costs less than 50% above the optimum. The team’s achievement earned the Best Paper Award at the 53rd annual Symposium on Theory of Computing (STOC 2021). 

Despite the seriousness of the subject — after all, the TSP is one of the problems underpinning the field — it’s evident that Oveis Gharan genuinely enjoys the challenge. And his collaborators enjoy it right along with him.

“Shayan is technically brilliant and intellectually fearless. He tackles only the hardest and most fundamental problems. These are problems that have remained open for decades, despite the attention of numerous researchers. And time and again, to my and other colleagues’ amazement, he makes progress on those problems,” said Karlin. “I cannot resist adding that he is also the most enthusiastic, generous and fun collaborator one could imagine working with.”

Oveis Gharan’s progress on fundamental — and fundamentally hard — problems extends beyond TSP. One of his recent results that has spurred a flurry of follow-on work within the theoretical computer science community resolved a two-decades-old open problem concerning the sampling of independent sets of a graph up to the computational complexity threshold. In the paper “Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model,” Oveis Gharan and his co-authors, Allen School Ph.D. student Kuikui Liu and Stanford University professor Nima Anari, showed for the first time that Glauber dynamics — an algorithmic tool used in statistical physics for modeling ferromagnetism — mixes in polynomial time for any graph, not just a subset of graphs, up to the phase-transition threshold, after which the problems become computationally intractable. After much follow-on work, another team subsequently built on their result to finally show that one can sample an independent set of a graph, up to the phase-transition threshold, in near-linear time — essentially, in the same time as sorting the vertices of the graph. Although the work is not yet two years old, having first appeared at FOCS 2020, it has already inspired more than 50 follow-on papers and was subsequently featured in the SIAM Journal of Computing published by the Society for Industrial and Applied Mathematics.

The above result built on previous work by the team in conjunction with UW Mathematics professor Cynthia Vinzant — at the time, a faculty member at North Carolina State University — that linked the analysis of Markov chains and the field of high dimensional expanders. In one of a series of papers to advance the theory of completely log-concave polynomials to study the combinatorial structure of matroids, they presented the first fully polynomial randomized approximation scheme (FPRAS) for counting the bases of a matroid. This novel approach, which is based on a simple two-step Markov Chain Monte Carlo process, enables the sampling of random spanning forests in a graph to estimate the reliability polynomial of any matroid. In the same paper, Oveis Gharan and his co-authors also proved the 30-year-old Mihail-Vazirani conjecture that the bases exchange graph of any matroid has edge expansion of at least 1. The team earned a Best Paper Award at STOC 2019 for their contributions, which have real-world applications for network reliability, data transmission, and more.

“Shayan is at the forefront of a series of exciting discoveries that are advancing our understanding of the foundations of computing. The impact he’s already made, so early in his career, is astonishing,” said Allen School colleague James R. Lee, who was named a Simons Investigator in 2017. “His application of algebraic and spectral methods to algorithm design and combinatorial optimization is expanding the mathematical and algorithmic toolbox for our entire community. And along the way, he’s making progress on some of the most significant and longest-standing problems in the field.”

Oveis Gharan’s designation as a Simons Investigator is the latest in a string of accolades that he has accumulated since his arrival at the Allen School, including the EATCS Presburger Award from the European Association for Theoretical Computer Science in 2021 and a Sloan Research Fellowship in 2019.

Learn more about the 2022 Simons Investigators here.

Congratulations, Shayan! Read more →