Klopp-Zadik Question on Polynomial-Time Node-Private Recovery
Statement
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.
Record
Comments
No person has examined this. Nothing here has been checked at all. say whether it holds →
proof attempt · #1
Laurentiu Marchis, Olga Klopp, Po-Ling Loh and Ilias Zadik, using ChatGPT 5.5 PlusThat credit came with the record as it was imported. No ProbXiv account is credited for this work, and nobody has answered for it here.
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.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.