Reduction from Maximum Inner Product Search to Stable Pair Checking

FROM: Maximum Inner Product Search TO: Stable Pair Checking

Implications

assume: NSETH
then: for any $\epsilon > {0}$ there is a $c$ such that determining whether a gaiven pair is part of any or all stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires nondeterministic 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