Talks

Fall 2015

# On the Existence of Optimal Algorithms

Wednesday, September 30th, 2015 9:30 am – 10:15 am

An *optimal meta algorithm* for a class C of computational problems is an algorithm A that can solve any problem P in C in some time T_P(n) and such that there does not exist an algorithm that can solve P significantly faster. A natural optimal algorithm for a class C in some sense provides the most satisfactory explanation to what makes certain problems in C hard and other problems easy.

In this high level and informal talk I will discuss for what classes of problems we might hope to get natural optimal algorithms, the works on the Sum-of-Squares SDP as a candidate optimal algorithm, and how such optimal algorithms/proof systems give rise to a computational analog of Bayesian probability.

Attachment | Size |
---|---|

On the Existence of Optimal Algorithms | 1.81 MB |