  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.
