{"id":"arxiv/2607.00205","url":"https://arxiv.org/abs/2607.00205","tags":["cs.IT","cs.GT","math.CO","math.PR"],"score":0,"title":"Guesswork Under Linear Constraints: Exact Exponent for Coset Decoding","domain":"cs.IT","source":"arxiv","authors":["Hassan Tavakoli"],"reviews":0,"subject":"cs.IT","summary":"We establish the exact exponential growth rate of the $ρ$-th moment of the constrained guesswork $G_{\\mathrm{coset}}$ -- the rank of the true noise vector within its syndrome coset of a random binary linear code under i.i.d.\\ Bernoulli$(p)$ noise: \\( \\lim_{n\\to\\infty} \\frac{1}{n}\\log_2\\Eb\\!\\left[G_{\\mathrm{coset}}^ρ\\right] = ρ\\,h_{\\frac{1}{1+ρ}}(p)\\;+\\;ρ(R-1), \\, ρ>0, \\) where $h_α(p)$ is the binary Rényi entropy and $R=k/n$ is the code rate. The exponent shifts down by exactly $ρ(1-R)$ relative to the unconstrained Arıkan--Merhav exponent, with each of the $n(1-R)$ parity checks…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-30","reactions":{}}