Previous Conferences & Workshops

Sep
30
2008

Computer Science/Discrete Mathematics Seminar II

A Survey of Time Lower Bounds by Algorithmic Arguments
Ryan Williams
10:30am|S-101

One natural strategy for proving a time lower bound for a problem is proof-by-contradiction: assume that there is a great algorithm for the problem, and apply this algorithm as a subroutine to solve other problems until the algorithms get so great...