Abstract
In October 2021, Luca wrote on his blog, in theory, about an algorithm of Khot and Naor for approximating Max 3-XOR. He had a fresh vantage point on a classical result, as in many of his blog posts. He observed that, unlike the best-known algorithms for all Max CSPs based on rounding a natural SDP relaxation, Khot and Naor's algorithm relies on random sampling and geometric tools. Consequently, we did not have something we take for granted when designing algorithms using convex relaxations: a polynomial time verifiable certificate of an approximate bound on the optimum (via the integrality gap). He posed the question of analyzing a natural SDP (the degree four sum of squares relaxation) and, in particular, finding an efficient "certifying" algorithm as a natural and intriguing direction that could lead to progress on Max 3-XOR and other CSPs beyond the well-studied case of 2-CSPs (where it amounts to the classical Grothendieck inequality and its generalizations).
I did not know Luca personally then, but like many others in our community, I was an ardent reader of his blog. His question intrigued me and my student Tim Hsieh. We worked on the problem (both of us were in Berkeley at the time), found a solution, and used it as an excuse to talk with Luca a few times on Zoom, who, by then also had an alternate solution with Lucas Pesenti. This project led Tim and me to visit Luca in Milan over the summer of 2022 and derive various generalizations of the results that eventually appeared in my sole paper co-authored with Luca. More importantly, through many conversations and meals together, we imbibed a bit of Luca's philosophy in life and research.
In this talk, I will share the story of this work that began, as at least a few other papers, in Luca's unique viewpoints in his expositions.