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

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

== Description == 



== Implications == 

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