{"ID":5552842,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-03T21:22:07.242086766Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.00205","arxiv_id":"2607.00205","title":"Guesswork Under Linear Constraints: Exact Exponent for Coset Decoding","abstract":"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), \\, ρ\u003e0, \\) 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 contributing equally. Finite-length simulations confirm convergence from below. We further establish: (i)~a transfer theorem expressing the partition-function exponent in terms of an arbitrary weight-enumerator growth rate $g(δ)$; (ii)~the exact exponent for $L_n$-list (``$k$-th'') constrained guesswork; and (iii)~a sharp second-order refinement of order $ρ\\log_2 n$. Beyond the binary i.i.d.\\ setting, we prove a universality theorem: for any code ensemble $\\mathcal{E}$ whose weight enumerator concentrates at rate $g_{\\mathcal{E}}(δ)$, the guesswork exponent equals $(1+ρ)ψ_{1/(1+ρ)}(g_{\\mathcal{E}})-ρ\\,ψ_1(g_{\\mathcal{E}})$, where $ψ_α(g)=\\sup_δ[g(δ)+α\\ell(δ)]$. As concrete applications, we instantiate this theorem for the $q$-ary extension, $Λ_q(ρ)=ρ\\,h^{(q)}_{1/(1+ρ)}(P)+ρ(R-1)\\log_2 q$, and for Gallager's regular LDPC ensemble, obtaining a closed-form guesswork exponent via an exact finite-length identity for the ensemble-average weight enumerator.","short_abstract":"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}}^ρ\\ri...","url_abs":"https://arxiv.org/abs/2607.00205","url_pdf":"https://arxiv.org/pdf/2607.00205v1","authors":"[\"Hassan Tavakoli\"]","published":"2026-06-30T21:35:56Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.GT\",\"math.CO\",\"math.PR\"]","methods":"[]","has_code":false}