ManuscriptsCai, Pavan and Sivakumar showed that it is hard to compute the permanent even with an inversely polynomial success probability, assuming the worst-case hardness of computing the permanent. Their proof combines the LFKN protocol with Sudan’s list-decoding algorithm for Reed-Solomon codes. We given an exposition of their result, as well as several results leading to it.
This talk was given at the Toronto Student Seminar on 17/9/2012.
