Showing 2025Show all
2 papers · 1 filter
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-…