Homomorphic hashing for sparse coefficient extraction

P. Kaski, M. Koivisto, J. Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationParameterized and Exact Computation (7th International Symposium, IPEC 2012, Ljubljana, Slovenia, September 12-14, 2012. Proceedings)
EditorsD. Thilikos, G.J. Woeginger
Place of PublicationBerlin
PublisherSpringer
Pages147-158
ISBN (Print)978-3-642-33292-0
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event7th International Symposium on Parameterized and Exact Computation (IPEC 2012) - Ljubljana, Slovenia
Duration: 12 Sep 201214 Sep 2012
Conference number: 7
http://ipec2012.isoftcloud.gr

Publication series

NameLecture Notes in Computer Science
Volume7535
ISSN (Print)0302-9743

Conference

Conference7th International Symposium on Parameterized and Exact Computation (IPEC 2012)
Abbreviated titleIPEC 2012
CountrySlovenia
CityLjubljana
Period12/09/1214/09/12
Internet address

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