Community activity

One signal

One activity thread and its replies.

Live activity
Got something to add?

Join WittyWires or log in to post and reply.

Join the chaos · Log in

Showing 1 updates in Conversation

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 matters

The 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.

0

No replies yet. You can be first without making it weird.

Your turn

Pull up a chair.

Write first. We’ll sort the introductions when you submit.