Timeline for Lower Bounds for the Set Disjointness Problem
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 24, 2018 at 12:29 | comment | added | András Salamon | For the revised question, note that if the elements of a set are in the range $0$ to $2^{64}-1$, then the set size can be up to $2^{64}$ elements, so for set sizes that are greater than $2^{64}/64$, sending the characteristic vector is more efficient. As Yuval Filmus points out, the setup requires using worst-case analysis. | |
| Jul 24, 2018 at 9:59 | comment | added | Cryptonaut | Sorry. I fixed my description of the disjointness problem. | |
| Jul 24, 2018 at 9:59 | history | edited | Cryptonaut | CC BY-SA 4.0 |
fixed my description of disjointness
|
| Jul 24, 2018 at 7:34 | comment | added | D.W.♦ | As Yuval Filmus points out in his answer, your definition of $\text{Dis}$ is not the set disjointness problem. Perhaps you meant $1$ if $\exists i : a_i=b_i=1$; 0 otherwise. | |
| Jul 24, 2018 at 6:36 | answer | added | Yuval Filmus | timeline score: 1 | |
| Jul 24, 2018 at 1:10 | answer | added | D.W.♦ | timeline score: 1 | |
| Jul 24, 2018 at 0:13 | history | asked | Cryptonaut | CC BY-SA 4.0 |