How should I treat this prior work? I submitted a theoretical paper about new algorithms to a computer science conference. Now I found out that the most important theorem of my paper was actually proved 20 years ago (in a workshop paper with less than 15 citations). The other theorems/algorithms of my paper are kind of easy corollaries of this result, so this makes the theoretical contribution of my paper lower. However my paper connects these results to a lot of literature of past 20 years to which the old paper has not been connected before, so it still has good motivation and a lot of original contribution.

What should I do if the reviewers do not find this old paper and accept my submission? Could an accept turn into decline if I tell them about this old paper? Would it be ok to just add a footnote where this old paper is cited?
Options:


Ignore the newly found paper for now. The result would be the same as if you learned of the paper just after the conference rather than before. Downside: People might get a chuckle over your lack of knowledge of prior art. Someone might point out the prior work at the conference if you don't mention it there. Some might think you plagiarized. However: You did the work in good faith and submitted in good faith. 
Inform the conference chair of the issue and ask for advice. Tell them you can add a note about the recently found paper OR you can do a rewrite incorporating the old work and emphasizing your own contributions. This assumes there is time and process for rewrites. Downside: The chair may withdraw the paper or just let it go, again assuming good faith. However: You clearly show due diligence. 
Withdraw the paper and rewrite it for the future. Downside: You don't get a publication just now. However: Time can also let you rethink and possibly extend. 


The sticky wicket here is that it was the most important theorem that was previously proven, leaving you, perhaps, with less novelty.