Yang Liu

@sushnt Yes, good point. I realized later that each subset being light is not equivalent to the sum being light (even if they're vertex disjoint).

@yangpliu Very nice thread and clean exposition! The proof from OpenAI proves something tiny bit even stronger: it proves that a subset of c*n vertices can be partitioned into ~d/eps subsets so that the **sum of these restricted Laplacians L_{S}** is eps-light.

1/ Technical thread on #1stProof Problem 6: finding “spectrally light” vertex subsets in a graph, and how its solution fits into the landscape of spectral sparsification + restricted invertibility. Original thread: x.com/yangpliu/statu…

I don't personally want to rate the proof vs. human researchers. More concretely, I feel that current models so far are quite strong at proving self-contained statements whose solutions we believe are based on ideas in the literature (or are sufficiently short). To me, this framework captures the advances we've seen on both the IMO/competition side and the math research side.

@yangpliu Wonderful, best thing I've read on the internet in quite some time! Anthropomorphising a wee sec: if a new human researcher produced this work, how would you rate it/ them

Just for intuition: the official proof informally says that as long as a set does not have too much "mass" on its neighboring edges, then it's possible to add a new vertex to it. So if I have many sets, then by an averaging argument, one of them must have less mass than average, so we can safely add a vertex to it.

@yangpliu I don't see how on average being light => there must be a set

@TFWNicholson Yes, it should be the pseudoinverse. If the graph is connected (for these problems, this can be assumed without loss of generality), the only vector in the nullspace is (1, 1, ..., 1) so it's easy to get a handle on the pseudoinverse.

@yangpliu Do we choose L so that L^{−1/2} exists or use the pseudo inverse? The graph Laplacian is typically not invertible right?

Technical thread here: x.com/yangpliu/statu…

Still, I’m genuinely impressed by how far AI-for-math has come in the past few years, and I’m excited to see what’s next. If people want, I’m happy to write up more about the problem, the solution, and how it fits in the context of prior results.

My thoughts on #1stProof Problem 6 (closely related to areas I've worked in): OpenAI’s solution is essentially correct, and the difficulty feels consistent with AI capabilities over the past several months. More detail in the thread.

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.

10/ OpenAI solution: it maintains r ≈ 1/ε different sets S_1, …, S_r, whose total size eventually is a constant fraction of n. The solution proves that you can always find one of the sets to add a new vertex to without increasing the potential: this makes sense, because on average some set should be “light’’. In the screenshots below, M_t is the sum of Laplacians of each color class, and as you can see, the solution maintains a barrier function over M_t, and does not need to maintain any property of the leverage scores of S.

A. (3) uses Theorem 2 from (1) + Lemma 1.5 from (2). B. Theorem 2 from (1) is the 3-CSP inverse theorem, which is a generalization of the U2-Gowers inverse theorem. The proof is in Sections 1-5. C. Lemma 1.5 from (2) is a quick extension of Theorem 2 to some 4-ary distributions.

Despite building on prior work, the papers are self-contained. (1) eccc.weizmann.ac.il/report/2024/19… (2) eccc.weizmann.ac.il/report/2024/19… (3) eccc.weizmann.ac.il/report/2024/19… Some notes for anyone adventurous enough to read:

In a sequence of new preprints with Amey Bhangale, Subhash Khot, and Dor Minzer, we obtain improved bounds for the density Hales-Jewett (DHJ) problem for combinatorial lines of length 3.