Klopp-Zadik Question on Polynomial-Time Node-Private Recovery
Klopp and Zadik gave an exponential-time node-private algorithm for exact community recovery in stochastic block models and asked whether a polynomial-time algorithm could match it. One can: a Lipschitz surrogate for the penalized likelihood plus an accept-reject sampler gives a high-probability polynomial-time node-private algorithm that nearly matches the exponential-time guarantee.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Differential privacy
- Posed by
- Olga Klopp, Ilias Zadik
- Year posed
- 2026
- Years open
- 0y
- Solved
- 2026-07-10
- Model
- ChatGPT 5.5 Plus
- Vendor
- OpenAI
- Collaborators
- Laurentiu Marchis, Olga Klopp, Po-Ling Loh, Ilias Zadik
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The AI declaration says the paper was written with the model's help and that it played a critical role in brainstorming the initial idea for a polynomial-time algorithm and in providing proof outlines for the main results. Two of the authors are the pair who posed the question.
Verification
arXiv preprint; not yet peer-reviewed.
Source
arXiv:2607.09441 - Near-optimal node-private community estimation in polynomial-time