Homomorphic hashing for sparse coefficient extraction

P. Kaski; M. Koivisto; J. Nederlof

doi:10.1007/978-3-642-33293-7_15

Homomorphic hashing for sparse coefficient extraction

P. Kaski, M. Koivisto, J. Nederlof

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

9 Citations (Scopus)

Abstract

We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT and SET COVER with sparse projections.

Original language	English
Title of host publication	Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings)
Editors	D. Thilikos, G.J. Woeginger
Place of Publication	Berlin
Publisher	Springer
Pages	147-158
ISBN (Print)	978-3-642-33292-0
DOIs	https://doi.org/10.1007/978-3-642-33293-7_15
Publication status	Published - 2012
Externally published	Yes
Event	7th International Symposium on Parameterized and Exact Computation (IPEC 2012) - Ljubljana, Slovenia Duration: 12 Sep 2012 → 14 Sep 2012 Conference number: 7 http://ipec2012.isoftcloud.gr

Publication series

Name	Lecture Notes in Computer Science
Volume	7535
ISSN (Print)	0302-9743

Conference

Conference	7th International Symposium on Parameterized and Exact Computation (IPEC 2012)
Abbreviated title	IPEC 2012
Country	Slovenia
City	Ljubljana
Period	12/09/12 → 14/09/12
Internet address	http://ipec2012.isoftcloud.gr

Access to Document

10.1007/978-3-642-33293-7_15

Fingerprint Dive into the research topics of 'Homomorphic hashing for sparse coefficient extraction'. Together they form a unique fingerprint.

Cite this

Kaski, P., Koivisto, M., & Nederlof, J. (2012). Homomorphic hashing for sparse coefficient extraction. In D. Thilikos, & G. J. Woeginger (Eds.), Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings) (pp. 147-158). (Lecture Notes in Computer Science; Vol. 7535). Springer. https://doi.org/10.1007/978-3-642-33293-7_15

@inproceedings{f8618b32d3544bf5b12ade3880a2ec17,

title = "Homomorphic hashing for sparse coefficient extraction",

abstract = "We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT and SET COVER with sparse projections.",

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

year = "2012",

doi = "10.1007/978-3-642-33293-7_15",

language = "English",

isbn = "978-3-642-33292-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "147--158",

editor = "D. Thilikos and G.J. Woeginger",

booktitle = "Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings)",

address = "Germany",

note = "7th International Symposium on Parameterized and Exact Computation (IPEC 2012), IPEC 2012 ; Conference date: 12-09-2012 Through 14-09-2012",

url = "http://ipec2012.isoftcloud.gr",

}

Kaski, P, Koivisto, M & Nederlof, J 2012, Homomorphic hashing for sparse coefficient extraction. in D Thilikos & GJ Woeginger (eds), Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings). Lecture Notes in Computer Science, vol. 7535, Springer, Berlin, pp. 147-158, 7th International Symposium on Parameterized and Exact Computation (IPEC 2012), Ljubljana, Slovenia, 12/09/12. https://doi.org/10.1007/978-3-642-33293-7_15

Homomorphic hashing for sparse coefficient extraction. / Kaski, P.; Koivisto, M.; Nederlof, J.

Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings). ed. / D. Thilikos; G.J. Woeginger. Berlin : Springer, 2012. p. 147-158 (Lecture Notes in Computer Science; Vol. 7535).

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

TY - GEN

T1 - Homomorphic hashing for sparse coefficient extraction

AU - Kaski, P.

AU - Koivisto, M.

AU - Nederlof, J.

N1 - Conference code: 7

PY - 2012

Y1 - 2012

N2 - We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT and SET COVER with sparse projections.

AB - We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT and SET COVER with sparse projections.

U2 - 10.1007/978-3-642-33293-7_15

DO - 10.1007/978-3-642-33293-7_15

M3 - Conference contribution

SN - 978-3-642-33292-0

T3 - Lecture Notes in Computer Science

SP - 147

EP - 158

BT - Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings)

A2 - Thilikos, D.

A2 - Woeginger, G.J.

PB - Springer

CY - Berlin

T2 - 7th International Symposium on Parameterized and Exact Computation (IPEC 2012)

Y2 - 12 September 2012 through 14 September 2012

ER -

Kaski P, Koivisto M, Nederlof J. Homomorphic hashing for sparse coefficient extraction. In Thilikos D, Woeginger GJ, editors, Parameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings). Berlin: Springer. 2012. p. 147-158. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-33293-7_15