Skip to main content

Allen School professor and “SIGACT oracle” Paul Beame recognized with ACM SIGACT Distinguished Service Award

Portrait of Paul Beame with sunlit trees and foliage in the background

Paul Beame, an associate director of the Allen School and a professor in the Theory of Computation group, has been honored with the 2021 ACM SIGACT Distinguished Service Award for his more than 20 years of dedicated and effective support to the theoretical computer science community. Each year, the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory presents the award to an individual or group who has gone above and beyond in service to their colleagues even as they work to advance the foundations of computing. 

Since joining the University of Washington faculty in 1987, Beame has devoted much of his research career to exploring pure and applied complexity to address a range of computational problems in multiple domains. Beyond his research contributions, Beame has dedicated significant time and effort to promoting knowledge-sharing and collaboration within the theoretical computer science community through various leadership roles in ACM, SIGACT, and its sibling organization within the IEEE Computer Society, the Technical Committee on Mathematical Foundations (TCMF). He is also credited with advancing two of the field’s flagship conferences, the ACM Symposium on the Theory of Computing (STOC) and the IEEE Symposium on Foundations of Computer Science (FOCS), through a combination of formal and informal leadership and service. 

FOCS 1999 marked Beame’s first foray into conference leadership, when he took on the role of program committee chair and served informally as a local co-organizer. He subsequently went on to serve as general chair, finance chair, and/or local co-organizer for no fewer than half a dozen more FOCS and STOC conferences between 2006 and 2011. Beyond fulfilling his official leadership duties, over the years Beame has provided organizers of numerous successive conferences with unofficial assistance ranging from identifying potential venues, to recruiting local volunteers, to addressing issues with the online registration system. 

“Paul’s tireless service, in both official and unofficial roles, has been highly instrumental in ensuring the smooth running and continued vitality of the flagship STOC and FOCS conferences and of SIGACT itself,” said ACM SIGACT Chair Samir Khuller, the Peter and Adrienne Barris Professor and Chair of the Computer Science Department at Northwestern University. “In addition to his many official roles, Paul’s influence is also felt, equally significantly, through his unofficial roles as ‘SIGACT oracle’ and advisor to those responsible for running our main conferences every year.”

Following the completion of his term as chair of IEEE’s TCMF in 2012, Beame began his tenure as chair of ACM SIGACT. During the next six years, as he served out his term as chair and immediate past chair of the group, Beame is credited with promoting greater cooperation between the two groups that represented the theoretical computer science community in parallel. He was also instrumental in revitalizing STOC through the introduction of TheoryFest, for which he co-planned and co-organized the first two events in 2017 and 2018. 

As a leader, Beame is known for building in mechanisms for ensuring good management practices will carry forward while building up the infrastructure for running conferences and committees that enables his successors to seamlessly take the reins. And he hasn’t been shy about challenging the conventional wisdom along the way.

“There are typically two distinct types of exceptional leaders for professional organizations,” observed David Shmoys, Laibe/Acheson Professor at Cornell University. “First, there are the people who are detail-focused and excel at making sure that the myriad of lower-level processes work with the precision of a well-engineered system — in a pre-digital world, the standard metaphor would be a Swiss watch. Second are the ‘out-of-the-box’ thinkers who aren’t content with making things run as well as possible within the framework of the status quo, but instead push the organization to improve upon itself by inventing new ways that the systems can run. Paul excels in both dimensions, and this is what makes his service extraordinarily remarkable.”

Even after officially passing the baton to the next slate of leaders and volunteers, Beame continues to be generous with his time and advice to help sustain the community’s momentum.

“Whereas many people who have served in leadership roles view stepping down as a chance to leave obligations behind,” Khuller noted, “Paul has repeatedly viewed it as an opportunity to smooth the path for future incumbents.”

In addition to laying the groundwork for future leaders, Beame was also a vocal champion of open access to SIGACT and other ACM conference proceedings during his time representing SIGACT and the SIG Board. Despite entrenched opposition from some quarters, his position ultimately prevailed. Beginning in 2015, all SIGACT and many other SIG conference proceedings were made open-access in perpetuity via their respective conference websites — including the STOC website, which Beame himself initially built and maintained along with the FOCS website to provide an online history of past conferences and their proceedings. 

“This award is a well-earned honor for Paul, who has been tireless in helping SIGACT move forward,” said Allen School professor emeritus Richard Ladner.

Ladner’s faculty colleague Anna Karlin agreed. “For two decades, Paul has repeatedly stepped up to provide every manner of service to the SIGACT community,” she said. “He is an exemplary recipient of this award.”

Read the award committee’s full citation here, and learn more about the SIGACT Distinguished Service Award here.

Congratulations, Paul!