3 papers
cs.CC2025
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…
cs.CC2025
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-…
cs.AI2024
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…