arXiv:2611.16176 · v1

A One-Sided Sublinear-Query Tester for Bounded-Degree 2SAT

首次提交 2026-11-12 10:08

版本更新 2026-11-12 10:08

雷达观测 2026-11-13 14:16

摘要

We give a one-sided tester for satisfiability of 2CNF formulas in the bounded-degree model. For every degree bound $Δ$, distance parameter $\varepsilon>0$, and $ν\in(0,1/2)$, its query complexity on $n$-variable formulas is $\widetilde O_{\varepsilon,Δ,ν}(n^{1/2+ν})$.