Exact 2-CSP Optimization Using Matrix Multiplication

  • Ryan Williams | Carnegie Mellon University and Microsoft Research

We investigate the complexity of exactly solving NP-hard optimization problems involving at most two variables per constraint, such as MAX-CUT, MAX-2-SAT, and MIN-BISECTION. For years it was not known if one could solve such problems in time significantly less than 2n (trying all possible assignments). We’ll present an algorithm that reduces any 2-CSP optimization problem to a (very, very large) matrix multiplication problem. Let nomega be the runtime of some matrix multiplication algorithm M on n by n matrices (note omega < 2.4 for some M). Using that M, the algorithm for 2-CSP optimization will run in 2omega n/3 time, modulo polynomial factors.

Speaker Details

Ryan is a PhD student in computer science at Carnegie Mellon University. Earlier, he received an M. Eng. and bachelor’s degree from Cornell. He is mainly interested in CS Theory, from both the algorithmic and complexity-theoretic sides. This summer, he is an intern in the theory group in Microsoft Research.

    • Portrait of Jeff Running

      Jeff Running

Watch Next