Andrea Lincoln

40 papers A* 9A 4B 4C 1Journal 20Unranked 2
YearRankTypeTitle / Venue / Authors
2025 A* conf
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More.
SODA
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams
2025 J jnl
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More.
CoRR
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, Virginia Vassilevska Williams
2025 A* conf
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems.
ICALP
Cheng-Hao Fu, Andrea Lincoln, Rene Reyes
2025 J jnl
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems.
CoRR
Cheng-Hao Fu, Andrea Lincoln, Rene Reyes
2024 J jnl
Towards a Law of Iterated Expectations for Heuristic Estimators.
CoRR
Paul F. Christiano, Jacob Hilton, Andrea Lincoln, Eric Neyman, Mark Xu
2023 J jnl
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.
CoRR
Monika Henzinger, Andrea Lincoln, Barna Saha, Martin P. Seybold, Christopher Ye
2023 J jnl
Quasipolynomiality of the Smallest Missing Induced Subgraph.
CoRR
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
2023 J jnl
Quasipolynomiality of the Smallest Missing Induced Subgraph.
J. Graph Algorithms Appl.
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
2022 A* conf
Delegation for Search Problems.
ICALP
Justin Holmgren, Andrea Lincoln, Ron D. Rothblum
2022 A* conf
How Compression and Approximation Affect Efficiency in String Distance Measures.
SODA
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
2022 A* conf
The Complexity of Average-Case Dynamic Subgraph Counting.
SODA
Monika Henzinger, Andrea Lincoln, Barna Saha
2021 B conf
Dynamic Boolean Formula Evaluation.
ISAAC
Rathish Das, Andrea Lincoln, Jayson Lynch, J. Ian Munro
2021 J jnl
How Compression and Approximation Affect Efficiency in String Distance Measures.
CoRR
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln, Barna Saha
2021 J jnl
The Complexity of Average-Case Dynamic Subgraph Counting.
Electron. Colloquium Comput. Complex.
Monika Henzinger, Andrea Lincoln, Barna Saha
2020 A conf
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs.
ITCS
Andrea Lincoln, Nikhil Vyas
2020 B conf
Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis.
SPAA
Michael A. Bender, Rezaul Alam Chowdhury, Rathish Das, Rob Johnson, William Kuszmaul, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Helen Xu
2020 A* conf
Faster Random k-CNF Satisfiability.
ICALP
Andrea Lincoln, Adam Yedidia
2020 A conf
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions.
ITCS
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
2020 J jnl
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions.
CoRR
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
2020 A* conf
New Techniques for Proving Fine-Grained Average-Case Hardness.
FOCS
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
2020 J jnl
New Techniques for Proving Fine-Grained Average-Case Hardness.
CoRR
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
2019 J jnl
Faster Random k-CNF Satisfiability.
CoRR
Andrea Lincoln, Adam Yedidia
2019 — conf
Public-Key Cryptography in the Fine-Grained Setting.
CRYPTO (3)
Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
2019 J jnl
Public-Key Cryptography in the Fine-Grained Setting.
IACR Cryptol. ePrint Arch.
Rio LaVigne, Andrea Lincoln, Virginia Vassilevska Williams
2018 B conf
Cache-Adaptive Exploration: Experimental Results and Scan-Hiding for Adaptivity.
SPAA
Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Helen Xu
2018 A conf
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy.
ITCS
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams
2018 A* conf
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.
SODA
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
2017 A conf
Conditional Hardness for Sensitivity Problems.
ITCS
Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams
2017 J jnl
Conditional Hardness for Sensitivity Problems.
CoRR
Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams
2017 J jnl
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy.
CoRR
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, Virginia Vassilevska Williams
2017 J jnl
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs.
CoRR
Andrea Lincoln, Virginia Vassilevska Williams, R. Ryan Williams
2017 J jnl
Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes, ...
J. Inf. Process.
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Adam Hesterberg, Andrea Lincoln, Jayson Lynch, Yun William Yu
2016 B conf
Cache-Adaptive Analysis.
SPAA
Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, Samuel McCauley
2016 A* conf
Deterministic Time-Space Trade-Offs for k-SUM.
ICALP
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
2016 J jnl
Deterministic Time-Space Tradeoffs for k-SUM.
CoRR
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
2016 J jnl
The one-out-of-k retrieval problem and linear network coding.
Adv. Math. Commun.
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard
2015 J jnl
Improved Connectivity Condition for Byzantine Fault Tolerance.
CoRR
Adam Hesterberg, Andrea Lincoln, Jayson Lynch
2014 — conf
The One-Out-of-k Retrieval Problem and Linear Network Coding.
ICMCTA
Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard
2011 J jnl
Fault Tolerance of Node Failure in a Stochastic Localization Algorithm for Wireless Sensor Networks.
Int. J. Comput. Their Appl.
Andrea Lincoln, Ying Wei Lin
2010 C conf
Fault Tolerance of Node Failures in a Stochastic Localization Algorithm for Wireless Sensor Networks.
CAINE
Andrea Lincoln, Ying Wei Lin