Tensors and Random Constraint Satisfaction Problems

Ying Xiao (mentor: Santosh Vempala, CS) - We are interested in applying tensors and spectral techniques to the study of random constraint satisfaction problems. In particular, we hope to provide "refutation proofs" (certificates of non-satisfiability) for most instances of random 3-CNF problems. Our approach is through tensor eigenvalues, and is motivated by a tensor formulation of the refutation problem. Additionally, we are interested in efficiently computing these tensor eigenvalues -- although this is NP-hard in general, nothing is known about the hardness of approximation.