A short note on Merlin-Arthur protocols for subset sum

J. Nederlof

doi:10.1016/j.ipl.2016.09.002

A short note on Merlin-Arthur protocols for subset sum

J. Nederlof

Research output: Contribution to journal › Article › Academic › peer-review

10 Citations (Scopus)

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 View the MathML sourceO⁎(t), can be constructed in O⁎(t)O⁎(t) time and can be probabilistically verified in time View the MathML sourceO⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅)O⁎(⋅) omits factors polynomial in the input size.

Original language	English
Pages (from-to)	15-16
Number of pages	2
Journal	Information Processing Letters
Volume	118
Issue number	Februari
DOIs	https://doi.org/10.1016/j.ipl.2016.09.002
Publication status	Published - 1 Feb 2017

Keywords

Computational complexity
Exact algorithms
Merlin–Arthur protocol
Probabilistic verification
Subset sum

Access to Document

10.1016/j.ipl.2016.09.002

Cite this

@article{48ba7151339848f4bdd58312d015a0ab,

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 View the MathML sourceO⁎(t), can be constructed in O⁎(t)O⁎(t) time and can be probabilistically verified in time View the MathML sourceO⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅)O⁎(⋅) omits factors polynomial in the input size.",

keywords = "Computational complexity, Exact algorithms, Merlin–Arthur protocol, Probabilistic verification, Subset sum",

author = "J. Nederlof",

year = "2017",

month = feb,

day = "1",

doi = "10.1016/j.ipl.2016.09.002",

language = "English",

volume = "118",

pages = "15--16",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "Februari",

}

TY - JOUR

T1 - A short note on Merlin-Arthur protocols for subset sum

AU - Nederlof, J.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - 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 View the MathML sourceO⁎(t), can be constructed in O⁎(t)O⁎(t) time and can be probabilistically verified in time View the MathML sourceO⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅)O⁎(⋅) omits factors polynomial in the input size.

AB - 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 View the MathML sourceO⁎(t), can be constructed in O⁎(t)O⁎(t) time and can be probabilistically verified in time View the MathML sourceO⁎(t) with at most 1/2 one-sided error probability. Here O⁎(⋅)O⁎(⋅) omits factors polynomial in the input size.

KW - Computational complexity

KW - Exact algorithms

KW - Merlin–Arthur protocol

KW - Probabilistic verification

KW - Subset sum

UR - http://www.scopus.com/inward/record.url?scp=84988484352&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2016.09.002

DO - 10.1016/j.ipl.2016.09.002

M3 - Article

SN - 0020-0190

VL - 118

SP - 15

EP - 16

JO - Information Processing Letters

JF - Information Processing Letters

IS - Februari

ER -

A short note on Merlin-Arthur protocols for subset sum

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this