Ben Brubaker (@quantamagazine.org) on Yumou Fei, Dor Minzer and Shuo Wang's proof of 4-to-1 Conjecture: www.quantamagazine.org/as-ai-closed...
@booleananalysis.bsky.socialRyan O'Donnell
@booleananalysis.bsky.social
@booleananalysis.bsky.social
@nutanlimaye.bsky.socialReposted by @booleananalysis.bsky.socialUnbelievable stuff!
arxiv.org/abs/2610.067...
APSP and 3SUM refuted!! This is big.
@booleananalysis.bsky.socialWho skips Delivering Maybes??
@ccanonne.github.ioReposted by @booleananalysis.bsky.socialThe Call for Papers for #STOC2027 is up! Importantly, the PC "will place substantial weight on the quality of exposition, and clarity of technical arguments and proofs"
Also:
- Public posting requirement
- Required video submission
and more.
Deadline: ⏰ Nov 2, AoE
@csds-bot.bsky.socialReposted by @booleananalysis.bsky.socialSahil Singla: The Matroid Secretary Conjecture is True https://arxiv.org/abs/2609.14555 https://arxiv.org/pdf/2609.14555 https://arxiv.org/html/2609.14555
@booleananalysis.bsky.social... one might strive further to get the best of both worlds: "Rich" 2-to-1 with perfect completeness (eccc.weizmann.ac.il/report/2019/...). That would imply both results. Perhaps the rumors might concern this?
@booleananalysis.bsky.socialI guess this result is morally close to 2-to-1 Conjecture with perfect completeness. (Maybe with tweaking you can get 4->2, who knows.) Then it's true that UGC is somewhat different, being stronger in one sense (1-to-1) and weaker in another (imperfect completeness). But...
@booleananalysis.bsky.socialOutstanding progress towards the Unique Games Conjecture posted by Yumou Fei, Dor Minzer, and Shuo Wang: eccc.weizmann.ac.il/report/2026/...
👀
@booleananalysis.bsky.socialAm teaching grad complexity theory at CMU; about 1/3 of the lectures will be new (vs. last time), 'modern' results. Videos are going onto www.youtube.com/@ComplexityT... which will later also feature student videos.
We did Williams (/Cook-Mertz/Shalunov) TIME(t) in SPACE(~√t) today.
@booleananalysis.bsky.socialI gave a talk at Carnegie Mellon about the recent proof (by OpenAI) of the existence of a non-sofic group: