Title: Reductions for Polynomial Lower Bounds
Speaker: Andrew Lohr, Rutgers University
Date: Wednesday, November 2, 2016 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
3SUM is a problem that is conjectured to need at least roughly quadradic time to solve. This can be used to get conjectured polynomial lower bounds on a large number of other problems. We'll be looking at a few of them.