Search

The k -ary n -cubes are a generalization of the hypercubes to alphabets of cardinality k , with k ≥ 2. More precisely, a k -ary n -cube is a graph with k n vertices associated to the k -ary words of length n. Given a k -ary word f , the k-ary n-cube avoiding f is the subgraph obtained deleting those vertices which contain f as a factor. When such a subgraph is isometric to the cube, for any n ≥ 1 , the word f is said isometric. A binary word f is isometric if and only if it is Ham-isometric , i.e., for any pair of f -free binary words u and v , u can be transformed in v by complementing the bits on which they differ and generating only f -free words. The case of a k -ary alphabet, with k ≥ 2 , is here investigated. From k ≥ 4 , the isometricity in terms of cubes is no longer captured by the Ham-isometricity, but by the Lee-isometricity. Then, Ham-isometric and Lee-isometric k -ary words are characterized in terms of their overlaps with errors. The minimal length of two words which witness the non-isometricity of a word f is called its index. The index of f is bounded in terms of its length and the bounds are shown tight by examples. [ABSTRACT FROM AUTHOR]

Group encryption (GE), introduced by Kiayias, Tsiounis and Yung (Asiacrypt'07), is the encryption analogue of group signatures. It allows to send verifiably encrypted messages satisfying certain requirements to certified members of a group, while keeping the anonymity of the receivers. Similar to the tracing mechanism in group signatures, the receiver of any ciphertext can be identified by an opening authority - should the needs arise. The primitive of GE is motivated by a number of interesting privacy-preserving applications, including the filtering of encrypted emails sent to certified members of an organization. This paper aims to improve the state-of-affairs of GE systems. Our first contribution is the formalization of fully dynamic group encryption (FDGE) - a GE system simultaneously supporting dynamic user enrolments and user revocations. The latter functionality for GE has not been considered so far. As a second contribution, we realize the message filtering feature for GE based on a list of t -bit keywords and 2 commonly used policies: "permissive" - accept the message if it contains at least one of the keywords as a substring; "prohibitive" - accept the message if all of its t -bit substrings are at Hamming distance at least d from all keywords, for d ≥ 1. This feature so far has not been substantially addressed in existing instantiations of GE based on DCR, DDH, pairing-based and lattice-based assumptions. Our third contribution is the first instantiation of GE under code-based assumptions. The scheme is more efficient than the lattice-based construction of Libert et al. (Asiacrypt'16) - which, prior to our work, is the only known instantiation of GE under post-quantum assumptions. Our scheme supports the 2 suggested policies for message filtering, and in the random oracle model, it satisfies the stringent security notions for FDGE that we put forward. [ABSTRACT FROM AUTHOR]

In an inverse combinatorial optimization problem, a feasible solution is given and is not optimal under the current parameters. The aim is to make the feasible solution optimal by modifying the current parameters as little as possible. The modification cost can be measured by different norms, such as weighted l 1 norm, weighted l 2 norm, weighted l ∞ norm, weighted Hamming distance and so on. In this paper, we focus on the constrained inverse minimum flow problems under the weighted Hamming distance. Three different models are considered: the general problem under the weighted bottleneck-type Hamming distance and two cases under the mixed of sum-type and bottleneck type. Strongly polynomial algorithms are presented for the models we studied. [ABSTRACT FROM AUTHOR]

An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O (n m 1.381 + N) -time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O (k 2 m G + k N) -time and O (m) -space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O (k m G + k N) -time and O (m) -space algorithm for solving the problem under Hamming distance. [ABSTRACT FROM AUTHOR]

In the k -mappability problem, we are given a string x of length n and integers m and k , and we are asked to count, for each length- m factor y of x , the number of other factors of length m of x that are at Hamming distance at most k from y. We focus here on the version of the problem where k = 1. There exists an algorithm to solve this problem for k = 1 requiring time O (m n log ⁡ n / log ⁡ log ⁡ n) using space O (n). Here we present two new algorithms that require worst-case time O (m n) and O (n log ⁡ n log ⁡ log ⁡ n) , respectively, and space O (n) , thus greatly improving the previous result. Moreover, we present another algorithm that requires average-case time and space O (n) for integer alphabets of size σ if m = Ω (log σ ⁡ n). Notably, we show that this algorithm is generalizable for arbitrary k , requiring average-case time O (k n) and space O (n) if m = Ω (k log σ ⁡ n) , assuming that the letters are independent and uniformly distributed random variables. Finally, we provide an experimental evaluation of our average-case algorithm demonstrating its competitiveness to the state-of-the-art implementation. [ABSTRACT FROM AUTHOR]

The Möbius transform is a crucial transformation into the Boolean world; it allows to change the Boolean representation between the True Table and Algebraic Normal Form. In this work, we introduce a new algebraic point of view of this transformation based on the polynomial form of Boolean functions. It appears that we can perform a new notion: the Möbius computation variable by variable and new computation properties. As a consequence, we propose new algorithms which can produce a huge speed up of the Möbius computation for sub-families of Boolean function. Furthermore we compute directly the Möbius transformation of some particular Boolean functions. Finally, we show that for some of them the Hamming weight is directly related to the algebraic degree of specific factors. [ABSTRACT FROM AUTHOR]

Given a set of n strings of length L and a radius d , the closest string problem (CSP for short) asks for a string t s o l that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n 2 L + n 2 d ⋅ 6.16 d) time, while the previously best deterministic algorithm runs in O (n L + n d 3 ⋅ 6.731 d) time. [ABSTRACT FROM AUTHOR]

Given n vectors x 0 , x 1 , ... , x n − 1 in { 0 , 1 } m , how to find two vectors whose pairwise Hamming distance is minimum? This problem is known as the Closest Pair Problem. If these vectors are generated uniformly at random except two of them are correlated with Pearson-correlation coefficient ρ , then the problem is called the Light Bulb Problem. In this work, we propose a novel coding-based scheme for the Closest Pair Problem. We design both randomized and deterministic algorithms, which achieve the best-known running time when the length of input vectors m is small and the minimum distance is very small compared to m. Specifically, the running time of our randomized algorithm is O (n log 2 ⁡ n ⋅ 2 c m ⋅ poly (m)) and the running time of our deterministic algorithm is O (n log ⁡ n ⋅ 2 c ′ m ⋅ poly (m)) , where c and c ′ are constants depending only on the (relative) distance of the closest pair. When applied to the Light Bulb Problem, our result yields state-of-the-art deterministic running time when the Pearson-correlation coefficient ρ is very large. Specifically, when ρ ≥ 0.9933 , our deterministic algorithm runs faster than the previously best deterministic algorithm (Alman, SOSA 2019). [ABSTRACT FROM AUTHOR]

Given a binary word relation τ onto A ⁎ and a finite language X ⊆ A ⁎ , a τ -Gray cycle over X consists in a permutation (w [ i ]) 0 ≤ i ≤ | X | − 1 of X such that each word w [ i ] is an image under τ of the previous word w [ i − 1 ]. We define the complexity measure λ A , τ (n) , equal to the largest cardinality of a language X having words of length at most n , and st. some τ -Gray cycle over X exists. The present paper is concerned with τ = σ k , the so-called k -character substitution, st. (u , v) ∈ σ k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length σ k -Gray cycles. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we consider an inverse obnoxious p -median location problem with p ≥ 2 on trees in which the aim is to change the edge lengths at the minimum total cost so that a predetermined set of p vertices becomes an obnoxious p -median location. A novel combinatorial algorithm with O (p 2 | V (T) | 2 log 2 ⁡ | V (T) |) time complexity is proposed for obtaining an optimal solution of the problem under the weighted Manhattan norm. Moreover, optimal solution algorithms with O (p 2 | V (T) |) time complexity are developed for the problem under the weighted Chebyshev norm and the weighted bottleneck-type Hamming distance. [ABSTRACT FROM AUTHOR]

A string T of length m is periodic in P of length p if P is a substring of T and T [ i ] = T [ i + p ] for all 0 ≤ i ≤ m − p − 1 and m ≥ 2 p . The shortest such prefix, P , is called the period of T (i.e., P = T [ 0 . . p − 1 ] ). In this paper we investigate the period recovery problem. Given a string S of length n , find the primitive period(s) P such that the distance between S and a string T that is periodic in P is below a threshold τ . We consider the period recovery problem over both the Hamming distance and the edit distance. For the Hamming distance case, we present an O ( n log ⁡ n ) -time algorithm, where τ is given as ⌊ n ( 2 + ϵ ) p ⌋ , for ϵ > 0 . For the edit distance case, τ = ⌊ n ( 3.75 + ϵ ) p ⌋ and ϵ > 0 , we provide an O ( n 4 / 3 ) -time algorithm. [ABSTRACT FROM AUTHOR]

An n -bit Gray code is a sequence of all n -bit vectors such that consecutive vectors differ in a single bit. It is well-known that given α , β ∈ { 0 , 1 } n , an n -bit Gray code between α and β exists iff the Hamming distance d ( α , β ) of α and β is odd. We generalize this classical result to k pairwise disjoint pairs α i , β i ∈ { 0 , 1 } n : if d ( α i , β i ) is odd for all i and k < n , then the set of all n -bit vectors can be partitioned into k sequences such that the i -th sequence leads from α i to β i and consecutive vectors differ in a single bit. This holds for every n > 1 with one exception in the case when n = k + 1 = 4 . Our result is optimal in the sense that for every n > 2 there are n pairwise disjoint pairs α i , β i ∈ { 0 , 1 } n with d ( α i , β i ) odd for which such sequences do not exist. [ABSTRACT FROM AUTHOR]

A growing number of measures of sequence similarity are being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs , and so on. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O ( n 2 ) . Preliminary experiments demonstrate the potential applicability to phylogeny and classification of these similarity measures. [ABSTRACT FROM AUTHOR]

Suppose we have two players A and C , where player A has a string s [ 0 . . u − 1 ] and player C has a string t [ 0 . . u − 1 ] and none of the two players knows the other's string. Assume that s and t are both over an integer alphabet [ σ ] = [ 0 , σ − 1 ] , where the first string contains n non-zero entries. We would wish to answer the following basic question. Assuming that s and t differ in at most k positions, how many bits does player A need to send to player C so that he can recover s with certainty? Further, how much time does player A need to spend to compute the sent bits and how much time does player C need to recover the string s ? This problem has a certain number of applications, for example in databases, where each of the two parties possesses a set of n key-value pairs, where keys are from the universe [ u ] and values are from [ σ ] and usually n ≪ u . In this paper, we show a time and message-size optimal Las Vegas reduction from this problem to the problem of systematic error correction of k errors for strings of length Θ ( n ) over an alphabet of size 2 Θ ( log ⁡ σ + log ⁡ ( u / n ) ) . The additional running time incurred by the reduction is linear expected (randomized) for player A and linear worst-case (deterministic) for player C , but the correction works with certainty. When using the popular Reed–Solomon codes, the reduction gives a protocol that transmits O ( k ( log ⁡ u + log ⁡ σ ) ) bits and runs in time O ( n ⋅ polylog ( n ) ( log ⁡ u + log ⁡ σ ) ) for all values of k . The time is expected for player A (encoding time) and worst-case for player C (decoding time). The message size is optimal whenever k ≤ ( u σ ) 1 − Ω ( 1 ) . [ABSTRACT FROM AUTHOR]

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. [ABSTRACT FROM AUTHOR]

Abstract: We present an efficient probabilistic algorithm for testing approximate membership of words to regular languages modulo the edit distance. Our algorithm runs in polynomial time in the size of the input automaton and the inverse error precision in contrast to all previous approaches, and independently of the size of the input word. We also improve a previous approximate membership tester modulo the Hamming distance such that it runs in polynomial complexity time, but with larger polynomials than for the edit distance. [Copyright &y& Elsevier]

Abstract: In this paper, we study the palindrome retrieval problem with the input string compressed into run-length encoded form. Given a run-length encoded string , we show how to preprocess  to support subsequent queries of the longest palindrome centered at any specified position and having any specified number of mismatches between its arms. We present two algorithms for the problem, both taking time and space polynomial in the compressed string size. Let  denote the number of runs of  and let denote the number of mismatches. The first algorithm, devised for small , identifies the desired palindrome in  time with  preprocessing time, while the second algorithm achieves  query time, independent of , after -time preprocessing. [Copyright &y& Elsevier]

Abstract: The inverse optimization problem is to modify the weight (or cost, length, capacity and so on) such that a given feasible solution becomes an optimal solution. In this paper, we consider the inverse min–max spanning tree problem under the weighted sum-type Hamming distance. For the model considered, we present its combinatorial algorithm that runs in strongly polynomial times. [Copyright &y& Elsevier]

Abstract: Given a string x and a language L, the Hamming distance of x to L is the minimum Hamming distance of x to any string in L. The edit distance of a string to a language is analogously defined. First, we prove that there is a language in such that both Hamming and edit distance to this language are hard to approximate; they cannot be approximated with factor , for any , unless (n denotes the length of the input string). Second, we show the parameterized intractability of computing the Hamming distance. We prove that for every there exists a language in for which computing the Hamming distance is -hard. Moreover, there is a language in for which computing the Hamming distance is -hard. Then we show that the problems of computing the Hamming distance and of computing the edit distance are in some sense equivalent by presenting approximation ratio preserving reductions from the former to the latter and vice versa. Finally, we define to be the class of languages to which the Hamming distance can efficiently, i.e.in polynomial time, be computed. We show some properties of the class . On the other hand, we give evidence that a characterization in terms of automata or formal languages might be difficult. [Copyright &y& Elsevier]

We recently introduced evolutive tandem repeats with jump (using Hamming distance) (Proc. MFCS’02: the 27th Internat. Symp. Mathematical Foundations of Computer Science, Warszawa, Otwock, Poland, August 2002, Lecture Notes in Computer Science, Vol. 2420, Springer, Berlin, pp. 292–304) which consist in a series of almost contiguous copies having the following property: the Hamming distance between two consecutive copies is always smaller than a given parameter e. In this article, we present a significative improvement that speeds up the detection of evolutive tandem repeats. It is based on the progressive computation of distances between candidate copies participating to the evolutive tandem repeat. It leads to a new algorithm, still quadratic in the worst case, but much more efficient on average, authorizing larger sequences to be processed. [Copyright &y& Elsevier]