13 citations · 17 across the 5 of their papers we have counts for
10 papers
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems
Monika Henzinger, Barna Saha, Martin P. Seybold +1
{\em Algorithms with predictions} incorporate machine learning predictions into algorithm design. A plethora of recent works incorporated predictions to improve on worst-case optim…
Quasipolynomiality of the Smallest Missing Induced Subgraph
David Eppstein, Andrea Lincoln, Virginia Vassilevska Williams
We study the problem of finding the smallest graph that does not occur as an induced subgraph of a given graph. This missing induced subgraph has at most logarithmic size and can b…
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
The most studied linear algebraic operation, matrix multiplication, has surprisingly fast time algorithms for . On the other hand, the matrix product w…
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). This paper defines new versions of OV, $k…
Faster Random -CNF Satisfiability
Andrea Lincoln, Adam Yedidia
We describe an algorithm to solve the problem of Boolean CNF-Satisfiability when the input formula is chosen randomly. We build upon the algorithms of Sch{ö}ning 1999 and Dantsin e…
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Andrea Lincoln, Virginia Vassilevska Williams, Ryan Williams
Fine-grained reductions have established equivalences between many core problems with -time algorithms on -node weighted graphs, such as Shortest Cycle, All-Pair…
Conditional Hardness for Sensitivity Problems
Monika Henzinger, Andrea Lincoln, Stefan Neumann +1
In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allow…
Deterministic Time-Space Tradeoffs for k-SUM
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang +1
Given a set of numbers, the -SUM problem asks for a subset of numbers that sums to zero. When the numbers are integers, the time and space complexity of -SUM is generally…
Improved Connectivity Condition for Byzantine Fault Tolerance
Adam Hesterberg, Andrea Lincoln, Jayson Lynch
Given a network in which some pairs of nodes can communicate freely, and some subsets of the nodes could be faulty and colluding to disrupt communication, when can messages reliabl…