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
- Added to the ledger