Timeline for Finding perfect matchings with as few database queries as possible
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 21, 2016 at 12:34 | vote | accept | Jake B | ||
| Jun 21, 2016 at 13:11 | |||||
| Jun 21, 2016 at 11:40 | comment | added | adrianN | In this paper the authors examine a similar problem with a slightly different oracle and get $\Theta(n \log \log n)$ in the randomized setting. I believe that one can also solve this problem quicker than $\Theta(n\log n)$. | |
| Jun 21, 2016 at 11:17 | comment | added | Yuval Filmus | There is an easy $\Omega(n)$ lower bound since you're recovering $\Omega(n\log n)$ bits of information, and you get $O(\log n)$ bits from each query. Your queries only give you one bit of information, which is why you need $\Omega(n\log n)$ of them. | |
| Jun 21, 2016 at 9:10 | comment | added | adrianN | Does anybody know a lower bound? I have a feeling that you might shave of some loglogs by asking about more men in parallel. | |
| Jun 21, 2016 at 9:09 | history | answered | adrianN | CC BY-SA 3.0 |