View source for Reduction from Maximum Inner Product Search to Stable Pair Checking

FROM: [[Maximum Inner Product Search]] TO: [[Stable Pair Checking]]

== Description == 



== Implications == 

assume: NSETH<br/>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