Counterexample-Guided Inference of Modular Specifications @SimonsInstituteTOC

Simons Institute | Counterexample-Guided Inference of Modular Specifications @SimonsInstituteTOC | Uploaded 2 months ago | Updated 22 hours ago
Bill Hallahan (Binghamton University)
https://simons.berkeley.edu/talks/bill-hallahan-binghamton-university-2024-07-03
Synthesis of Models and Systems

Modular verification tools allow programmers to compositionally specify and prove function specifications. When using a modular verifier, proving a specification about a function f requires additional specifications for the functions called by f. We present a counterexample guided algorithm to automatically infer these specifications. The algorithm is parameterized over a verifier, counterexample generator, and constraint guided synthesizer. If each of these three components is sound and complete over a finite set of possible specifications, our algorithm is sound and complete as well. Additionally, we introduce additional requirements which extend our completeness result to an infinite set of possible specifications. We conclude with an evaluation demonstrating our technique on a variety of benchmarks.

Machine learning models of differential gene expression

Computing a fixed point of contraction maps in polynomial queries

Bioacoustics and Machine Learning as Key Tools in Conservation

$Hypothesis selection with computational constraints Maryam Aliakbarpour (Rice University) https://simons.berkeley.edu/talks/maryam-aliakbarpour-rice-university-2024-06-21 Extroverted Sublinear Algorithms Hypothesis selection is a fundamental problem in learning theory and statistics. Given a dataset and a finite set of candidate distributions, the goal is to select a distribution that matches the data as well as possible. More specifically, suppose we have sample access to an unknown distribution $P$ over a domain $mathcal{X}$. We assume that $P$ is well-approximated by one of $n$ distributions in a class (called hypotheses), denoted $mathcal{H} coloneqq {H_1, H_2, ldots, H_n}$. The goal is to design an algorithm that outputs a distribution $hat{H} in mathcal{H}$ whose total variation distance from $P$ is nearly minimal. In this work, we study the hypothesis selection problem under memory and time constraints. In particular, we discuss how to achieve a nearly optimal tradeoff between memory usage and sample complexity. Additionally, we explore methods to obtain optimal accuracy via algorithms with nearly optimal time complexity.$

Lessons from Texas, COVID-19, and the 737 Max: Efficiency vs. Resilience | Richard M. Karp...

Conditional Sampling for Distribution Testing

Sparsifying Set Systems for Coverage Problems

A Strong Separation for Adversarially Robust L_0 Estimation for Linear Sketches

Deciding regular games: a playground for exponential time algorithms