Andrea Lincoln

Andrea Lincoln graduated from MIT's undergraduate program with a double major in Mathematics and Electrical Engineering & Computer Science in 2014. She then received a Masters in Engineering in Electrical Engineering & Computer Science from MIT in 2015, advised by Erik Demaine. In 2016, she graduated with a Masters in Computer Science from Stanford, advised by Virginia Vassilevska Williams. Andrea Lincoln was awarded a Stanford Graduate Fellowship in 2015. She was then awarded the EECS Merrill Lynch Fellowship in 2017. She received the NSF GRFP honorable mention in 2016 and 2017. She is currently a Postdoctoral Researcher at UC Berkeley.

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 is on the topic of the application of FGC to other areas of theoretical computer science. Her thesis focuses on studying the core assumptions of FGC and three areas of applications: (1) FGC in models other than the RAM computation model, (2) fine-grained average-case complexity and algorithms, and (3) fine-grained cryptography.