Search

For each non-constant Boolean function q , Klapper introduced the notion of q -transforms of Boolean functions. The q -transform of a Boolean function f is related to the Hamming distances from f to the functions obtainable from q by nonsingular linear change of basis. In this work, we discuss the existence of q -nearly bent functions, a new family of Boolean functions characterized by the q -transform. We prove that any balanced Boolean functions (linear or non-linear) are q -nearly bent if q has weight one, which gives a positive answer to an open question (whether there exist non-affine q -nearly bent functions) proposed by Klapper. We also prove a necessary condition for checking when a function is not q -nearly bent. [ABSTRACT FROM AUTHOR]

A border p of a string x is an enhanced cover of x if the number of positions of x that lie within some occurrence of p is the maximum among all borders of x. (String p is a border of x if p is both a proper prefix and a suffix of x.) In this paper, two more general notions based on enhanced covers are introduced: a k -approximate enhanced cover and a relaxed k -approximate enhanced cover, where a fixed maximum number of errors k under the Hamming distance is considered. The k -approximate enhanced cover of x is its border, and its k -approximate occurrences are also considered in the covered number of positions of x. The relaxed k -approximate enhanced cover of x is a factor of x and a k -approximate border of x. Algorithms that compute all the variations of k -approximate enhanced covers mentioned above are presented in this paper. [ABSTRACT FROM AUTHOR]

Parameterized pattern matching is a string searching variant that was initially defined to detect duplicate code but later proved to support several other applications. In particular, two equal-length strings X and Y are a parameterized-match if there exists a bijective function g for which every text symbol in X is equal to g (Y). Baker was the first researcher to have addressed this problem (Baker, 1993) and, since then, many others have followed her work. She did, indeed, open up a wide field of extensive research. Over the years, many variants and extensions that have been pursued include: parameterized matching under edit and Hamming distances, parameterized multi-pattern matching, two dimensional parameterized matching, structural matching, function matching, and the very recent developments in succinct and streaming models. This accelerated research could only be justified by the usefulness of its practical applications such as in software maintenance, image processing and bioinformatics to name some. Even though the problem was posed about 25 years ago, research on parameterized matching is still very active. Its extensive study over the years and its current relevance motivate us to review the most notorious contributions as road map for current and future research. [ABSTRACT FROM AUTHOR]

We present a method based on simulated annealing to obtain a nested split graph that approximates a real complex graph. This is used to compute a number of graph indices using very efficient algorithms that we develop, leveraging the geometrical properties of nested split graphs. Practical results are given for six graphs from such diverse areas as social networks, communication networks, word associations, and molecular chemistry. We present a critical analysis of the appropriate perturbation schemes that search the whole space of nested split graphs and the distance functions that gauge the dissimilarity between two graphs. [ABSTRACT FROM AUTHOR]

The idea of the inverse optimization problem is to adjust the value of the parameters such that the observed feasible solution becomes optimal. The modification cost can be measured by different norms, such as l 1 , l 2 , l ∞ norms and the Hamming distance, and the goal is to adjust the parameters as little as possible. In this paper, we consider the inverse minimum flow problem under the weighted sum-type Hamming distance, where the lower and upper bounds for the arcs should be changed as little as possible under the weighted sum-type Hamming distance such that a given feasible flow becomes a minimum flow. Two models are considered: the unbounded case and the general bounded case. We present their respective combinatorial algorithms that both run in O ( n m ) time in terms of the minimum cut method. Computational examples are presented to illustrate our algorithms. [ABSTRACT FROM AUTHOR]

Rotation symmetric (RS) Boolean functions have been extensively studied in recent years because of their applications in cryptography. In cryptographic applications, it is usually important to know the weight of the functions, so much research has been done on the problem of determining such weights. Recently it was proved that for cubic RS functions in n variables generated by a single monomial, the weights of the functions as n increases satisfy a linear recursion. Furthermore, explicit methods were found for generating these recursions and the initial values needed to use the recursions. It is important to be able to compute the order of these recursions without needing to determine all of the coefficients. This paper gives a technique for doing that in many cases, based on a new notion of towers of RS Boolean functions. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the following two hypercube coloring problems: given and , find the minimum number of colors, denoted as (resp. ), needed to color the vertices of the -cube such that any two vertices with Hamming distance at most (resp. exactly ) have different colors. These problems originally arose in the study of the scalability of optical networks. Using methods in coding theory, we show that for any odd number , and give two upper bounds on . The first upper bound improves on that of Kim, Du and Pardalos. The second upper bound improves on the first one for small . Furthermore, we derive an inequality on and . [Copyright &y& Elsevier]