Andrea Lincoln

Andrea Lincoln

Andrea Lincoln

Massachusetts Institute of Technology

PhD Student

Andrea Lincoln is a 5th year student in MIT’s Ph.D. program advised by Prof. Virginia Vassilevska Williams. Previously, Andrea received a double major Bachelor’s degree in Mathematics and EECS from MIT in 2014 and a Masters of Engineering degree in EECS again from MIT in 2015, advised by Prof. Erik Demaine. In 2016 she graduated with a Masters in Computer Science from Stanford advised by Prof. Virginia Vassilevska Williams and followed her advisor to MIT to continue her Ph.D. studies. Andrea’s thesis work is in the theory of computation, with a particular focus on fine-grained complexity and its applications.
Andrea has received several awards including the Stanford Graduate Fellowship in 2015, the MIT EECS Merrill Lynch Fellowship in 2017, and the NSF GRFP honorable mention in 2016 and 2017. Andrea has given invited talks at the STOC TCS Women Workshop-Rising Star Talks 2019, China Theory Week 2018, and the Complexity Theory workshop by the Clay Math Institute at Oxford 2018.

Research Abstract:

Many fundamental algorithmic problems are inefficient to solve, given modern input sizes and computational hardware. For many of the problems, the best known runtimes have not significantly improved in the last 60 years. Fine-grained complexity (FGC) focuses on the exact constant in the exponent for these problems, with a primary focus on polynomial-time problems. FGC research focuses on finding conditional lower bounds, i.e. lower bounds that are guaranteed to hold if certain specified conjectures are true. There are three conjectures which have been most studied in fine-grained complexity: 3-SUM, All Pairs Shortest Paths, and Satisfiability.
Andrea Lincoln’s PhD thesis will be on the topic of the application of FGC to other areas of theoretical computer science. Her thesis will focus on studying the core assumptions of FGC and three areas of applications: (1) FGC in models other than the RAM model, (2) fine-grained average-case complexity, and (3) fine-grained cryptography.