• Department Home
• Undergraduate Students
• Graduate Students
• Faculty & Staff
• Research

Computer Science Colloquia

The approximability of the fundamental MAX3SAT and MAXCLIQUE optimization problems has been well-studied. Under standard computational complexity assumptions on the class NP, it is known that it is impossible to significantly improve upon the approximation ratios that are achieved by the best current algorithms. While the bound on the approximation ratios is very strong, these inapproximability results do not address the frequency of the difficult instances on which these problems cannot be approximately solved. This talk surveys my research that gives an exponential lower bound on this frequency under the plausible assumption that NP is a fractal in the sense of resource-bounded dimension.

This talk is based on the papers "MAX3SAT Is Exponentially Hard to Approximate If NP Has Positive Dimension" and "The Frequency of Difficult Instances for MAXCLIQUE Approximation Algorithms" available at my web page.