4 papers
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
Cheng-Hao Fu, Andrea Lincoln, Rene Reyes
In this paper we present tight lower-bounds and new upper-bounds for hypergraph and database problems. We give tight lower-bounds for finding minimum hypercycles. We give tight low…
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha +1
This work establishes conditional lower bounds for average-case {\em parity}-counting versions of the problems -XOR, -SUM, and -OV. The main contribution is a set of self-…
Towards a Law of Iterated Expectations for Heuristic Estimators
Paul Christiano, Jacob Hilton, Andrea Lincoln +2
Christiano et al. (2022) define a *heuristic estimator* to be a hypothetical algorithm that estimates the values of mathematical expressions from arguments. In brief, a heuristic e…
How Compression and Approximation Affect Efficiency in String Distance Measures
Arun Ganesh, Tomasz Kociumaka, Andrea Lincoln +1
Real-world data often comes in compressed form. Analyzing compressed data directly (without decompressing it) can save space and time by orders of magnitude. In this work, we focus…