Paper Info
Title
A short note on Merlin-Arthur protocols for subset sum.
Abstract
Given n positive integers we show how to construct a proof that the number of subsets summing to a particular integer t equals a claimed quantity. The proof is of size O⁎(t), can be constructed in O⁎(t) time and can be probabilistically verified in time O⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅) omits factors polynomial in the input size.
Year
DOI
Venue
2017
10.1016/j.ipl.2016.09.002
Information Processing Letters
Keywords
DocType
Volume
Subset sum,Probabilistic verification,Exact algorithms,Merlin–Arthur protocol,Computational complexity
Journal
118
Issue
ISSN
Citations 
C
0020-0190
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Jesper Nederlof129424.22