VibeMathedMath problems solved by AI

Nikolov-Ullman Pure-DP Query Release Conjecture

Nikolov and Ullman asked, as Open Problem 1 on DifferentialPrivacy.org, whether kk statistical queries over a universe of size TT can be released under pure differential privacy at the square-root error rate that the known lower bounds suggest, rather than the cube-root rate of the classical small-database method. They can: for every nn and ε>0\varepsilon > 0 there is an ε\varepsilon-differentially private mechanism with expected error O(min⁡{1,log⁡(2T)log⁡(2k)/(εn)})O(\min\{1, \sqrt{\log(2T)\log(2k)/(\varepsilon n)}\}).

Result
Proved(see note)
Status
Resolved
AI contribution
AI-assisted
Method
Argument
Field
Differential privacy
Posed by
Aleksandar Nikolov, Jonathan Ullman
Year posed
—
Years open
—
Solved
2026-07-22
Model
Codex, Harmonic Aristotle
Vendor
OpenAI / Harmonic
Collaborators
Jack Fitzsimons
Verification
Unreviewed
Publication
Preprint
Significance
20 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

information-theoretic; a polynomial-time implementation remains open

What the AI did

The generative-AI disclosure states that Codex and Aristotle were used in connection with Lean formalization and proof search, and that Codex also gave editorial feedback on clarity and organization. Proof search is a mathematical contribution, but the disclosure does not say which steps came from where.

Verification

Single-author arXiv preprint with a companion Lean 4 development that the paper says machine-checks the finite construction, pure privacy after deterministic decoding, and the all-regimes upper bound, with an axiom audit and a paper-to-Lean crosswalk in the artifact. We have not compiled it. Not yet peer-reviewed.

Source

arXiv:2607.20418 - Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

Discussion