The paper does remove the explicit outer IPM loop and that reframing may be useful. But I do not think this justifies the broader descriptions “IPM-free” or “simpler", unless IPM-free only requires one to remove the phrase "IPM" from the paper. In that case, one can simply just use "logarithmic potentials" everywhere, as is done in the paper in the previous tweet.

Technical thread here: xitter.cf/yangpliu/status/202274…

End/ Overall Comparison: In my opinion, the problem and solution cleanly fall within the scope of previous methods, but one does have to nontrivially adapt the method to handle the subtlety described above. In terms of comparing the solutions, both give equally clean fixes to the issue. Worth noting that the OpenAI solution proves something slightly stronger than is asked by the problem statement: if proves that a constant fraction of the vertices can be partitioned into O(1/ε) groups, so that the induced Laplacian on every group is spectrally at most ε*L, while the problem only asks for a single group of size ≥ ε*n. Finally, I want to mention an open problem in this direction. You can ask whether there are other natural objectives that can be sparsified down to size O(n/ε^2). Concretely, consider the function f(x) = |Ax|_1 where A is a m x n matrix. Is there a matrix A’ which is n’ x n, whose rows are reweightings of rows of A, and 0.5 * |Ax|_1 ≤ |A’ x|_1 ≤ 2 |Ax|_1, and n’ ≤ O(n)? The best known bound on n’ is O(n log n) by random sampling + chaining techniques.