DROPS

Document

Approximate and Probabilistic Computing: Design, Coding, Verification (Dagstuhl Seminar 15491)

Authors: Antonio Filieri, Marta Kwiatkowska, Sasa Misailovic, and Todd Mytkowicz

Published in: Dagstuhl Reports, Volume 5, Issue 11 (2016)

Abstract

Computing has entered the era of approximation, in which hardware and software generate and reason about estimates. Navigation applications turn maps and location estimates from hardware GPS sensors into driving directions; speech recognition turns an analog signal into a likely sentence; search turns queries into information; network protocols deliver unreliable messages; and recent advances promise that approximate hardware and software will trade result quality for energy efficiency. Millions of people already use software which computes with and reasons about approximate/probabilistic data daily. These complex systems require sophisticated algorithms to deliver accurate answers quickly, at scale, and with energy efficiency, and approximation is often the only way to meet these competing goals. Despite their ubiquity, economic significance, and societal impact, building such applications is difficult and requires expertise across the system stack, in addition to statistics and application-specific domain knowledge. Non-expert developers need tools and expertise to help them design, code, and verify these complex systems. The aim of this seminar was to bring together academic and industrial researchers from the areas of probabilistic model checking, quantitative software analysis, probabilistic programming, and approximate computing to share their recent progress, identify challenges in computing with estimates, and foster collaboration with the goal of helping non-expert developers design, code, and verify modern approximate and probabilistic systems.

Cite as

Antonio Filieri, Marta Kwiatkowska, Sasa Misailovic, and Todd Mytkowicz. Approximate and Probabilistic Computing: Design, Coding, Verification (Dagstuhl Seminar 15491). In Dagstuhl Reports, Volume 5, Issue 11, pp. 151-179, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{filieri_et_al:DagRep.5.11.151,
  author =	{Filieri, Antonio and Kwiatkowska, Marta and Misailovic, Sasa and Mytkowicz, Todd},
  title =	{{Approximate and Probabilistic Computing: Design, Coding, Verification (Dagstuhl Seminar 15491)}},
  pages =	{151--179},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{11},
  editor =	{Filieri, Antonio and Kwiatkowska, Marta and Misailovic, Sasa and Mytkowicz, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.11.151},
  URN =		{urn:nbn:de:0030-drops-58008},
  doi =		{10.4230/DagRep.5.11.151},
  annote =	{Keywords: approximation, model checking, performance, probability, program analysis, systems, verification}
}

Document

DOI: 10.4230/LIPIcs.SNAPL.2015.156

InterPoll: Crowd-Sourced Internet Polls

Authors: Benjamin Livshits and Todd Mytkowicz

Published in: LIPIcs, Volume 32, 1st Summit on Advances in Programming Languages (SNAPL 2015)

Abstract

Crowd-sourcing is increasingly being used to provide answers to online polls and surveys. However, existing systems, while taking care of the mechanics of attracting crowd workers, poll building, and payment, provide little to help the survey-maker or pollster in obtaining statistically significant results devoid of even the obvious selection biases. This paper proposes InterPoll, a platform for programming of crowd-sourced polls. Pollsters express polls as embedded LINQ queries and the runtime correctly reasons about uncertainty in those polls, only polling as many people as required to meet statistical guarantees. To optimize the cost of polls, InterPoll performs query optimization, as well as bias correction and power analysis. The goal of InterPoll is to provide a system that can be reliably used for research into marketing, social and political science questions. This paper highlights some of the existing challenges and how InterPoll is designed to address most of them. In this paper we summarize some of the work we have already done and give an outline for future work.

Cite as

Benjamin Livshits and Todd Mytkowicz. InterPoll: Crowd-Sourced Internet Polls. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 156-176, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{livshits_et_al:LIPIcs.SNAPL.2015.156,
  author =	{Livshits, Benjamin and Mytkowicz, Todd},
  title =	{{InterPoll: Crowd-Sourced Internet Polls}},
  booktitle =	{1st Summit on Advances in Programming Languages (SNAPL 2015)},
  pages =	{156--176},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-80-4},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{32},
  editor =	{Ball, Thomas and Bodík, Rastislav and Krishnamurthi, Shriram and Lerner, Benjamin S. and Morriset, Greg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SNAPL.2015.156},
  URN =		{urn:nbn:de:0030-drops-50242},
  doi =		{10.4230/LIPIcs.SNAPL.2015.156},
  annote =	{Keywords: CrowdSourcing, Polling, LINQ}
}

Search Results

Documents authored by Mytkowicz, Todd

Approximate and Probabilistic Computing: Design, Coding, Verification (Dagstuhl Seminar 15491)

Abstract

Cite as

InterPoll: Crowd-Sourced Internet Polls

Abstract

Cite as

Thanks for your feedback!

Could not send message