Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
The Planted Orthogonal Vectors Problem
David Kühnemann, Adam Polak, Alon Rosen
In the -Orthogonal Vectors (-OV) problem we are given sets, each containing binary vectors of dimension , and our goal is to pick one vector from each set…
cs.CC2025
Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
Bingbing Hu, Adam Polak
Most of the known tight lower bounds for dynamic problems are based on the Online Boolean Matrix-Vector Multiplication (OMv) Hypothesis, which is not as well studied and understood…