Determinations: Theory and Practice

Tuesday, September 29, 2026, 11 a.m.

Bahen Centre for Information Technology, BA 3200

This lecture is open to the public. Please register using the link below

Abstract:

Every time a language model writes a proof, a plan, or a program, it does something our usual theory of computation does not explain: it commits, token by token, to one answer among many admissible ones. This is not the familiar picture of computation as evaluating a function — given an input, produce the one correct output. It is the separate task of resolving a relation: choosing one of many admissible outcomes by making irrevocable commitments that progressively narrow the possibilities. This setting is by no means AI-specific; it is surprisingly widespread in modern computing. A distributed system in the cloud must settle on one consistent state from a set of admissible ones; a database system must choose an ordering of concurrent transactions; a market or auction must select one equilibrium. 
 
We call the structure of commitments a determination. This talk develops a theory of determinations around three questions, each with a clean answer: 
 
1. When are irrevocable commitments unavoidable? Exactly when a specification's outcomes are non-monotone over history. This Complete CALM Theorem generalizes a foundational result from databases and distributed systems, and yields a Complete CAP Theorem as a corollary. 
 
2. How many commitments are required? We introduce determination complexity: the number of irreducible sequential layers a task forces. It is a new axis, with autoregressive generation (think Chain-of-Thought) as a natural witness of orthogonality from computational complexity. 
 
3. Why would a particular outcome emerge, and how likely is it? These are determination provenance questions, answered by extending the theory of data provenance to the determination setting. The algebra is different from classical provenance — a filtration — suggesting a bridge to measure theory and probability. 
 
The theory pays off in practice. Hydro, an open-source Rust framework for distributed programming, instantiates it directly: the compiler rejects programs with unintended race conditions, and applies Complete CALM to report the consistency level of each output. Hydro also points toward a new kind of observability that can answer the "why" questions above. 
 
The talk is aimed at systems, theory, and AI researchers alike. 

Bio:

Joseph M. Hellerstein is the Jim Gray Professor of the Graduate School at UC Berkeley, and a VP/Distinguished Scientist at Amazon Web Services where he leads the Hydro open source project. His research focuses broadly on data-oriented systems and the way they drive computing. This spans topics in database systems, distributed computing, programming languages and AI. Hellerstein is an ACM-SIGMOD Codd Award winner and a Fellow of the ACM. His industry work prior to AWS includes co-founding multiple startups and leading industrial research teams.