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.
Fine Grained Complexity, Algorithms, Lower Bounds, Average-Case Complexity
- 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
- Public-Key Cryptography: in the Fine-Grained Setting
- Faster Random k-CNF Satisfiability
- Andrea Lincoln, Adam Yedidia
- In Submission
- Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity
- Fine-grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
- Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
- Conditional Hardness for Sensitivity Problems
- Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,...
- Deterministic Time-Space Tradeoffs for k-SUM,
- Cache-Adaptive Analysis,
- The one-out-of-k retrieval problem and Linear Network Coding,