Recovering Assignments with One-Sided Noise
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.24073
curl -X POST /api/v1/records/arxiv/2607.24073/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.24073/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'