Reduction from Maximum Inner Product Search to Stable Matching Verification

FROM: Maximum Inner Product Search TO: Stable Matching Verification

Implications

assume: OVH
then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}).

Year

2016

Reference

Moeller, Daniel, Ramamohan Paturi, and Stefan Schneider. "Subquadratic algorithms for succinct stable matching." International Computer Science Symposium in Russia. Springer, Cham, 2016.

https://arxiv.org/pdf/1510.06452.pdf