Speaker: Ryan Williams

Time: Wednesday 12-1pm

Place: NSH 1507

Title: 	Using Linear Algebra for Faster Solution of NP-hard Problems

Abstract: 	

We present a connection between two fundamental problems in computer science:  the well-known
problem of Matrix Multiplication, and the very general problem of 2-CSP (2-Constraint
Satisfaction Problem) Optimization which encodes many important graph optimization problems.
While Matrix Multiplication is well-known to be a polynomial time problem, 2-CSP Optimization
is NP-Hard. Despite the stark computational differences between the two problems, we show that
better Matrix Multiplication algorithms yield better 2-CSP Optimization algorithms, focusing on
the case of MIN-BISECTION: given a graph on 2k nodes, partition the nodes into two parts of k
nodes such that the number of edges straddling the two parts is minimized. Namely, we show that
if multiplication of n by n matrices is possible in (n^3)/f(n) time for some function f, then a
MIN-BISECTION of a graph with n nodes can be found in roughly (2^n)/f(2^{n/3}) time. In
particular, the n^{2.376} matrix multiplication algorithm of Coppersmith and Winograd implies
that MIN-BISECTION can be solved in 2^{.792n} time. Prior to our work, no improvement over
brute-force search (2^n time) was known for solving 2-CSP Optimization exactly.