MathematicsMachine-checked

Gemini agents help prove the Courtade–Kumar conjecture, with a batch of new algorithm results

Google Research with CUHK and other academic co-authors · Antigravity /teamwork agents on Gemini 4 models

The 2013 conjecture says no one-bit summary of a noisy signal carries more information than simply reading off a single input bit. Google says Gemini found counterexamples to a broader version, worked out most of the analytical bounds and interval-arithmetic certificates, and extended the proof from balanced to unbalanced functions without human input; the whole proof is formalized in about 50 million lines of Lean 4. The same post lists about ten further new results, including a deterministic Boolean matrix multiplication algorithm that answers an open question from STOC 2024 and the first n-bit functions needing more than n/2 quantum queries.

Still openGoogle and its co-authors are the only source, and nothing here has been peer reviewed or independently reproduced. People supplied key steps: the CUHK team proposed the function that cut the problem to a 14-variable optimization and gave one analytical bound. Google gives no count of problems attempted or failed.

Machine-checked. A formal proof compiles in a proof assistant such as Lean. People have not yet confirmed that it proves what the announcement says. How entries are graded

Record

  1. Added to the ledger

AI Discovery Ledger Weekly

One email every Friday, about a three-minute read: the week's lead result, the grades that moved up or down, what else was logged, and what is still open.

Unsubscribe from any issue. Prefer a feed reader? Follow by RSS.