Exact 2-CSP Optimization Using Matrix Multiplication

Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=RMIVPBIA7ko



Duration: 48:01
692 views
3


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 2^n (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 n^{omega} 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 2^{omega n/3} time, modulo polynomial factors.







Tags:
microsoft research