Homomorphic Hashing for Sparse Coefficient Extraction

Details Homomorphic Hashing for Sparse Coefficient Extraction Homomorphic Hashing for Sparse Coefficient Extraction

2012-03-19

arxiv.org/abs/1203.4063v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Homomorphic Hashing for Sparse Coefficient Extraction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Homomorphic Hashing for Sparse Coefficient Extraction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Homomorphic Hashing for Sparse Coefficient Extraction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-212235