Speaker: Yi Wu
Carnegie Mellon University
Title: Approximability of NP hard problems in Learning and CSP
Abstract: An α-approximation algorithm is an algorithm guaranteed to output a
solution that is within an α ratio of the optimal solution. We are
interested in the following question:
Given an NP-hard optimization problem, what is the best approximation
guarantee that any polynomial time algorithm could achieve?
We mostly focus on studying the approximability of two classes of
Constraint Satisfaction Problems (CSPs) and Computational Learning Problems.
Our research in the field of CSPs is to show that certain Semidefinite
Programming (SDP) algorithms are the optimal polynomial time approximation
algorithm; our work in the learning area is to prove that tasks are inherently
hard; i.e., there is no better-than-trivial algorithm for the problems.
We will describe results on the approximability of several problems
from these two classes such as Max-Cut, Satisfiable 3-CSPs and
agnostic learning of monomials and low degree PTFs.