License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SNAPL.2015.129
URN: urn:nbn:de:0030-drops-50225
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5022/
Go to the corresponding LIPIcs Volume Portal

Gaboardi, Marco ; Hsu, Justin

A Theory AB Toolbox

pdf-format:
12.pdf (0.4 MB)

Abstract

Randomized algorithms are a staple of the theoretical computer science literature. By careful use of randomness, algorithms can achieve properties that are simply not possible with deterministic algorithms. Today, these properties are proved on paper, by theoretical computer scientists; we investigate formally verifying these proofs.

The main challenges are two: proofs about algorithms can be quite complex, using various facts from probability theory; and proofs are highly customized - two proofs of the same property for two algorithms can be completely different. To overcome these challenges, we propose taking inspiration from paper proofs, by building common tools - abstractions, reasoning principles, perhaps even notations - into a formal verification toolbox. To give an idea of our approach, we consider three common patterns in paper proofs: the union bound, concentration bounds, and martingale arguments.

BibTeX - Entry

@InProceedings{gaboardi_et_al:LIPIcs:2015:5022,
  author =	{Marco Gaboardi and Justin Hsu},
  title =	{{A Theory AB Toolbox}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{129--139},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Thomas Ball and Rastislav Bodik and Shriram Krishnamurthi and Benjamin S. Lerner and Greg Morrisett},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5022},
  URN =		{urn:nbn:de:0030-drops-50225},
  doi =		{10.4230/LIPIcs.SNAPL.2015.129},
  annote =	{Keywords: Verification, randomized algorithms}
}

Keywords: Verification, randomized algorithms
Collection: 1st Summit on Advances in Programming Languages (SNAPL 2015)
Issue Date: 2015
Date of publication: 30.04.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI