2 papers
cs.CC2026
Strongly Refuting Random CSP without Literals
Siu On Chan, Tommaso d'Orsi, Jeff Xu
Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each co…
cs.CC2024
Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs
Jeff Xu
In this work, we give novel spectral norm bounds for graph matrix on inputs being random regular graphs. Graph matrix is a family of random matrices with entries given by polynomia…