Grayscale-invariant reversible data hiding (GI-RDH) in color images is a data embedding framework in which the grayscales of a marked color image must be identical to those of the host color image. Recently, some state-of-the-art GI-RDH schemes were proposed. However, their performance in embedding distortion is unsatisfactory. In order to obtain better image quality, a well-known histogram-shifting-based RDH method called multiple histograms modification (MHM) is considered. In this paper, we propose an MHM-based GI-RDH scheme. First, we modified our previous GI-RDH scheme using a multiple-histogram-shifting approach instead of a difference expansion approach. Next, we designed a procedure to select expansion–bin pairs for generated histograms to achieve low embedding distortion through further data embedding. Specifically, we analyzed the expected embedding distortion of our MHM-based GI-RDH scheme given any set of expansion–bin pairs. We then formulated an optimization problem called the GI-MHM minimization problem to identify the optimal expansion–bin pairs for further embedding tasks. Finally, we generated an approximated solution for the GI-MHM minimization problem and conducted the embedding task with these selected expansion–bin pairs. The experimental results revealed that the proposed GI-RDH scheme outperformed previous methods when the embedding capacity was small.

Log-rank conjecture is one of challenging problems in communication complexity. It is known to hold for some special function classes such as XOR functions f(x ⊕ y) when the outer function f is monotone, symmetric, AC0, low F2-degree, linear threshold or read-k. However, for AND functions f(x ∧ y), Log-rank conjecture is only known to hold when the outer function is a monotone function or a function with small alternating numbers. In this paper, we show that Log-rank conjecture holds for AND functions whose outer functions are read-once F2-degree polynomials, constant-F2-degree polynomials, and symmetric functions. For read-once and symmetric AND functions, their proof are based on the elementary analysis of Möbius sparsity of the outer functions and designing efficient protocols for computing the corresponding AND functions in terms of the Möbius sparsity of their outer functions. For a constant- F2-degree AND function f(x ∧ y), we use the concept of the variable rank to design a decision tree for computing f where the tree depth is bounded above by a polynomial in the logarithm of the Möbius sparsity of f. The communication protocol can be obtained easily from the constructed decision tree. Our results deepen the understanding of the log-rank conjecture for AND functions.

A distance-preserving mapping is a one-to-one function f from p-ary vectors of length m to q-ary vectors of length n such that any two distinct p-ary vectors are mapped to two different q-ary vectors with an equal or greater Hamming distance. A distance-increasing mapping is a special distance-preserving mapping which strictly increases the distance by at least one if the distance of two distinct input vectors is less than the length of the output vectors. A constant composition code over a k-ary alphabet has the property that the numbers of occurrences of the k symbols within a codeword are fixed for each codeword. One of the most important applications of distance-preserving mappings and distance-increasing mappings is to construct constant composition codes, of which the permutation codes are a special subclass. There are two results in this paper. First, we propose a swap-based distance-increasing mapping from binary vectors to quaternary constant composition vectors. Second, we prove that it is impossible to construct any swap-based distance-preserving mappings from binary vectors to ternary constant composition vectors under the swap model that we defined.

Constant composition codes arise from applications in powerline communication and balanced scheduling in frequency hopping. Binary constant weight codes and permutation codes are special types of constant composition codes. In ISIT 2009, Chang and Wu proposed a method to construct constant composition codes through distance-increasing mappings from binary vectors to quaternary constant composition vectors. But they did not touch the decoding problem. In this paper, we present efficient decoding algorithms for the constant composition codes generated from distance-increasing (or distance-preserving) mappings.

A distance-preserving mapping is a one-to-one function f from p-ary vectors of length m to q-ary vectors of length n such that any two distinct p-ary vectors are mapped to two different q-ary vectors with an equal or greater Hamming distance. A special distance-preserving mapping called a distance-increasing mapping is a mapping which increases the distance at least one if the distance of two distinct input strings are not equal to the output length. A constant composition vector is a vector under the restriction that each alphabet symbol occurs a given number of times. In this paper, we propose a distance-increasing mapping from binary vectors to constant composition quaternary vectors. We also give an optimal impossibility result for constructing distance-preserving mapping from binary vectors to constant composition ternary vectors in the so-called swapping model.

We give a simple construction of distance-preserving mappings from ternary vectors to permutations (3-DPM). Our result gives a lower bound for permutation arrays, i.e., P(n, d) ges A3(n, d) , which significantly improves previous lower bounds for d les 3n / 5.

For$\delta \in (0,1)$and$k,n\in \BBN $, we study the task of transforming a hard function$f: \{0,1\}^{n}\to \{0,1\} $, with which any small circuit disagrees on$(1-\delta )/2$fraction of the input, into a harder function$f^{\prime}$, with which any small circuit disagrees on$(1-\delta ^{k})/2$fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth$d$and size$2^{o(k^{1/d})}$or by a nondeterministic circuit of size$o(k/\log k)$(and arbitrary depth) for any$\delta \in (0,1)$. This extends the result of Viola, which only works when$(1-\delta )/2$is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function$f^{\prime}$, even against uniform machines, one has to start with a function$f$, which is hard against nonuniform algorithms with$\Omega (k\log (1/\delta ))$bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with$(1-\delta )/2=2^{-n}$. Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

We study the task of transforming a hard function f, with which any small circuit disagrees on (1 - /spl delta/)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - /spl delta//sup k/)/2 fraction of the input, for /spl delta/ /spl isin/ (0,1) and k /spl isin/ /spl Nopf/. We show that this process cannot be carried out in a black-box way by a circuit of depth d and size 2/sup o(k2/d)/ or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth). In particular, for k = 2/sup /spl Omega/(n)/, such hardness amplification cannot be done in ATIME(O(1), 2/sup o(n)/. Therefore, hardness amplification in general requires a high complexity. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently non-uniform in the following sense. Given as an oracle any algorithm which agrees with f' on (1 - /spl delta//sup k/)/2 fraction of the input, we still need an additional advice of length /spl Omega/(k log(1//spl delta/)) in order to compute f correctly on (1 - /spl delta/)/2 fraction of the input. Therefore, to guarantee the hardness, even against uniform machines, of the function f', one has to start with a function f which is hard against non-uniform circuits. Finally, we derive similar lower bounds for any black-box construction of pseudorandom generators from hard functions.

We study the distance measures between two probability distributions via two different distance metrics, a new metric induced from Jensen-Shannon divergence, and the well known L/sub 1/ metric. We show that several important results and constructions in computational complexity under the L/sub 1/ metric carry over to the new metric, such as Yao's next-bit predictor, the existence of extractors, the leftover hash lemma, and the construction of expander graph based extractor. Finally, we show that the useful parity lemma in studying pseudorandomness does not hold in the new metric.