Homomorphic hashing for sparse coefficient extraction

DOI10.1007/978-3-642-33293-7_15MaRDI QIDQ4899249zbMATH OpenOpenAlexFDO

Authors Petteri Kaski, Mikko Koivisto, Jesper Nederlof

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.4063

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Nonnumerical algorithms (68W05)

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 with sparse projections.

Recommendations

• scientific article; zbMATH DE number 432798
• Saving space by algebraization
• Dynamic programming on the word RAM
• Space saving by dynamic algebraization
• On perfect hashing of numbers with sparse digit representation via multiplication by a constant

Cited in

(2)

• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Model counting for CNF formulas of bounded modular treewidth

This page was built for publication: Homomorphic hashing for sparse coefficient extraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899249)