Andrea Lincoln
I am a PhD student at MIT. I am lucky to have Virginia Vassilevska Williams as my advisor.
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
- Public-Key Cryptography: in the Fine-Grained Setting
- Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
- Accepted to CRYPTO 2019
- Faster Random k-CNF Satisfiability
- Andrea Lincoln, Adam Yedidia
- In Submission
- Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity
- Andrea Lincoln, Quanquan Liu, Jayson Lynch, Helen Xu
- SPAA 2018
- 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
- 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
- Cache-Adaptive Analysis,
- 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,
- Advances in Mathematics of Communications AMC; ICMCTA 2014
