I graduated from my PhD at MIT in 2020. I was fortunate to be advised by Virginia Vassilevska Williams.
I hope to build and refine theoretical models that crystallize concerns about complex systems. I strive to build networks of reductions that give shared explanations for the hardness of problems.
Research Interests: Fine Grained Complexity, Average-Case Complexity, Lower Bounds, Algorithms.
The Complexity of Average-Case Dynamic Subgraph Counting
Monika Henzinger, Andrea Lincoln, Barna Saha
How Compression and Approximation Affect Efficiency in String Distance Measures
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
Faster Random k-CNF Satisfiability
Andrea Lincoln, Adam Yedidia
ICALP 2020 [Invited to special issue of Theory of Computing Systems]
Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis
Michael Bender, Rezaul Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
Andrea Lincoln and Nikhil Vyas
Monochromatic triangles, intermediate matrix products, and convolutions
Andrea Lincoln, Adam Polak and, Virginia Vassilevska Williams
ITCS 2020, short presentation at HALG'20
Public-Key Cryptography: in the Fine-Grained Setting
Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity
Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik Demaine, Andrea Lincoln, Quanquan Liu, Jayson Lynch, Virginia Vassilevska Williams
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Andrea Lincoln, Virginia Vassilevska Williams, and Ryan R. Williams
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams
Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,...
Erik D Demaine, Martin L Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, Y William Yu
Journal of Information Processing 2017
Deterministic Time-Space Tradeoffs for k-SUM,
A. Lincoln, V. Vassilevska Williams, J. R. Wang and R. R. Williams,
Michael Bender, Erik Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch and Samuel Mccauley.
SPAA 2016; HALG 2017
The one-out-of-k retrieval problem and Linear Network Coding,
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln and Muriel Medard,