Timeline for Finding $k$ active elements by evaluating the "any-operator" of subsets of variables
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 17, 2023 at 12:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 18, 2022 at 11:22 | answer | added | pcpthm | timeline score: 2 | |
| Dec 6, 2022 at 11:12 | history | edited | Asaf Karagila♦ |
edited tags
|
|
| Dec 6, 2022 at 11:00 | comment | added | Emil Jeřábek | Also, I believe that if you count better, the “splitting in halves, discarding empty subsets” algorithm actually uses only $O(m\log(n/m))$ operations rather than $O(m\log n)$. So it is optimal up to a multiplicative constant (at least for $m\le n/2$). | |
| Dec 6, 2022 at 10:23 | comment | added | Emil Jeřábek | For fixed $m$, there are $\binom nm$ possible outcomes, whereas each application of your operation only gives 1 bit of information. Thus, you need at least $\log\binom nm$ operations, which is $\Omega(m\log n)$ if $m$ is much smaller than $n$ (say, $m\le n^\gamma$ for a constant $\gamma<1$). For larger $m$, this bound is about $\Omega(m\log(n/m))$. | |
| Dec 6, 2022 at 10:16 | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
fix TeX abuse
|
| Dec 6, 2022 at 9:08 | comment | added | Erik Hellsten | @JoelDavidHamkins Thanks, for the comments. I have edited for clarity. | |
| Dec 6, 2022 at 9:07 | history | edited | Erik Hellsten | CC BY-SA 4.0 |
added 161 characters in body
|
| Dec 5, 2022 at 16:12 | comment | added | Joel David Hamkins | But also, I am confused as to the basic set up. We are "allowed a single operation", but do you mean we can use this operation repeatedly, for different Q, or are we allowed just one use of it? Do we do the choosing of Q, or does the "operation" choose, as you seem to say? Why do you speak of a distribution for a fixed |Q|, rather than on the set of all such Q? When you refer to solving "this", what is it that is being solved exactly? Basically, I am confused about many things here. I think my understanding would benefit from an edit to the question to explain everything more carefully. | |
| Dec 5, 2022 at 15:49 | comment | added | Joel David Hamkins | Could you clarify what is the goal? Do we want merely to find an active element? Or all of them? | |
| S Dec 5, 2022 at 15:12 | review | First questions | |||
| Dec 6, 2022 at 0:22 | |||||
| S Dec 5, 2022 at 15:12 | history | asked | Erik Hellsten | CC BY-SA 4.0 |