Andrea Lincoln

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Worst-case and average-case hardness of hypercycle and database problems	2026-09-29	Paper
Average-case hardness of parity problems: orthogonal vectors, k-SUM and more	2026-07-03	Paper
Faster random k-CNF satisfiability	2026-03-18	Paper
New techniques for proving fine-grained average-case hardness	2025-08-12	Paper
The complexity of average-case dynamic subgraph counting	2024-07-19	Paper
How compression and approximation affect efficiency in string distance measures	2024-07-19	Paper
Delegation for search problems	2024-06-24	Paper
scientific article; zbMATH DE number 7788634 (Why is no real title available?)	2024-01-15	Paper
Quasipolynomiality of the Smallest Missing Induced Subgraph Journal of Graph Algorithms and Applications	2023-09-20	Paper
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs.	2023-02-03	Paper
Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy (available as arXiv preprint)	2021-06-15	Paper
Public-key cryptography in the fine-grained setting	2020-03-09	Paper
Conditional hardness for sensitivity problems (available as arXiv preprint)	2018-05-03	Paper
Tight hardness for shortest cycles and paths in sparse graphs (available as arXiv preprint)	2018-03-15	Paper
Tight hardness for shortest cycles and paths in sparse graphs	2018-03-15	Paper
Deterministic time-space trade-offs for k-SUM (available as arXiv preprint)	2017-12-19	Paper
The one-out-of-\(k\) retrieval problem and linear network coding Advances in Mathematics of Communications	2016-03-11	Paper
The one-out-of-\(k\) retrieval problem and linear network coding Coding Theory and Applications	2016-01-07	Paper

Research outcomes over time

This page was built for person: Andrea Lincoln