Timeline for Reducing search space by probability
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2014 at 14:55 | answer | added | Douglas Zare | timeline score: 2 | |
| Mar 11, 2014 at 23:53 | comment | added | usul | @DouglasZare, by brute force I meant the ~$qp$ approach of finding one answer at a time. | |
| Mar 11, 2014 at 21:26 | comment | added | David Wihl | Douglas, you're right - by exhaustively trying permutations, it should be possible in $(q+1)(p-1)$ tries. I suspect it should be a lot less, but that is only intuition. | |
| Mar 11, 2014 at 20:42 | comment | added | Douglas Zare | @usul: I'm not sure what you mean by brute force. A ball of radius $10$ takes up about $1/(4\times10^{57})$ of the possibilities. You don't need anything like $4 \times 10^{57}$ guesses. It's easy to get the exact answer in under $600$ tries by altering only one answer at a time. However, if you can get a few bits of information per try, you can do better. Asymptotically, for any fixed $q$, I think you should expect something like $c p/\log p$ guesses to find out all answers. | |
| Mar 11, 2014 at 19:53 | comment | added | usul | Perhaps some ideas from coding or sphere-packing can help give a lower bound (I suspect you cannot do much better than brute-force search...). There is some target codeword in $\mathbb{Z}_q^p$ (the string of correct answers), your goal is to find a word within Hamming distance $0.1p$ of this target, and your only tool is to make Hamming-distance queries (how far is $x$ from the target?). | |
| Mar 11, 2014 at 15:25 | review | First posts | |||
| Mar 11, 2014 at 15:43 | |||||
| Mar 11, 2014 at 15:22 | comment | added | Douglas Zare | A simpler version, with $q=2$ and a $100\%$ target, was discussed here: mathoverflow.net/questions/151390/… | |
| Mar 11, 2014 at 15:09 | history | asked | David Wihl | CC BY-SA 3.0 |