Sarah M. Morin

CS PhD student at UC Berkeley advised by Joe Hellerstein and Max Willsey.

Research

How can we bridge the gap between the powerful theoretical potential of programming languages research and its practical implementation in complex, real-world systems? I believe we can use novel languages, techniques, and formal frameworks to improve the performance, reliability, and security of distributed systems from the ground up.

My current project asks a deceptively simple question: when can we optimize a program by optimizing its pieces? Bellman’s principle of optimality – which forms the foundation of dynamic programming – tells us that an optimal solution is composed of optimal solutions to its sub-problems. But many optimization problems violate this principle in subtle ways: a locally suboptimal choice for a sub-problem might be exactly what’s needed to unlock a better solution downstream. Developers work around this with ad hoc, domain-specific techniques, but there is no general theory of when and why these heuristics are necessary.

My work develops such a theory: a general framework for determining precisely when the principle of optimality holds and a strategy for ““lifting” problems that violate it into a form that satisfies it. Additionally, I present the multe-graph, a compact data-structure for representing these compositional optimization problems that is a variant of a traditional e-graph. The goal is to draw a concrete connection between related ideas that have developed independently across optimization, algorithms, and programming languages research. Stay tuned for updates!

Background

I earned my B.S. in Computer Science from The George Washington University. During my time as an undergraduate I worked as a Research Assistant for Professor Poorvi Vora and contributed to several publications on risk-limiting audits to statistically verify election outcomes. I also served as a Teaching Assistant in the Computer Science Department and taught for the Computer Architecture, Systems Programming, and Discrete Structures courses.

After graduating from GW, I joined Oracle as a Software Engineer on the File System Storage team of Oracle Cloud Infrastructure (OCI) where I was later promoted to Member of Technical Staff. As a developer on the data-plane I was given the opportunity to tackle many complex problems in distributed storage such as introducing support for SMB protocol and building a user quota enforcement system.

I live in San Francisco with my partner, Gus, and our cats, Zuko (yes, as in Avatar: The Last Airbender) and Kiwi. In my free time, I enjoy cooking, knitting, playing pool, and watching hockey. Although I have quite a few hobbies, there is nothing I enjoy more than learning and solving problems.

latest posts

Dec 18, 2024	Design Documentation

selected publications

USENIX Security

Minerva– An Efficient Risk-Limiting Ballot Polling Audit

Filip Zagórski, Grant McClearn, Sarah Morin, Neal McBurnett, and Poorvi L. Vora

In 30th USENIX Security Symposium (USENIX Security ’21), Aug 2021

Abs PDF

Evidence-based elections aim to produce trustworthy and compelling evidence of the correctness of election outcomes, enabling the detection of problems with high probability. They require a well-curated voter-verified paper trail, compliance audits, and a rigorous tabulation audit of the election outcome, known as a risk-limiting audit (RLA).

This paper focuses on ballot polling RLAs which can require that a very large sample of ballots be drawn. The main ballot polling RLA in use today, BRAVO, is designed for use when single ballots are drawn at random and a decision regarding whether to stop the audit or draw another ballot is taken after each ballot draw. But in practice, ballot polling audits draw many ballots in a single round before determining whether to stop.

Direct application of BRAVO to large rounds results in considerable inefficiency. We present MINERVA, a risk-limiting audit that addresses this problem. When compared to the BRAVO stopping rule being applied at the end of the round, for a first-round with 90% stopping probability, MINERVA halves the number of ballots required across all state margins in the 2020 US Presidential election. When compared to the BRAVO stopping rule being applied after examination of individual ballots, MINERVA reduces the number of ballots by about a quarter. MINERVA requires that round sizes are predetermined; this does not appear to be a drawback for large first rounds which have been typical choices for election officials.

Ballot-polling audits are the leading option in most states. MINERVA significantly reduces the necessary expense for contests with close margins and thus makes adopting RLAs easier. Wider adoption of RLAs is a critical step in increasing public confidence in elections.

MINERVA was used in Ohio’s pilot RLA of the primaries in May 2020 in Montgomery County. We provide open-source implementations of MINERVA. The code has been integrated as an option in Arlo, the most widely-used RLA software.
VOTING 20

A Note on Risk-Limiting Bayesian Polling Audits for Two-Candidate Elections

Sarah Morin, Grant McClearn, Neal McBurnett, Poorvi L. Vora, and Filip Zagórski

In Fifth Workshop on Advances in Secure Electronic Voting, Financial Cryptography, 2020

Abs PDF

This short paper provides a general form for a polling audit that is both Bayesian and risk-limiting: the Bayesian Risk-Limiting (Polling) Audit, which enables the use of a Bayesian approach to explore more efficient Risk-Limiting Audits. A numerical example illustrates the implications to practice.