*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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 NP-hard problems: 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.
