A certifying algorithm is an algorithm that provides a certificate with each answer that it produces. The certificate is a short piece of evidence that proves that the answer is correct. This is highly desirable among practitioners, who are reluctant to accept on faith that an implementation is bug-free even when the underlying algorithm has been proven to be correct. In view of this, it is surprising that many published algorithms are non-certifying. The issue has been largely neglected by algorithms theorists. This situation presents a wide-open research opportunity.
The talk will use two problems in graph theory to illustrate how a non-certifying algorithm can be turned into a certifying one. It will include a discussion of open problems and potential thesis topics.