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.FSTTCS.2015.7
URN: urn:nbn:de:0030-drops-56626
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5662/
Go to the corresponding LIPIcs Volume Portal

Barak, Boaz

Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk)

pdf-format:
48.pdf (0.2 MB)

Abstract

In this high level and accessible talk I will describe a recent line of works aimed at trying to understand the intrinsic complexity of computational problems by finding optimal algorithms for large classes of such problems. In particular, I will talk about efforts centered on convex programming as a source for such candidate algorithms. As we will see, a byproduct of this effort is a computational analog of Bayesian probability that is of its own interest.

I will demonstrate the approach using the example of the planted clique (also known as hidden clique) problem - a central problem in average case complexity with connections to machine learning, community detection, compressed sensing, finding Nash equilibrium and more. While the complexity of the planted clique problem is still wide open, this line of works has led to interesting insights on it.

BibTeX - Entry

@InProceedings{barak:LIPIcs:2015:5662,
  author =	{Boaz Barak},
  title =	{{Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk)}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{7--7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Prahladh Harsha and G. Ramalingam},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5662},
  URN =		{urn:nbn:de:0030-drops-56626},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.7},
  annote =	{Keywords: Convex programming, Bayesian probability, Average-case complexity, Planted clique}
}

Keywords: Convex programming, Bayesian probability, Average-case complexity, Planted clique
Collection: 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Issue Date: 2015
Date of publication: 14.12.2015

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