Reduction from Maximum Inner Product Search to Boolean d-Attribute Stable Matching

FROM: Maximum Inner Product Search TO: Boolean d-Attribute Stable Matching

Implications

assume: OVH
then: for an $\epsilon > {0}$ there is a $c$ such that finding 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