*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
The theory of NP-hardness has been very successful in identifying problems that are unlikely to have general purpose polynomial time algorithms. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make them run for days, weeks or more. For example, quadratic time algorithms, although practical on moderately sized inputs, can become inefficient on problems that involve gigabytes or more of data. Although for many problems no subquadratic time algorithms are known, evidence of quadratic-time hardness has remained elusive.
In this talk, I will give an overview of recent research that aims to remedy this situation. In particular, I will describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., support vector machines or batch gradient computation in neural networks). All of them have polynomial time algorithms, but despite an extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.
