Allen School professors Alvin Cheung and Shayan Oveis Gharan were named 2019 Sloan Research Fellows in Computer Science by the Alfred P. Sloan Foundation. The prestigious Sloan Research Fellowship Program recognizes early-career scientists and engineers who have already distinguished themselves through their research and exhibit the potential to make substantial contributions in their respective fields.
Alvin Cheung engages in cross-disciplinary research as a member of the Allen School’s Database and Programming Languages & Software Engineering groups. In his young career, Cheung has produced multiple, paradigm-shifting solutions spanning data management, data analysis, and end-user programming.
“From booking plane tickets to browsing social networking websites, we interact with large amounts of data everyday,” noted Cheung. “My group works on new techniques to help users process and manage data easily, with the goal to simplify software developers’ efforts to build databases and applications without compromising on performance, and enable the rapid development of database applications that provide efficient and reliable data access to all.”
One of Cheung’s key early-career contributions has been his pioneering work on verified lifting, a technique for automatically translating applications written in Java to domain-specific languages such as SQL, Spark, and Hadoop to optimize performance and reduce errors. For example, by consolidating application logic into compact SQL queries in which the SQL engine could identify optimization opportunities, Cheung’s approach increased the speed of applications up to 1,000 fold. The technique also has the effect of “future-proofing” applications driven by big-data systems that are subject to frequent updates.
For another project, Cheung and his collaborators developed methods in theorem proving and model checking to produce Cosette, an automated prover for checking complex SQL queries that can identify bugs contained in hundreds of manually written rules within seconds. Cheung has also contributed to dramatic leaps in end-user programming; for example, he helped develop Scythe to synthesize SQL queries based on input-output examples posted on Stack Overflow by users seeking expert help with writing SQL queries. Their algorithm can answer around 70% of the most SQL-related questions on the platform faster than the human experts can, making it the best SQL synthesizer ever developed.
“Alvin stands out for his interdisciplinary approach and keen intuition regarding how systems are likely to perform, which has enabled him to crack problems that appear impossible to solve,” said Allen School Director Hank Levy. “His breakthrough work on verified lifting and other projects will have a tremendous impact on the functions that future systems will be able to deliver.”
Shayan Oveis Gharan is a member of the Allen School’s Theory of Computation group who focuses on the design and analysis of efficient algorithms for solving fundamental NP-hard counting and optimization problems at the heart of the theory and practice of computing. These problems have implications for a wide range of fields, from logistics and marketing, to planning and policy-making, that cry out for new and better computational tools for managing and exploiting the vast quantities of data available.
“I encode a discrete phenomenon in a complex multivariate polynomial, and I understand it via the interplay of the coefficients, zeros, and function values of this polynomial,” explained Oveis Gharan. “Although these polynomials are so large that they cannot be stored in all computers in the world combined, I use their analytical properties to design efficient optimization algorithms for the underlying discrete phenomenon.”
Among Oveis Gharan’s most notable contributions to date are his works on the Traveling Salesman Problem (TSP) and its asymmetric variant — one of the most studied problems in optimization — and his very recent work on counting problems related to matroids. Oveis Gharan and his collaborators studied TSP using analytical techniques, proposing a new class of algorithms for variants of TSP and introducing novel analysis of classical algorithms for this problem dating back 50 years. The team’s efforts produced the first improvement on existing approximation algorithms which broke barriers that had withstood for three decades despite substantial previous attempts within the theoretical computer science community.
Oveis Gharan’s most recent work on counting bases of matroids has profound applications in many areas, such as network reliability. To illustrate, he cited the road network of Seattle, which became heavily blocked due to a recent snowstorm. If each street x in the city will be blocked with probability px, what is the probability that the whole city will be disconnected — that there is no available route from home to work for some residents — and how should the city position its snow plows to minimize the probability of such an event? Oveis Gharan and his group devised efficient algorithms to answer such questions.
“Shayan’s contributions in combinatorial optimization, such as his work on the Traveling Salesman Problem, have had a profound impact on the theoretical computer science community,” observed Levy. “His creative and driven approach has enabled him to break through long-standing barriers and expand our understanding of fundamental theoretical problems that underpin our field.”
Joining Cheung and Oveis Gharan in the class of 2019 Fellows is professor Kelley Harris of the UW Department of Genome Sciences, who was recognized in the computational and Evolutionary Molecular Biology category for her research into the evolutionary history of humans and other species based on large datasets of genetic variation. Each year, the Sloan Foundation selects a total of 126 Fellows from higher education institutions across North America who are making contributions in Chemistry, Computational and Evolutionary Molecular Biology, Computer Science, Economics, Mathematics, Neuroscience, Ocean Sciences, Physics, or a related field.
“Sloan Research Fellows are the best young scientists working today,” said Adam F. Falk, president of the Alfred P. Sloan Foundation, in a press release. “Sloan Fellows stand out for their creativity, for their hard work, for the importance of the issues they tackle, and the energy and innovation with which they tackle them. To be a Sloan Fellow is to be in the vanguard of 21st century science.”
Recent Sloan Fellowship recipients at the Allen School include Maya Cakmak, who was recognized last year for her work in robotics; Ali Farhadi and Jon Froehlich, who were included among the class of 2017 Fellows for their work in artificial intelligence and human-computer interaction, respectively; and Emina Torlak for her contributions to computer-aided verification and synthesis. A total of 35 current or former Allen School faculty members have been recognized through the fellowship program.
Congratulations to Alvin, Shayan, and Kelley!