Lance Fortnow
fortnow@fediscience.org
<p>Professor</p>
Posts
-
View post
In my 1989 thesis I asked if there was an oracle separating IP from MIP. That was before we knew that MIP=NEXP, though that result doesn't relativize. Bouland, Huang, Natarajan, Shalit, Tal and Astra now answer the original question. https://arxiv.org/abs/2609.25680
-
View post
I bring back the Complexity Class of the Week to talk about L_2^P, the set of problems reducible to finding the minimum element of a total linear order. https://blog.computationalcomplexity.org/2026/07/complexity-class-of-week-l2p.html