Remark on balanced incomplete block designs,near-resolvable block designs,and <Emphasis Type="Italic">q</Emphasis>-ary constant-weight codes

We prove that any balanced incomplete block design B(v, k, 1) generates a nearresolvable balanced incomplete block design NRB(v, k ? 1, k ? 2). We establish a one-to-one correspondence between near-resolvable block designs NRB(v, k ?1, k ?2) and the subclass of nonbinary (optimal, equidistant) constant-weight codes meeting the generalized Johnson bound.     

On partitions of an <Emphasis Type="Italic">n</Emphasis>-cube into nonequivalent perfect codes

We prove that for all n = 2^k ? 1, k ≥ 5, there exists a partition of the set of all binary vectors of length n into pairwise nonequivalent perfect binary codes of length n with distance 3.     

On transitive partitions of an <Emphasis Type="Italic">n</Emphasis>-cube into codes

We present methods to construct transitive partitions of the set E ⁿ of all binary vectors of length n into codes. In particular, we show that for all n = 2 ^k ? 1, k ≥ 3, there exist transitive partitions of E ⁿ into perfect transitive codes of length n.     

On the Construction of Transitive Codes

Application of some known methods of code construction (such as the Vasil'ev, Plotkin, and Mollard methods) to transitive codes satisfying certain auxiliary conditions yields infinite classes of large-length transitive codes, in particular, at least ?k/2?² nonequivalent perfect transitive codes of length n = 2 ^k ? 1, k > 4. A similar result is valid for extended perfect transitive codes.     

Using dynamic pixel value mapping method to construct visible and reversible image watermarking scheme

A reversible and visible image watermarking scheme extracts a visibly embedded binary watermark image and recovers the original cover image. This paper presents a reversible and visible image watermarking scheme that embeds visible watermarks into a part of the cover image, called the embedded region R, and embeds required binary strings into the whole image through the conventional difference-expansion method. The size of the embedded visible watermark is determined by the coefficient k; a large k value leads to a large embedded region for the visible watermark. The embedded region R is first segmented to non-overlapped k×k blocks, and each block is related to one bit of the watermark image. For those blocks that are related to the logo bits of the watermark image, these k×k blocks are adjusted by the proposed dynamic pixel value mapping method for highly visual detection. The binary bit string S, composed of the binary watermark image and LSB bits of the logo watermark bits’ corresponding k×k blocks, is embedded into the cover image using the conventional difference-expansion method. Experimental results show that the watermark is clearly embedded into the embedded region R and that the distortion of the reversible embedding is limited.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

Conflict-avoiding codes and cyclic triple systems

The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length n and Hamming weight 3 and having the following property: any 3 × n matrix whose rows are cyclic shifts of three different code vectors contains a 3 × 3 permutation matrix as a submatrix. This property (in the special case w = 3) characterizes conflict-avoiding codes of length n for w active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of w active users to transmit a data packet successfully in one of w attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length n with w = 3 is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for w = 3 which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.     

On ℤ<Subscript>4</Subscript>-linear codes with the parameters of Reed-Muller codes

For any pair of integers r and m, 0 ≤ r ≤ m, we construct a class of quaternary linear codes whose binary images under the Gray map are codes with the parameters of the classical rth-order Reed-Muller code RM(r, m).     

Cardinality spectra of components of correlation immune functions,bent functions,perfect colorings,and codes

We study cardinalities of components of perfect codes and colorings, correlation immune functions, and bent function (sets of ones of these functions). Based on results of Kasami and Tokura, we show that for any of these combinatorial objects the component cardinality in the interval from 2 ^k to 2 ^k+1 can only take values of the form 2 ^k+1 ? 2 ^p , where p ∈ {0, ..., k} and 2 ^k is the minimum component cardinality for a combinatorial object with the same parameters. For bent functions, we prove existence of components of any cardinality in this spectrum. For perfect colorings with certain parameters and for correlation immune functions, we find components of some of the above-given cardinalities.     

On Cosets of Weight 4 of Binary BCH Codes with Minimum Distance 8 and Exponential Sums

We study coset weight distributions of binary primitive (narrow-sense) BCH codes of length n = 2 ^m (m odd) with minimum distance 8. In the previous paper [1], we described coset weight distributions of such codes for cosets of weight j = 1, 2, 3, 5, 6. Here we obtain exact expressions for the number of codewords of weight 4 in terms of exponential sums of three types, in particular, cubic sums and Kloosterman sums. This allows us to find the coset distribution of binary primitive (narrow-sense) BCH codes with minimum distance 8 and also to obtain some new results on Kloosterman sums over finite fields of characteristic 2.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Upper bound on the minimum distance of LDPC codes over <Emphasis Type="Italic">GF</Emphasis>(<Emphasis Type="Italic">q</Emphasis>) based on counting the number of syndromes

In [1] a syndrome counting based upper bound on the minimum distance of regular binary LDPC codes is given. In this paper we extend the bound to the case of irregular and generalized LDPC codes over GF(q). A comparison with the lower bound for LDPC codes over GF(q), upper bound for the codes over GF(q), and the shortening upper bound for LDPC codes is made. The new bound is shown to lie under the Gilbert–Varshamov bound at high rates.     

On <Emphasis Type="Italic">m</Emphasis>-Near-Resolvable Block Designs and <Emphasis Type="Italic">q</Emphasis>-ary Constant-Weight Codes

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs.     

List decoding for a multiple access hyperchannel

We obtain bounds on the rate of (optimal) list-decoding codes with a fixed list size L ≥ 1 for a q-ary multiple access hyperchannel (MAHC) with s ≥ 2 inputs and one output. By definition, an output signal of this channel is the set of symbols of a q-ary alphabet that occur in at least one of the s input signals. For example, in the case of a binary MAHC, where q = 2, an output signal takes values in the ternary alphabet {0, 1, {0, 1}}; namely, it equals 0 (1) if all the s input signals are 0 (1) and equals {0, 1} otherwise. Previously, upper and lower bounds on the code rate for a q-ary MAHC were studied for L ≥ 1 and q = 2, and also for the nonbinary case q ≥ 3 for L = 1 only, i.e., for so-called frameproof codes. Constructing upper and lower bounds on the rate for the general case of L ≥ 1 and q ≥ 2 in the present paper is based on a substantial development of methods that we designed earlier for the classical binary disjunctive multiple access channel.     

Pseudo-Randomness of Certain Sequences of <Emphasis Type="Italic">k</Emphasis> Symbols with Length <Emphasis Type="Italic">pq</Emphasis>

The theory of finite pseudo-random binary sequences was built by C. Mauduit and A. Sárközy and later extended to sequences of k symbols (or k-ary sequences). Certain constructions of pseudo-random sequences of k symbols were presented over finite fields in the literature. In this paper, two families of sequences of k symbols are constructed by using the integers modulo pq for distinct odd primes p and q. The upper bounds on the well-distribution measure and the correlation measure of the families sequences are presented in terms of certain character sums over modulo pq residue class rings. And low bounds on the linear complexity profile are also estimated.     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

A novel weighting scheme for random k-SAT关于随机 k-SAT 的新加权方法

Consider a random k-conjunctive normal form F_k(n, rn) with n variables and rn clauses. We prove that if the probability that the formula F_k(n, rn) is satisfiable tends to 0 as n→∞, then r ? 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.     

List decoding of the first-order binary Reed-Muller codes

A list decoding algorithm is designed for the first-order binary Reed-Muller codes of length n that reconstructs all codewords located within the ball of radius n/2(1 ? ?) about the received vector and has the complexity of O(n ln²(min{? ^?2, n})) binary operations.     

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α _k times OPT, where α _k is an increasing function of k, with \(\lim _{k\to \infty } \alpha _{k} = 3\). Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5.