Paper Info
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.
Year
DOI
Venue
2012
10.1007/978-3-642-33293-7_15
IPEC'12 Proceedings of the 7th international conference on Parameterized and Exact Computation
Keywords
DocType
Volume
coefficient extraction technique,set cover,set partition,extraction method,dp table,improved algorithm,linear sat,dp algorithm,sparse dp,sparse coefficient extraction,cnf sat
Conference
abs/1203.4063
Citations 
PageRank 
References 
7
0.50
22
Authors
3
Name
Order
Citations
PageRank
Petteri Kaski191266.03
Mikko Koivisto280355.81
Jesper Nederlof329424.22