Showing cs.CCShow all
3 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.CC2024
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…
cs.CC2023
Deterministic 3SUM-Hardness
Nick Fischer, Piotr Kaliciak, Adam Polak
As one of the three main pillars of fine-grained complexity theory, the 3SUM problem explains the hardness of many diverse polynomial-time problems via fine-grained reductions. Man…