Timeline for Bounds for duplicate finding with limited independence
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2012 at 0:39 | comment | added | Douglas Zare | For $k=3$, it looks like $(1/3 + o(1))n$ is the limit of this technique, with about $n/4$ pairs and $n/6$ triplets. | |
| Jul 28, 2012 at 13:24 | history | edited | Douglas Zare | CC BY-SA 3.0 |
Solved 3-independent case.
|
| Jul 19, 2012 at 17:30 | vote | accept | Raphael | ||
| Jul 15, 2012 at 8:36 | comment | added | Douglas Zare | Earlier I had overlooked that you only need the sum from about $\sqrt{2n}$ to $n$, which is why I didn't obtain the $O(\sqrt{n})$ result from this technique. | |
| Jul 14, 2012 at 10:21 | history | answered | Douglas Zare | CC BY-SA 3.0 |