Breakthroughs Weekly — 12 October 2026
A human-written proof that 4-to-1 games are NP-hard lands in complexity theory, and the Nobel Prize in Physics goes to IceCube neutrino pioneer Francis Halzen.
A proof that 4-to-1 games are NP-hard advances Khot’s conjectures
ECCC · 14 Sep 2026 · Complexity theory
Yumou Fei, Dor Minzer and Shuo Wang show that distinguishing perfectly satisfiable 4-to-1 games from nearly unsatisfiable ones is NP-hard, which confirms a weakened form of Khot’s 2-to-1 games conjecture. As consequences, no algorithm can efficiently colour a 3-colourable graph with any fixed number of colours unless P equals NP, and a related hardness result follows for hypergraphs. The report is not yet peer reviewed and was first posted in a rough state; a fuller revision appeared on 8 October. Quanta Magazine’s coverage this month quotes Ryan O’Donnell of Carnegie Mellon calling it “another truly great one”, which is how it reached wider attention.
Francis Halzen wins the 2026 Nobel Prize in Physics for IceCube neutrino work
Daily Maverick · 6 Oct 2026 · Physics prize
The Nobel committee announced the 2026 physics prize on 6 October, citing Halzen’s contributions to the IceCube Neutrino Observatory and the discovery of high-energy neutrinos of astrophysical origin. This is an award, not a new result: it recognises earlier experimental work that opened a way to observe cosmic sources through neutrinos rather than light. The Nobel Foundation’s own page could not be retrieved this run, so this item cites secondary coverage.