Timeline for Solving multiple instances of 3SUM generated from the same set
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Feb 1, 2012 at 2:26 | history | tweeted | twitter.com/#!/StackCSTheory/status/164535000904110080 | ||
| Feb 1, 2012 at 1:53 | answer | added | David Eppstein | timeline score: 9 | |
| Feb 1, 2012 at 0:48 | comment | added | Tsuyoshi Ito | (1) I think that now I understand the question (but not the answer…). Thanks for editing the question. (2) I do not think that the main difference between your previous question and the current question is whether you use 3SUM or 3SUM′. The important differences are the size of set Y (previously called set D) and how this set is chosen (“randomly” is very important). | |
| Feb 1, 2012 at 0:26 | comment | added | Heinz Fiedler | Someone build Y for me, that was wrong in the question, my bad. | |
| Feb 1, 2012 at 0:24 | history | edited | Heinz Fiedler | CC BY-SA 3.0 |
added 22 characters in body
|
| Feb 1, 2012 at 0:07 | comment | added | Tsuyoshi Ito | I am confused. I thought that Y is an input to your algorithm, but I realized that you are talking about how you choose Y. If you choose Y, why don’t you just choose something trivial such as the sum of the three smallest elements in S? I think that you have some assumption about how Y must be chosen in your mind, which is not stated in the question. | |
| Jan 31, 2012 at 23:51 | history | edited | Heinz Fiedler | CC BY-SA 3.0 |
deleted 109 characters in body
|
| Jan 31, 2012 at 23:48 | comment | added | Heinz Fiedler | Done. For the birthday problem, I've edited a little more to make everything clear I hope (and right). It's maybe clearer in the balls and urns model. If you have $n$ balls in an urn, and you pick balls in this urn, you'll have to pick roughly $\sqrt{n}$ balls (with replacement) to pick the same ball twice. So in my case, if I pick $n^1.5$ triplets from the $n^3$ possible triplets (=balls) to build $Y$, I'll pick the same triplet twice with good (i.e. constant) probability with $O(n^{1.5}$ tries. | |
| Jan 31, 2012 at 23:10 | history | edited | Heinz Fiedler | CC BY-SA 3.0 |
added 191 characters in body
|
| Jan 31, 2012 at 23:05 | comment | added | Tsuyoshi Ito | Please provide a link to your previous question and state the relation between the current question and the previous one. I think that this is the special case of your previous question with the additional assumption |D|=n, and I fail to see how the birthday paradox can be used to obtain an O(n^{3/2})-time randomized algorithm, but I may be missing something. | |
| Jan 31, 2012 at 22:25 | history | asked | Heinz Fiedler | CC BY-SA 3.0 |