|
Howdy yâall,
Next Monday (3/25/2019) at 12pm in CS 4310, Samuel Drews will give a presentation on a MadPL CAV17 paper on synthesizing programs with probabilistic correctness properties. The abstract for the talk
is below.
- Calvin
Abstract: Our CAV17 paper presented "DIGITS," which synthesizes {0,1}-valued programs that meet some probabilistic correctness property. The algorithm iteratively queries an SMT solver to produce
candidate programs consistent with finite sets of input-output constraints; somewhat surprisingly, DIGITS provably converges to near-optimal solutions by making only polynomially many such queries. In this talk, I plan to (1) give a brief overview of how
our algorithm operates, (2) highlight a few concepts from Computational Learning Theory on which our proof is based--namely "VC Dimension" and the "Sauer-Shelah Lemma"--, and finally (3) prove our polynomial bound (which is practically an immediate consequence
of the aforementioned lemma).
|
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}