Skip to main content
6 events
when toggle format what by license comment
Dec 12, 2013 at 4:08 review Suggested edits
Dec 12, 2013 at 7:41
Dec 1, 2011 at 18:19 comment added Alan Haynes @Marcin I think your question has an answer but it is hard to determine exactly what you are asking. For example why can't you recover $q$ if $r$ does not grow with $n$? No matter what $r$ is, for any $q$, if the RHS is less that $1/2q$ then there is always a choice of $p_i$'s that works. That is also why I asked if you really to say mean $1/poly (n)$ on the RHS. If $q$ grows along any sequence which is exponential in $n$ but the bound on the right hand side is only $1/poly (n)$ then for every large enough $q$ there will be many choices for $p_i$'s.
Nov 30, 2011 at 23:06 comment added Marcin Kotowski @AH: I do mean poly(n) - poly(q) would be exponential in n. r must grow with n, otherwise, you can't even hope to recover q.
Nov 23, 2011 at 22:20 comment added Alan Haynes @Marcin There are two things that are confusing me. First, do you really mean to allow $r$ to grow with $n$? It seems like the dependence of the problem on $r$ is artificial since you can just multiply it through the whole equation. Secondly, do you really mean $poly(n)$ on the RHS of your inequality, or should it be $poly(q)$?
Oct 15, 2011 at 23:13 history edited Marcin Kotowski CC BY-SA 3.0
added 115 characters in body
Oct 15, 2011 at 23:04 history asked Marcin Kotowski CC BY-SA 3.0