AF: Medium: Collaborative Research: Hardness in Polynomial Time

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

A central endeavor of theoretical computer science is to classify computational problems according to the resources (such as running time and storage space) needed to solve them.  Although the field of algorithm design has been highly successful in discovering efficient, polynomial-time algorithms for problems of practical interest, little evidence has been shown for the optimality of most algorithms.  The goal of this project is to build a useful complexity theory for the class of polynomial-time solvable problems (called P), by proving equivalences between problems and proving conditional lower bounds on specific problems, assuming the validity of certain plausible mathematical conjectures. Known lower bounds for specific problems in P are conditioned on some complexity-theoretic assumption such as the (Strong) Exponential Time Hypothesis (concerning the complexity of k-CNF-SAT), the conjecture that dense all-pairs shortest paths (APSP) requires cubic time, or that 3SUM requires quadratic time.  The goals of this project are threefold.  The first goal is to establish conditional lower bounds on problems in diverse areas (such as graph optimization, string matching, geometry, and dynamic data structures) using standard hardness conjectures. The second goal is to search for better hardness conjectures that are both plausible and versatile, and to discover relationships (implications or equivalences) between nominally unrelated conjectures.  The last goal is to investigate the plausibility of these conjectures by attempting to disprove them. The curricular portion of this project involves developing lecture material suitable for introductory algorithms and complexity courses at both the undergraduate and graduate level.