Back to search

Cornell University

PROBABILISTIC SEPARATION LOGICS FOR RANDOMIZED ALGORITHMS

Abstract

dc:description.abstract

Randomized algorithms are hard to test, thus accentuating the need for formalmethods to ensure their correctness. When probabilistic separation logic was first developed as a formal method for proving probabilistic independence be- tween program variables, it was unclear whether this approach generalizes to weaker forms of probabilistic separation used in program analysis. We first overview existing work in Bunched logic — the assertion logic underlying separation logic — and probabilistic separation logic for independence in chapter 2. In chapter 3, we extend probabilistic separation logic to reason about negativedependence, a relation in which an increase in one variable makes others less likely to increase. We demonstrate the utility of this program logic by analyzing hash-based data structures, such as Bloom filters. In chapter 4, we introduce a variation of probabilistic separation logic forreasoning about dependence and independence. Specifically, we use it to establish conditional independence between programs variables in simple programs. Last, in chapter 5, we present the unary fragment of BLUEBELL to provide amore ergonomic way to reason about conditional independence and independence. We illustrate its application through more intricate examples drawn from cryptography, security, and probabilistic graphical models. All the program logics developed in this thesis target imperative programsthat can sample from probability distributions.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2025

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bao, Jialu
Chair dc:contributor.chair
  • Hsu, Justin
Committee members dc:contributor.committeemember
  • Kozen, Dexter
  • Halpern, Joseph
  • Martins da Silva, Alexandra

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422685
Dc Identifier Other
ProQuest Submission ID: 15243
ProQuest Publication ID: 32171133

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bao, Jialu. PROBABILISTIC SEPARATION LOGICS FOR RANDOMIZED ALGORITHMS. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120904