Computer Sciences Seminar
Thursday, March 7
11:30 AM, NAC 8/206

Evasive Graph Properties and other Hardness Results

Amit Chakrabarti
Princeton University

Abstract
Computational complexity theory seeks to understand the capabilities as well as the limitations of algorithms. Hardness results, also called lower bound results, are aimed at the latter goal. Given our very limited success at proving hardness results in general computational models (such as the Turing machine), research in this area has tended to focus on more specialized models, tailored to the problem at hand. A long-standing family of open problems in this area concerns algorithms that decide whether or not an input graph satisfies a particular property. The most celebrated of these open problems is Karp's "evasiveness conjecture", which states that for a monotone graph property any deterministic algorithm must inspect every single edge of the graph, in the worst case. Examples of monotone properties are connectedness, k-colorability, Hamiltonicity, and just about any other "natural" graph property. We prove that Karp's conjecture is true for the important class of minor-closed graph properties. We also significantly improve earlier results for subgraph containment properties. I shall present these results, along with a brief survey of my other work on computational hardness.

Bio
Amit Chakrabarti received a B.Tech. in Computer Science from the Indian Institute of Technology, Bombay, along with the President of India Gold Medal. He subsequently received an M.A. in Computer Science and expects to receive a Ph.D. in Computer Science from Princeton University in summer 2002. His research interests are in Complexity Theory, where he investigates the limitations of computers at solving fundamental algorithmic problems, and in Approximation Algorithms, where he is interested in finding close-to-optimal solutions for NP-hard optimization problems.