LIPIcs.FSTTCS.2015.7.pdf
- Filesize: 216 kB
- 1 pages
Document
Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk)
Author
-
Part of:
Volume:
35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-12-14
Cite AsGet BibTex
Boaz Barak. Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk). In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, p. 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.7
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.7
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.
Keywords
- Convex programming
- Bayesian probability
- Average-case complexity
- Planted clique
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads