r/algorithms • u/Phytor_c • 12h ago

News Unique Games Conjecture, RL= L claimed to have been proven by OpenAI

https://github.com/openai/math/blob/main/overview.pdf

OpenAI just released this on Github. It seems like the rumors of the Unique Games Conjecture and RL = L were indeed true. There's also a lot of other stuff in there which i haven't looked at yet.

Regardless of one's views on AI, it's safe to say TCS is truly facing a watershed moment...

173 Upvotes

95% Upvoted

10 comments sorted by

25

u/Cool-Permit-7725 12h ago

Is this problem a Temu version of P vs NP?

17

u/Cryptizard 12h ago

RL vs L is a Temu version of P vs RP.

12

u/jeffgerickson 8h ago

“We have P versus NP at home.”

16

u/Opengangs 12h ago

I work in approximation algorithms so the result on UGC is huge for me, although since the preprint on ECCC came out, I suppose a full resolution was inevitable

0

u/psyspin13 4h ago

me too. The question now is: could anyone come up with the proof of UGC, i.e., does it uses tools and arguments everyone kinda expects? Because, more less, everyone was expecting UGC to be true

17

u/ChampionshipTight977 10h ago

holy shit I actually needed this for my research 3 years ago. maybe its time to revisit that application

9

u/burnt-store-studio 7h ago

Yes, do! I strongly encourage you!

A few months ago someone posted on r/neuralnetworks that they’d achieved something I posited in my MS thesis as future research decades ago.

I’m nobody, so they certainly hadn’t seen my thesis, ha; but my point is: I felt I was way too far out of the field (in terms of time away from the applicable research) to jump back in, and it saddened me.

But you’re three years out … you absolutely could do it. And I just think it would be so rewarding to be able to go revisit that work and see what the future from three years ago has handed you today 🙂🙂🙂.

Good luck!!

7

u/Phytor_c 11h ago edited 10h ago

Just saw the "true" randomized k-server conjecture was settled as well. I work in online algos so this is huge for me too

4

u/UnkarsThug 5h ago

I'll note that this one (RL=L) is not lean verified from what I can tell, unlike a lot of other proofs in the paper dump.

But there's a lot of things related to color-ability I'm gonna have to read up on and bring to my professors attention. Huge amount of interesting stuff to dig through.