I'd just first like to say that I love reading your work. I'm always delighted when I see an update on Shtetl-Optimized and I admire how you are both simultaneously rigorous and funny in your papers and posts. Your PnP survey stands out in my mind as a truly fun and insightful read in particular.
Two questions:
1. Any meaningful updates you'd make to the PnP survey today?
2. As a total aside, I'm curious for your thoughts on blockchains. Not specifically proof of work as a BFT system per se, but more broadly curious to what degree you think "trustless" transactions and data processing might or might not be transformative.
Apologies in advance if you've recently provided thoughts on either of these topics and I've sadly missed them!
1. The P vs. NP survey is only 2 years old, so all the edits I'd make to it now would be rather minor ones: for example, including some more recent circuit lower bounds of Ryan Williams and others, some more no-go results for Geometric Complexity Theory, and Raz and Tal's BQP vs. PH breakthrough (which required a new circuit lower bound, though not of a kind that can evade the natural proofs barrier).
Thanks for the reply! And apologies I didn't realize the autocorrect on my phone turned "PvNP" to "PnP". I'll read up on the recent works you mentioned here. Appreciate the link to your comment on Blockchain technology as well.
If you still have time to answer questions.. is there any recent work in the cryptographic or blockchain space you see as standout? I haven't referred recently to any citations or updates, but found Ben-Sasson, Bentov, Horesh and Riabzev's recent work (https://eprint.iacr.org/2018/046) on ZK-STARKs intriguing.
Two questions:
1. Any meaningful updates you'd make to the PnP survey today?
2. As a total aside, I'm curious for your thoughts on blockchains. Not specifically proof of work as a BFT system per se, but more broadly curious to what degree you think "trustless" transactions and data processing might or might not be transformative.
Apologies in advance if you've recently provided thoughts on either of these topics and I've sadly missed them!