Elektrine lite

← Feed

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&#39;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