DIMACS - Graduate Student Combinatorics Seminar

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


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.

See: http://www.math.rutgers.edu/~ajr224/GCS.html