Title: Hardness amplification for errorless heuristics
Speaker: Andrej Bogdanov, DIMACS
Date: Wednesday, January 24, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We say a problem is tractable on average if it can be solved on a "good" fraction of instances by an efficient algorithm. To make this definition precise, we need to make two choices: First, what is a "good" fraction of instances - is it 1%, 51%, 99%, or something else? And second, what should the algorithm do on the instances where it fails to solve the problem?
For heuristic algorithms for NP - these are allowed to behave arbitrarily on instances where they fail to solve the problem - it is known that the definition is robust with respect to the fraction of instances. Namely, if all problems in NP can be solved on a 51% fraction of instances by heuristic algorithms, then all problems in NP can be solved on a 99% fraction of instances by heuristic algorithms.
We consider the analogous question for errorless heuristics - these algorithms must output "I don't know" on instances where they fail to solve the problem - and show that if all problems in NP can be solved on even a 1% fraction of instances by errorless heuristics, then all problems in NP can be solved on 99% instances by errorless heuristics. (This is based on joint work with Muli Safra)