Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity
summary
Presents concrete Merlin–Arthur protocols and time bounds: near-linear MA for 3SUM by reducing to counting solutions mod d, encoding inputs as a polynomial A(x), testing coefficients via Schwartz–Zippel and fast polynomial arithmetic (FFT); general kSUM certified in about N^{k/3} MA time; subset-sum certification in roughly 2^{n/3} MA; counting zero-weight k-cliques in N^{ceil(k/2)} MA (4-clique in N^2); APSP in nearly N^2 MA; k-ONSAT uncertifiability improved to ~2^{n/2 - Θ(n/k)} and true QBF in 2^{4n/5} MA.
AI-written summary · about