{"id":"arxiv/2607.24073","url":"https://arxiv.org/abs/2607.24073","tags":["cs.DS","cs.CC","math.PR"],"score":0,"title":"Recovering Assignments with One-Sided Noise","domain":"cs.DS","source":"arxiv","authors":["Cassandra Marcussen","Elchanan Mossel","Colin Sandon"],"reviews":0,"subject":"cs.DS","summary":"We study the query complexity of recovering a planted assignment from a random constraint-satisfaction instance with one-sided noise. We consider the following 1-CNF recovery problem: an unknown binary string with $n/2$ ones and $n/2$ zeros is queried at individual variables. A query to a $1$-variable returns \"$1$\" with probability $p$ and \"$0$\" otherwise, while a $0$-variable always returns \"$0$\" (each query is a fresh noisy draw). The goal is to recover the binary string with probability at least $1 - δ$. While the naive counting argument may suggest a query complexity of $\\log_2…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-27","reactions":{}}