Timeline for Combinatorial computational problem about 0-1 vectors and sampling algorithms
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 3, 2018 at 14:34 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
deleted 680 characters in body
|
| S Mar 3, 2018 at 11:36 | history | suggested | Rodrigo de Azevedo | CC BY-SA 3.0 |
Minor edits to improve readability
|
| Mar 3, 2018 at 10:27 | review | Suggested edits | |||
| S Mar 3, 2018 at 11:36 | |||||
| S Mar 3, 2018 at 9:41 | history | suggested | Matemáticos Chibchas | CC BY-SA 3.0 |
Add required package for \boldsymbol command
|
| Mar 3, 2018 at 4:19 | review | Suggested edits | |||
| S Mar 3, 2018 at 9:41 | |||||
| Mar 3, 2018 at 0:45 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 3 characters in body
|
| Mar 2, 2018 at 20:00 | answer | added | Watson Ladd | timeline score: 1 | |
| Mar 2, 2018 at 18:56 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 7 characters in body
|
| Mar 2, 2018 at 17:33 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 11 characters in body
|
| Mar 2, 2018 at 17:27 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 11 characters in body
|
| Mar 2, 2018 at 17:18 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 11 characters in body
|
| Mar 2, 2018 at 17:14 | comment | added | Penelope Benenati | Max, thank you for your answer. What you say it is clear, but in my problem I took for granted that you have access only to $\sqrt{n}$ elements of the copy of $\boldsymbol{r}$ you receive in step 1. And, of course, as you know even if the $n$-dimensional matrix row vectors are sorted in $M$, the rows of a submatrix obtained by sampling u.a.r. $\sqrt{n}$ from $M$ are not sorted in general. Hence, it is no possible in general to apply dichotomic search methods. I am now rephrasing the problem in order to avoid misunderstanding. Thank you again. | |
| Mar 2, 2018 at 17:00 | comment | added | Penelope Benenati | Brendan, thank you. You are right about defining the pre-processing time complexity bound. I would just say that a polynomial (in n and m) time and space complexity for the preprocessing is OK. About the table, I don't think it can work, because the number of columns that can be sampled from a subset of $n^{1/4}$ columns is exponential in $n$ (it is still exponential $n$ if we consider the expected number of columns sampled by any fixed subset of $n^{1/4}$ columns). I instead believe it would be interesting to analyse the expected time required by verifying u.a.r. each row until finding $r'$. | |
| Mar 2, 2018 at 9:47 | comment | added | Max Alekseyev | Having matrix rows sorted (in lexicographic order) allows to perform exact search of $r$ in $M$ in time about $\log_2(m)n$, which may be better than $m\sqrt{n}$ (depending on relationship between $m$ and $n$). | |
| Mar 2, 2018 at 2:25 | comment | added | Brendan McKay | An answer that matches the letter, but presumably not the spirit, of your question is to do so much preprocessing that all possible questions have been answered already and stored in a convenient table. Or you can go part way by, say, making a table that allows any $n^{1/4}$ columns of $M$ to be looked up immediately. To make the question more useful, I think you need to put some limit on either the time used for preprocessing or the space used to hold the results of preprocessing. | |
| Mar 1, 2018 at 21:17 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
edited body
|
| Mar 1, 2018 at 20:11 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
added 4 characters in body; edited tags
|
| Mar 1, 2018 at 17:57 | history | edited | Penelope Benenati | CC BY-SA 3.0 |
edited title
|
| Mar 1, 2018 at 17:50 | history | edited | Penelope Benenati |
edited tags
|
|
| Mar 1, 2018 at 16:39 | history | asked | Penelope Benenati | CC BY-SA 3.0 |