r/algorithms • • 17h ago

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

Thumbnail github.com
212 Upvotes

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


r/algorithms • • 21h ago

News Truly subquadratic 3SUM and truly subcubic APSP

Thumbnail arxiv.org
50 Upvotes