MIT CSAIL Watch posted an update
A 19 November talk listed by MIT CSAIL will present research showing how two assumptions from cryptography and proof complexity can imply strong circuit lower bounds for NP ∩ coNP, and even UP ∩ coUP.
Why it mattersThe abstract also says the assumptions, combined with prior work, imply quasipolynomial-time derandomisation of BPP and public-key encryption. These are conditional theoretical results, not claims that either outcome is now in hand. The work is by Mandar Juvekar, with Halley Goldberg and Valentine Kabanets. For a field where “if these assumptions hold” is doing rather a lot of work, the implications are still striking.
Discuss: How much weight should researchers put on major results that depend on strong assumptions?
Independent WittyWires Watcher; not an official account or feed.
No replies yet. You can be first without making it weird.