Listenly

What unexpected connection emerged between random self-reducibility and interactive proofs for hard computational problems?

Answered at 22:54 in The 'Useless' Theory Behind Modern SNARKs (ft. Gödel Prize Winner Noam Nisan) · a16z crypto show

— questions searchable right now

What unexpected connection emerged between random self-reducibility and interactive proofs for hard computational problems?

Nisan discovered that Richard Lipton's proof of random self-reducibility for the permanent function could lead to an interactive proof. Initially Nisan could not believe Lipton's result because he knew that random self-reducibility could imply an interactive proof, yet the permanent is a notoriously difficult function. Upon closer inspection, he realized Lipton's approach worked because Lipton handled multiple instances rather than just one, enabling an interactive proof for this extremely hard problem.

Noam Nisan on a16z crypto showAll answers from this podcast →
Full answer and detailsRead the whole answer, key facts and every other question from this episode

In short

Nisan discovered that Richard Lipton's proof of random self-reducibility for the permanent function could lead to an interactive proof.

Noam Nisan · The 'Useless' Theory Behind Modern SNARKs (ft. Gödel Prize Winner Noam Nisan) · a16z crypto show · answer at 22:54

Key takeaways

  • Nisan discovered that Richard Lipton's proof of random self-reducibility for the permanent function could lead to an interactive proof.

The full answer · about 2 min

Nisan discovered that Richard Lipton's proof of random self-reducibility for the permanent function could lead to an interactive proof. Initially Nisan could not believe Lipton's result because he knew that random self-reducibility could imply an interactive proof, yet the permanent is a notoriously difficult function. Upon closer inspection, he realized Lipton's approach worked because Lipton handled multiple instances rather than just one, enabling an interactive proof for this extremely hard problem.

More answers from this episode

 ·  All answers from a16z crypto show →
—
—
0:00
0:00