Hardness amplification proofs require majority… and 15 years
Thoughts 2018-04-09
Summary:
Aryeh Grinberg, Ronen Shaltiel, and myself have just posted a paper which proves conjectures I made 15 years ago (the historians want to consult the last paragraph of [2] and my Ph.D. thesis). At that time, I was studying hardness amplification, a cool technique to take a function that is somewhat hard on average, and […]