Andrea Lincoln
I am a postdoc at UC Berkeley. I am working with Barna Saha.
I graduated from my PhD at MIT in 2020. I was lucky enough to be advised by Virginia Vassilevska Williams.
I hope to build and refine theoretical models that crystallize concerns about complex systems. Correct choices of models lead to strong theoretical statements that capture properties of interest in real systems.
Research Interests:
Fine Grained Complexity, Algorithms, Lower Bounds, Average-Case Complexity
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
FOCS 2020
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
SPAA 2020
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
Andrea Lincoln and Nikhil Vyas
ITCS 2020
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
CRYPTO 2019
Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity
Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
SPAA 2018
Erik Demaine, Andrea Lincoln, Quanquan Liu, Jayson Lynch, Virginia Vassilevska Williams
ITCS 2018
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Andrea Lincoln, Virginia Vassilevska Williams, and Ryan R. Williams
SODA 2018
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann and Virginia Vassilevska Williams
ITCS 2017
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,
ICALP 2016
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,
