Published November 2012
| public
Journal Article
On the Hardness of Counting and Sampling Center Strings
- Creators
- Boucher, Christina
- Omar, Mohamed
Abstract
Given a set S of n strings, each of length ℓ, and a nonnegative value d, we define a center string as a string of length ℓ that has Hamming distance at most d from each string in S. The #CLOSEST STRING problem aims to determine the number of center strings for a given set of strings S and input parameters n, ℓ, and d. We show #CLOSEST STRING is impossible to solve exactly or even approximately in polynomial time, and that restricting #CLOSEST STRING so that any one of the parameters n, ℓ, or d is fixed leads to a fully polynomial-time randomized approximation scheme (FPRAS). We show equivalent results for the problem of efficiently sampling center strings uniformly at random (u.a.r.).
Additional Information
© 2012 IEEE. Manuscript received 12 May 2011; revised 7 Jan. 2012; accepted 29 Apr. 2012; published online 23 May 2012. The authors would like to thank Nick Wormald for his discussions and insights concerning the results presented in this paper. They gratefully acknowledge research support of the Natural Sciences and Engineering Research Council of Canada (NSERC).Additional details
- Eprint ID
- 36466
- Resolver ID
- CaltechAUTHORS:20130118-090959190
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Created
-
2013-01-18Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 13168084