Tel-Aviv University - Computer Science Colloquium
Sunday, November 1, 14:15-15:15
at 14:00 Our understanding of the class NP has been considerably deepened in recent year, through new and stronger characterizations. These characterizations have been extensively applied to show numerous hardness results for approximation problems. The talk will survey these stronger characterizations of NP and their application to hardness results.