Subset sum in the absence of concentration

P. Austrin; P. Kaski; M. Koivisto; J. Nederlof

doi:10.4230/LIPIcs.STACS.2015.48

Subset sum in the absence of concentration

P. Austrin, P. Kaski, M. Koivisto, J. Nederlof

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

18 Citations (Scopus)

154 Downloads (Pure)

Abstract

We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem

Original language	English
Title of host publication	32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015)
Editors	E.W. Mayr, N. Ollinger
Place of Publication	Dagstuhl
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	48-61
ISBN (Print)	978-3-939897-78-1
DOIs	https://doi.org/10.4230/LIPIcs.STACS.2015.48
Publication status	Published - 2015
Event	32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) - Technische Universität München, München, Germany Duration: 4 Mar 2015 → 7 Mar 2015 Conference number: 32 http://wwwmayr.in.tum.de/konferenzen/STACS2015/

Publication series

Name	LIPIcs: Leibniz International Proceedings in Informatics
Volume	30
ISSN (Print)	1868-8968

Conference

Conference	32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Abbreviated title	STACS 2015
Country/Territory	Germany
City	München
Period	4/03/15 → 7/03/15
Internet address	http://wwwmayr.in.tum.de/konferenzen/STACS2015/

Access to Document

10.4230/LIPIcs.STACS.2015.48

publishers versionFinal published version, 690 KB

Cite this

Austrin, P., Kaski, P., Koivisto, M., & Nederlof, J. (2015). Subset sum in the absence of concentration. In E. W. Mayr, & N. Ollinger (Eds.), 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015) (pp. 48-61). (LIPIcs: Leibniz International Proceedings in Informatics; Vol. 30). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.STACS.2015.48

Austrin, P. ; Kaski, P. ; Koivisto, M. et al. / Subset sum in the absence of concentration. 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015). editor / E.W. Mayr ; N. Ollinger. Dagstuhl : Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. pp. 48-61 (LIPIcs: Leibniz International Proceedings in Informatics).

@inproceedings{a3f1bc1d503541a79412d871d3d0fff5,

title = "Subset sum in the absence of concentration",

abstract = "We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem",

author = "P. Austrin and P. Kaski and M. Koivisto and J. Nederlof",

year = "2015",

doi = "10.4230/LIPIcs.STACS.2015.48",

language = "English",

isbn = "978-3-939897-78-1",

series = "LIPIcs: Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "48--61",

editor = "E.W. Mayr and N. Ollinger",

booktitle = "32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, M{\"u}nchen., Germany, March 4-7, 2015)",

note = "32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), STACS 2015 ; Conference date: 04-03-2015 Through 07-03-2015",

url = "http://wwwmayr.in.tum.de/konferenzen/STACS2015/",

}

Austrin, P, Kaski, P, Koivisto, M & Nederlof, J 2015, Subset sum in the absence of concentration. in EW Mayr & N Ollinger (eds), 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015). LIPIcs: Leibniz International Proceedings in Informatics, vol. 30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, pp. 48-61, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), München, Germany, 4/03/15. https://doi.org/10.4230/LIPIcs.STACS.2015.48

Subset sum in the absence of concentration. / Austrin, P.; Kaski, P.; Koivisto, M. et al.
32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015). ed. / E.W. Mayr; N. Ollinger. Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. p. 48-61 (LIPIcs: Leibniz International Proceedings in Informatics; Vol. 30).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Subset sum in the absence of concentration

AU - Austrin, P.

AU - Kaski, P.

AU - Koivisto, M.

AU - Nederlof, J.

N1 - Conference code: 32

PY - 2015

Y1 - 2015

N2 - We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem

AB - We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem

U2 - 10.4230/LIPIcs.STACS.2015.48

DO - 10.4230/LIPIcs.STACS.2015.48

M3 - Conference contribution

SN - 978-3-939897-78-1

T3 - LIPIcs: Leibniz International Proceedings in Informatics

SP - 48

EP - 61

BT - 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015)

A2 - Mayr, E.W.

A2 - Ollinger, N.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

CY - Dagstuhl

T2 - 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Y2 - 4 March 2015 through 7 March 2015

ER -

Austrin P, Kaski P, Koivisto M, Nederlof J. Subset sum in the absence of concentration. In Mayr EW, Ollinger N, editors, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015). Dagstuhl: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2015. p. 48-61. (LIPIcs: Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.STACS.2015.48

Subset sum in the absence of concentration

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this