2 Replies - 414 Views - Last Post: 13 January 2020 - 10:53 PM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,861
  • Joined: 27-December 08

[News] MIP* = RE

Post icon  Posted 13 January 2020 - 08:44 PM

A few months ago, a lower bound for MIP* (the class of languages that are accepted using a multiprover protocol where the provers have unlimited power and share entanglement) was announced: NEEXP is contained in MIP*. This mirrors the classical setting, in which we have NEXP = MIP (Babai, Fortnow, Lund, 1991).

Up until the last day or so, no known upper bound was known for MIP*. It was conjectured that MIP* could contain all possible recursively enumerable language (RE). This conjecture was resolved in the affirmative; indeed, MIP* = RE. The result that MIP* contains NEEXP was one of the biggest results in the last ten years. MIP* = RE is undoubtedly the biggest complexity theory result of the last ten years.

Here is the paper.

https://scirate.com/...erFKR-3mOeg9N8g

Is This A Good Question/Topic? 1
  • +

Replies To: [News] MIP* = RE

#2 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,861
  • Joined: 27-December 08

Re: [News] MIP* = RE

Posted 13 January 2020 - 10:29 PM

I should also add that the authors resolved an open problem in functional analysis.

Quote

Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.

Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12680
  • View blog
  • Posts: 45,861
  • Joined: 27-December 08

Re: [News] MIP* = RE

Posted 13 January 2020 - 10:53 PM

Here is a blog post explaining the result.

https://mycqstate.wo...asters-project/
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1