pseudo-random array is a two-dimensional array in which eachn1×n2nonzero matrix is contained exactly once as a window in the array. The pseudo-random arrays we consider have many desirable properties in addition, such as the shift-and-add-property, i.e., the addition of the array to any of its nontrivial shifts is another nontrivial shift of the array. A pseudorandom array code is a linear code ofr1×r2arrays in which eachn1×n2nonzero matrix is contained exactly once as a window in one of the arrays. In this paper, new parameters for pseudo-random arrays are presented, and their construction is generalized to pseudo-random array codes. Our constructions of pseudo-random array codes are based on the folding of sequences. Two techniques to verify whether an array or a set of arrays constructed by folding is a pseudo-random array or a pseudo-random array code, respectively, are presented. These verification techniques can also be used for VLSI testing.

MDS codes with determined Hermitian hull dimensions have attracted significant attention for their application in quantum error correction. From an MDS code over Fq2with fixed Hermitian hull dimension ℓ, whereqis a prime power larger than 2, one can obtain an MDS code with any smaller ℓ′-dimensional Hermitian hull for 0 ≤ ℓ′ ≤ ℓ. Then it is natural to consider the problem of determining the maximum Hermitian hull dimension, denoted byLq(n, k), among all MDS codes with the same lengthnand dimensionkover Fq2. Some constructions of Hermitian self-orthogonal generalized Reed-Solomon (GRS) codes had been proposed, which addressed this problem for certain parameter regimes. However, it is still unknown for many cases, in particular fork≥q+ 1. In this paper, we study the Hermitian hulls of a class of codes which generalizes GRS codes, called twisted generalized Reed-Solomon (TGRS) codes. TGRS codes contain MDS subclasses that are not linearly equivalent to GRS codes (called non-GRS codes). We give a bound on the Hermitian hull dimensions of certain TGRS codes of general twists. In addition, we derive a lower bound onLq(n, k) forn|q2− 1 and 1 ≤k≤n, which generalizes and improves some previous results. For some parameter regimes wheren≥q+ 1 andk≥q+ 1, we prove thatLq(n, k) ≥k/2 and explicitly construct [n, k]q2MDS codes whose Hermitian hulls have dimension at leastk/2. This result solves partially an open problem pointed out in the literature. The constructed MDS codes arise from either GRS or non-GRS TGRS codes. Furthermore, some sufficient conditions for TGRS codes with general twists to be Hermitian self-orthogonal are given, and Hermitian self-orthogonal non-GRS MDS codes are constructed. Based on our constructions, we provide several families of MDS entanglement-assisted quantum error-correcting codes.

We consider a multi-armed bandit setting with finitely many arms, in which each arm yields an $M$-dimensional vector reward upon selection. We assume that the reward of each dimension (a.k.a. {\em objective}) is generated independently of the others. The best arm of any given objective is the arm with the largest component of mean corresponding to the objective. The end goal is to identify the best arm of {\em every} objective in the shortest (expected) time subject to an upper bound on the probability of error (i.e., fixed-confidence regime). We establish a problem-dependent lower bound on the limiting growth rate of the expected stopping time, in the limit of vanishing error probabilities. This lower bound, we show, is characterised by a max-min optimisation problem that is computationally expensive to solve at each time step. We propose an algorithm that uses the novel idea of {\em surrogate proportions} to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step. We demonstrate theoretically that our algorithm is asymptotically optimal. In addition, we provide extensive empirical studies to substantiate the efficiency of our algorithm. While existing works on pure exploration with multi-objective multi-armed bandits predominantly focus on {\em Pareto front identification}, our work fills the gap in the literature by conducting a formal investigation of the multi-objective best arm identification problem.

Pseudo-random arrays are the two-dimensional analog of M-sequences. Pseudo-random array codes are the twodimensional analog of sequences generated by a product of irreducible polynomials with the same exponent. The union of the arrays in such a code has the window property and the shift-and-add property, implying that these codes are linear. The folding technique is the most basic one for forming such arrays and codes. A new criterion for generating pseudo-random arrays based on folding is given. This new criterion yields pseudo-random arrays with new parameters. A general construction for such array codes is given. It appears that the arrays generated in this construction can be constructed by folding the nonzero sequences generated by a product of irreducible polynomials of the same degree and the same exponent. Two hierarchies of the pseudo-random array codes are provided. In one hierarchy codewords of one code with smaller windows are contained in codewords of another code which stands above him in the hierarchy. The second hierarchy is a partition of the pseudo-random array codes generated by folding into classes based on the polynomial types which participate in their construction.

Run length limited (RLL) sequences and codes have been studied extensively in coding theory for a long time. Several kinds of weight constrained RLL codes have gained attentions recently owing to their applications, especially in DNA-based data storage. In this work, we revisit the old problem of constant weight RLL codes and provide new efficient encoding/decoding algorithms of these optimal codes. In particular, we rank/unrank all constant weight RLL sequences in a certain order, called$d$-Gray order, where the Hamming distance between two consecutive sequences in the list is at most$d$. The list of all constant weight RLL sequences is called a constant weight RLL$d$-Gray code.

The coded trace reconstruction problem, where multiple noisy copies (traces) of an original message are used for recovery, has garnered significant attention. We investigate this problem under the specific constraints that the messages are permutations of length n and the errors are deletions. Our primary focus is the burst deletion model: given M > 1 traces, each resulting from the original permutation by deleting a single burst of at most t symbols. We present an explicit construction of a permutation code capable of uniquely recovering the original permutation from M = 2 distinct traces, each affected by a burst deletion of size up to t. Notably, this code achieves recovery with only constant redundancy (independent of n). Additionally, we explore a different scenario involving two arbitrary deletions per trace. For this model, we demonstrate that existing 1deletion correcting permutation codes are sufficient to guarantee unique recovery of the original permutation, provided at least M =5 distinct traces are available.

Permutation codes are extensively studied because of applications such as frequency-shift keying modulation for power line communication (PLC). In PLC channels with synchronization issues, the error propagation due to insertion/deletion errors blurs the boundaries of codewords, thus making the communication unreliable. Prior studies on regaining synchronization focused on scenarios where noise and errors distort permutation codewords that were consecutively transmitted. In this paper, we consider the case where the channel output is a two-dimensional array, which is a concatenation of distorted permutation matrices of the transmitted codewords. Firstly, we propose algorithms to achieve two tasks. The first is to predict the distance of subarrays of the channel output from all codewords, and the second is to predict the original transmitted codewords given the output matrices corresponding to these codewords. Secondly, we apply these algorithms in an extended version of Viterbi-like algorithms proposed by Cheng et al. to decode the outputs received from transmissions over PLC channels with synchronization issues. Finally, our simulations demonstrate that block error rates were significantly improved over implementations lacking neural network-based algorithms, regardless of noise and error types.

Abstract An ( n , R )-covering sequence is a cyclic sequence whose consecutive n -tuples form a code of length n and covering radius R . Using several construction methods improvements of the upper bounds on the length of such sequences for $$n \le 20$$ n ≤ 20 and $$1 \le R \le 3$$ 1 ≤ R ≤ 3 , are obtained. The definition is generalized in two directions. An ( n , m , R )-covering sequence code is a set of cyclic sequences of length m whose consecutive n -tuples form a code of length n and covering radius R . The definition is also generalized to arrays in which the $$m \times n$$ m × n sub-matrices form a covering code with covering radius R . We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.

Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of$\epsilon $in$\mathrm {poly}(1/\epsilon, \text {input dimension})$time, compared to the$\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.

Permutation codes in the Ulam metric, which can correct multiple deletions, have been investigated extensively recently. In this work, we are interested in the maximum size of permutation codes in the Ulam metric and aim to design permutation codes that can correct multiple deletions with efficient decoding algorithms. We first present an improvement on the Gilbert–Varshamov bound of the maximum size of these permutation codes by analyzing the independence number of the auxiliary graph. The idea is widely used in various cases and our contribution in this section is to enumerate the number of triangles in the auxiliary graph and show that it is small enough. Next, we design permutation codes correcting multiple deletions with a decoding algorithm. In particular, the constructed permutation codes can correcttdeletions with at most (3t− 1) log(n+ 1) +o(logn) bits of redundancy wherenis the length of the code. Our construction is based on a new mapping that yields a new connection between permutation codes in the Hamming metric and permutation codes in various metrics. Furthermore, we construct permutation codes that correct multiple bursts of deletions using this new mapping. Finally, we extend the new mapping for multi-permutations and construct the best-known multi-permutation codes in the Ulam metric.

With the growth of 3D sensing technology, the deep learning system for 3D point clouds has become increasingly important, especially in applications such as autonomous vehicles where safety is a primary concern. However, there are growing concerns about the reliability of these systems when they encounter noisy point clouds, either occurring naturally or introduced with malicious intent. This paper highlights the challenges of point cloud classification posed by various forms of noise, from simple background noise to malicious adversarial/backdoor attacks that can intentionally skew model predictions. While there's an urgent need for optimized point cloud denoising, current point outlier removal approaches, an essential step for denoising, rely heavily on handcrafted strategies and are not adapted for higher-level tasks, such as classification. To address this issue, we introduce an innovative point outlier cleansing method that harnesses the power of downstream classification models. Using gradient-based attribution analysis, we define a novel concept: point risk. Drawing inspiration from tail risk minimization in finance, we recast the outlier removal process as an optimization problem, named PointCVaR. Extensive experiments show that our proposed technique not only robustly filters diverse point cloud outliers but also consistently and significantly enhances existing robust methods for point cloud classification. A notable feature of our approach is its effectiveness in defending against the latest threat of backdoor attacks in point clouds.

Atomic commit protocols (ACPs) are crucial for ensuring transaction atomicity in distributed transaction processing. However, existing ACPs, designed specifically for fixed failure conditions, cannot work efficiently in modern environments, where failures such as node crashes and connection delays can happen anytime due to the use of commodity nodes and networks. In this paper, we propose FC, a novel and practical ACP that can adapt to changes in failure conditions. In essence, FC includes three dedicated protocols, which are specifically designed for three different failure conditions: (i) failure-free: no failure occurs, (ii) crash-failure: nodes might crash but there is no delayed connection, or (iii) network-failure: both crashed nodes and delayed connection can occur. During its operation, FC can monitor if any failure occurs and dynamically switch to the most suitable protocol, using a protocol selector, whose parameters are fine-tuned by reinforcement learning. Consequently, FC improves transaction performance and robustly ensures fault tolerance when crash failures and network failures occur. We conduct extensive experiments to evaluate FC with both YCSB and TPC-C benchmarks. The experimental results show that FC achieves up to 2.88x higher throughput and 3.76x lower latency than state-of-the-art ACPs, and its sustainable performance when integrated with two popular databases, namely MongoDB and PostgreSQL.

We study best arm identification (BAI) in linear bandits in the fixed-budget regime under differential privacy constraints, when the arm rewards are supported on the unit interval. Given a finite budget $T$ and a privacy parameter $\varepsilon>0$, the goal is to minimise the error probability in finding the arm with the largest mean after $T$ sampling rounds, subject to the constraint that the policy of the decision maker satisfies a certain {\em $\varepsilon$-differential privacy} ($\varepsilon$-DP) constraint. We construct a policy satisfying the $\varepsilon$-DP constraint (called {\sc DP-BAI}), based on the principle of {\em maximum absolute determinants}, and derive an upper bound on its error probability. Furthermore, we derive a minimax lower bound on the error probability, and demonstrate that the lower and the upper bounds decay exponentially in $T$, with exponents in the two bounds matching order-wise in (a) the sub-optimality gaps of the arms, (b) $\varepsilon$, and (c) the problem complexity that is expressible as the sum of two terms, one characterising the complexity of standard fixed-budget BAI (without privacy constraints), and the other accounting for the $\varepsilon$-DP constraint. Additionally, we present some auxiliary results that contribute to the derivation of the lower bound on the error probability. These results, we posit, may be of independent interest and could prove instrumental in proving lower bounds on error probabilities in several other bandit problems. Whereas prior works provide results for BAI in the fixed-budget regime without privacy constraints or in the fixed-confidence regime with privacy constraints, our work fills the gap in the literature by providing the results for BAI in the fixed-budget regime under the $\varepsilon$-DP constraint.

Given$d$defective items in a population of$n$items with$d\ll n$, in threshold group testing without gap, the outcome of a test on a subset of items is positive if the subset has at least$u$defective items and negative otherwise, where$1 \leq u \leq d$. The basic goal of threshold group testing is to quickly identify the defective items via a small number of tests. In non-adaptive design, all tests are designed indepen-dently and can be performed in parallel. The decoding time in the non-adaptive state-of-the-art work is a polynomial of$(d/u)^{u}(d/(d-u))^{d-u}, d$, and$\log n$. In this work, we present a novel design that significantly reduces the number of tests and the decoding time to polynomials of$\min\{u^{u},\ (d-u)^{d-u}\}, d$, and$\log n$. In particular, when$u$is a constant, the number of tests and the decoding time are$O(d^{3}(\log^{2}n)\log(n/d))$and$O(d^{3}(\log^{A}n)\log(n/d)+d^{2}(\log n)\log^{3}(n/d))$, respectively. For a special case when$u=2$, with non-adaptive design, the number of tests and the decoding time are$O(d^{3}(\log n)\log(n/d))$and$O(d^{2}(\text{log} n+\log^{2}(n/d)))$, respectively. Moreover, with 2-stage design, the number of tests and the decoding time are$O(d^{2}\log^{2}(n/d))$. The full version is available at [1].

To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost.

An$(m, n, R)-\mathbf{de}$Bruijn covering array (dBCA) is a doubly periodic$M\times N$array over an alphabet of size$q$such that the set of all its$m\times n$windows form a covering code with radius$R$. An upper bound of the smallest array area of an$(m, n, R)-\mathbf{dBCA}$is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and$(m, n, R)-\mathbf{dBCAs}$with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

In DNA-based data storage, sequencing the stored DNA is essential in reading the stored data. Nanopore sequencing, an emerging sequencing technology, has attracted a lot of attention recently owing to their various advantages, in particular, it is portable, scalable, automated and rapid. However, several kinds of errors, including inter-symbol interference, noisy measurement, backtracking, and skipping, reduce the accuracy of the technology. Several coding schemes have been proposed recently to deal with various kinds of error sources, especially inter-symbol interference and noisy measurement. In this work, we focus on backtracking and skipping errors and aim to design a good coding scheme to combat these errors. We first note that backtracking and skipping errors can be modelled as synchronization errors, including duplication and deletion errors. Next, we propose new families of codes to locate and correct all synchronization errors caused by backtracking and skipping. The proposed codes are constrained codes avoiding prescribed set of patterns. Then, we focus on studying these constrained codes. In particular, we present a method to compute their maximal asymptotic rates. For illustration, we use experimental data available online to compute the numerical results for maximal asymptotic rates of these codes.

In this paper, we study the asymptotic nonnegative rank of matrices, which characterizes the asymptotic growth of the nonnegative rank of fixed nonnegative matrices under the Kronecker product. This quantity is important since it governs several notions in information theory such as the so-called exact Renyi common information and the amortized communication complexity. By using the theory of asymptotic spectra of V. Strassen (J. Reine Angew. Math. 1988), we define formally the asymptotic spectrum of nonnegative matrices and give a dual characterization of the asymptotic nonnegative rank. Comple-mentary to the nonnegative rank, we introduce the notion of the sub rank of a nonnegative matrix and show that it is exactly equal to the size of the maximum induced matching of the bipartite graph defined on the support of the matrix (therefore, independent of the value of entries). Finally, we show that two matrix parameters, namely rank and fractional cover number, belong to the asymptotic spectrum of nonnegative matrices.

Window Weight Limited (WWL) strings and codes have been studied recently owing to their various applications, including DNA based storage and energy-harvesting. In this work, we proposed to study a new coding scheme, called WWL Gray code. This is a list of WWL strings in Gray order, that is, the Hamming distance of two consecutive strings in the list is one. We are the first to investigate the WWL Gray codes with efficient rankinglunranking algorithms. We show that the WWL Gray codes are useful in designing robust positioning sequences. Note that the robust positioning sequences have attracted a lot of attentions recently owing to their numerous applications, including quantum communications and robot localization. In this work, using the WWL Gray codes, we obtain robust positioning sequences with less redundancy compared to the best known results.

Sum-rank-metric codes have attracted lots of attention due to their numerous applications, including muti-shot linear network coding, space-time coding, and distributed storage systems. In this paper, we focus on constructing linear sum-rank-metric codes achieving Singleton bound, which are called maximum sum-rank distance (MSRD) codes. This family of codes is the analogue of maximum distance separable (MDS) codes in Hamming metric. We propose two constructions of linear MSRD codes with various matrix sizes. Each of them yields new MSRD codes with different parameter regimes, and one of them generalizes some recent results of Byrne et al. (2021) and Chen (2023). The block lengths and the matrix block sizes of our codes are not restricted to the sizes of the finite field. Our technique is mainly based on rank metric codes and their sub-codes of different minimum rank distances.

Our main goal in this work is to study permutation codes in the Levenshtein metric which can correct multiple deletions. Permutation codes in the Levenshtein metric are known to have a close relationship with those in Ulam and generalized Kendall-tau metrics. In this work, we present a new connection between different kinds of distances over two permu-tations' including Hamming, Levenshtein, Ulam, and generalized Kendall-tau distance. From this new connection and some known permutation codes in the Hamming metric, we obtain new permu-tation codes in Levenshtein, Ulam, and generalized Kendall-tau metrics with better size. In particular, we show that there exist permutation codes of length$n$for correcting$t$deletions with at most$(3t+1)\log n+o(\log n)$bits of redundancy. Furthermore, we present the construction of our permutation codes for correcting$t$deletions with a specific decoding process.

We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set$S$of linearly independent combinations of the sub-symbols of the lost symbol. When$S=\varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When$S$is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on$\vert S\vert$and not the content of$S$and construct a lower bound on the repair bandwidth of a linear repair scheme with side information$S$We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.

Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work ared-dimensional subspaces of ak-dimensional vector space over$\mathbb {F}_{q}$. Each server stores one representative for each distinct one-dimensional subspace of thek-dimensional vector space, or equivalently a distinct point of PG$(k-1,q)$. As column vectors, the associated vectors of the stored one-dimensional subspaces form the generator matrix of the$[(q^{k} -1)/(q-1),k,q^{k-1}]$simplex code over$\mathbb {F}_{q}$. Lower bounds and upper bounds on the maximum number of such recovery sets are provided. It is shown that generally, these bounds are either tight or very close to being tight.

We study best arm identification in a federated multi-armed bandit setting with a central server and multiple clients, when each client has access to asubsetof arms and each arm yields independent Gaussian observations. The goal is to identify the best arm of each client subject to an upper bound on the error probability; here, the best arm is one that has the largestaveragevalue of the means averaged across all clients having access to the arm. Our interest is in the asymptotics as the error probability vanishes. We provide an asymptotic lower bound on the growth rate of the expected stopping time of any algorithm. Furthermore, we show that for any algorithm whose upper bound on the expected stopping time matches with the lower bound up to a multiplicative constant (almost-optimalalgorithm), the ratio of any two consecutive communication time instants must beboundeda result that is of independent interest. We thereby infer that an algorithm can communicate no more sparsely than at exponential time instants in order to be almost-optimal. For the class of almost-optimal algorithms, we present the first-of-its-kind asymptotic lower bound on the expected number ofcommunication roundsuntil stoppage. We propose a novel algorithm that communicates at exponential time instants, and demonstrate that it is asymptotically almost-optimal.

While the encoder-decoder structure is widely used in the recent neural construction methods for learning to solve vehicle routing problems (VRPs), they are less effective in searching solutions due to deterministic feature embeddings and deterministic probability distributions. In this article, we propose the feature embedding refiner (FER) with a novel and generic encoder-refiner-decoder structure to boost the existing encoder-decoder structured deep models. It is model-agnostic that the encoder and the decoder can be from any pretrained neural construction method. Regarding the introduced refiner network, we design its architecture by combining the standard gated recurrent units (GRU) cell with two new layers, i.e., an accumulated graph attention (AGA) layer and a gated nonlinear (GNL) layer. The former extracts dynamic graph topological information of historical solutions stored in a diversified solution pool to generate aggregated pool embeddings that are further improved by the GRU, and the latter adaptively refines the feature embeddings from the encoder with the guidance of the improved pool embeddings. To this end, our FER allows current neural construction methods to not only iteratively refine the feature embeddings for boarder search range but also dynamically update the probability distributions for more diverse search. We apply FER to two prevailing neural construction methods including attention model (AM) and policy optimization with multiple optima (POMO) to solve the traveling salesman problem (TSP) and the capacitated VRP (CVRP). Experimental results show that our method achieves lower gaps and better generalization than the original ones and also exhibits competitive performance to the state-of-the-art neural improvement methods.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

The run length limited de Bruijn (RLLdB) sequences have been studied recently owing to their application in communication systems. In each RLLdB sequence, all length-k substrings are distinct and each substring is a run length limited sequence, where there are at most s consecutive symbol 0’s. In previous work, the maximal length RLLdB sequence was designed only for the case s = 1.In this work, we propose to study a more generalised problem of constrained de Bruijn sequence, called weight bounded run length limited de Bruijn (WRdB) sequence. In each WRdB sequence, all length-k substrings are distinct and each length-k substring satisfies both constraints: the number of consecutive symbol 0’s is at most s, and the number of symbol 1’s is at least l. We aim to design a WRdB sequence with maximal length in all cases.Firstly, we build a constrained de Bruijn graph that represents a WRdB sequence and use some properties of the graph to show an upper bound on the maximal length of the sequence. Next, using Lyndon words, we present a construction of a WRdB sequence. Finally, we compute the length of the constructed WRdB sequence and show that it has the maximal length.

In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.

In this work, we study two types of constraints on two-dimensional binary arrays. Given$p\in [{0,1}],\epsilon \in [{0,1/2}]$, we study 1) the$p$-bounded constraint: a binary vector of size$n$is said to be$p$-bounded if its weight is at most$pn$, and 2) the$\epsilon $-balanced constraint: a binary vector of size$n$is said to be$\epsilon $-balanced if its weight is within$\big [(1/2-\epsilon)n, (1/2+\epsilon)n\big]$. Such constraints are crucial in several data storage systems, those regard the information data as two-dimensional (2D) instead of one-dimensional (1D), such as the crossbar resistive memory arrays and the holographic data storage. In this work, efficient encoding/decoding algorithms are presented for binary arrays so that the weight constraint (either$p$-bounded constraint or$\epsilon $-balanced constraint) is enforced over every row and every column, regarded as 2D row-column (RC) constrained codes; or over every window (where each window refers to as a subarray consisting of consecutive rows and consecutive columns), regarded as 2D sliding-window (SW) constrained codes. While low-complexity designs have been proposed in the literature, mostly focusing on 2D RC constrained codes where$p=1/2$and$\epsilon =0$, this work provides efficient coding methods that work for both 2D RC constrained codes and 2D SW constrained codes, and more importantly, the methods are applicable for arbitrary values of$p$and$\epsilon $. Furthermore, for certain values of$p$and$\epsilon $, we show that, for sufficiently large array size, there exists linear-time encoding/decoding algorithm that incurs at most one redundant bit.

Numerous advancements in deep learning can be attributed to the access to large-scale and well-annotated datasets. However, such a dataset is prohibitively expensive in 3D computer vision due to the substantial collection cost. To alleviate this issue, we propose a cost-effective method for automatically generating a large amount of 3D objects with annotations. In particular, we synthesize objects simply by assembling multiple random primitives. These objects are thus auto-annotated with part labels originating from primitives. This allows us to perform multi-task learning by combining the supervised segmentation with unsupervised reconstruction. Considering the large overhead of learning on the generated dataset, we further propose a dataset distillation strategy to remove redundant samples regarding a target dataset. We conduct extensive experiments for the downstream tasks of 3D object classification. The results indicate that our dataset, together with multitask pretraining on its annotations, achieves the best performance compared to other commonly used datasets. Further study suggests that our strategy can improve the model performance by pretraining and fine-tuning scheme, especially for the dataset with a small scale. In addition, pretraining with the proposed dataset distillation method can save 86% of the pretraining time with negligible performance degradation. We expect that our attempt provides a new data-centric perspective for training 3D deep models.

Interactive graph search (IGS) uses human intelligence to locate the target node in hierarchy, which can be applied for image classification, product categorization and searching a database. Specifically, IGS aims to categorize an object from a given category hierarchy via several rounds of interactive queries. In each round of query, the search algorithm picks a category and receives a boolean answer on whether the object is under the chosen category. The main efficiency goal asks for the minimum number of queries to identify the correct hierarchical category for the object. In this paper, we study the average-case interactive graph search (AIGS) problem that aims to minimize the expected number of queries when the objects follow a probability distribution. We propose a greedy search policy that splits the candidate categories as evenly as possible with respect to the probability weights, which offers an approximation guarantee of$O(\log n)$for AIGS given the category hierarchy is a directed acyclic graph (DAG), where$n$is the total number of categories. Meanwhile, if the input hierarchy is a tree, we show that a constant approximation factor of$(1+\sqrt{5})/2$can be achieved. Furthermore, we present efficient implementations of the greedy policy, namely GreedyTree and GreedyDAG, that can quickly categorize the object in practice. Extensive experiments in real-world scenarios are carried out to demonstrate the superiority of our proposed methods.

We present an efficient Neural Neighborhood Search (N2S) approach for pickup and delivery problems (PDPs). In specific, we design a powerful Synthesis Attention that allows the vanilla self-attention to synthesize various types of features regarding a route solution. We also exploit two customized decoders that automatically learn to perform removal and reinsertion of a pickup-delivery node pair to tackle the precedence constraint. Additionally, a diversity enhancement scheme is leveraged to further ameliorate the performance. Our N2S is generic, and extensive experiments on two canonical PDP variants show that it can produce state-of-the-art results among existing neural methods. Moreover, it even outstrips the well-known LKH3 solver on the more constrained PDP variant. Our implementation for N2S is available online.

The main goal of group testing is to identify a small number of positive items among a large population of n items. In this work, we consider a new model of group testing in which the input items are linearly ordered, and the positives are subsets of small blocks (at unknown locations) of consecutive items over that order. When the number of blocks is at least one and at most k, and the number of items in a block is at most d, we show that there exists a deterministic and explicit design that can identify the positives with O(k2d log (n/d)) tests in O(poly(k, n/d)+kd) time. The number of tests in our proposed design is less than that of in standard combinatorial group testing by a factor of at least d/ log (kd). We also show that there exists a randomized design that can identify the positives with O(k(log (n/d)+d log k)) tests in O(k(log2(n/d)+k log k+d log k)) time with high probability.

The de Bruijn based timing and synchronization (dBTS) system has been proposed and studied recently for some channels require reliable synchronization, such as quantum communication. To avoid a long period of no-pulse in the dBTS system, we propose to study the run length limited de Bruijn sequences which not only are run length limited sequences but also can be used to locate the location of any sub-string. Such subjects are expected to have various applications and they also present some interesting theoretical questions in combinatorics, algorithms and coding theory.In this paper, we are the first to provide an explicit formula of the maximal length of the run length limited de Bruijn sequences. Besides that, using Lyndon words, we present an efficient construction of a run length limited de Bruijn sequence with the maximal length. Furthermore, we also provide a sub-linear decoding algorithm which can locate the position of an arbitrary sub-string.

An (n, d, b, k)q-robust locally positioning (RLP) sequence s is a q-ary sequence of length n where each subset of b consecutive windows of length k in s is a q-ary code of length k with minimum Hamming distance d. A set of these sequences is called an (n, d, b, k)q-robust locally positioning code. The RLP sequence is a generalization of a locally constrained de Bruijn sequence and a robust positioning sequence which have been studied recently owing to their various applications. In this work, we study the RLP sequences and codes with motivation from both practical and theoretical points of view. Firstly, these RLP sequences and codes are useful to combat a combination of substitutions and synchronization errors in the ℓ-symbol read channel. Secondly, the RLP code can be viewed as a combination of an error correcting code and a constrained code avoiding a set of patterns and as such they pose several interesting theoretical challenges in combinatorics, algorithms and coding theory. Finally, from the practical point of view, these sequences and codes have numerous applications, especially error-correction in racetrack memories.Owing to their applications in racetrack memories, we investigate (n, d, b, k)qRLP codes with small values of b and d. Numerous techniques are used to compute the maximal asymptotic rate (capacity) of these codes for given set of parameters. The numerical results are computed and tabulated. We also study these codes with large values of b and d for theoretical interests. In some cases, we can construct a code with only a single bit of redundancy.

In this work, given n,ϵ > 0, two efficient encoding (decoding) methods are presented for mapping arbitrary data to (from) n×n binary arrays in which the weight of every row and every column is within [(1/2–ϵ)n, (1/2+ϵ)n], which is referred to as the ϵ-balanced constraint. The first method combines the divide and conquer algorithm and a modification of the Knuth’s balancing technique, resulting a redundancy of Θ(n) bits. On the other hand, for sufficiently large n, the second method uses the sequence replacement technique, which costs only 1 redundant bit. The latter method reduces significantly the redundancy of the best known encoder for two-dimensional p-bounded weight constrained codes from (n + 3) bits to a single bit.

The interactive graph search (IGS) problem aims to locate an initially unknown target node leveraging human intelligence. In IGS, we can gradually find the target node by sequentially asking humans some reachability queries like "is the target node reachable from a given node x?". However, human workers may make mistakes when answering these queries. Motivated by this concern, in this paper, we study a noisy version of the IGS problem. Our objective in this problem is to minimize the query complexity while ensuring accuracy. We propose a method to select the query node such that we can push the search process as much as possible and an online method to infer which node is the target after collecting a new answer. By rigorous theoretical analysis, we show that the query complexity of our approach is near-optimal up to a constant factor. The extensive experiments on two real datasets also demonstrate the superiorities of our approach.

Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out-of-distribution instances, which are either randomly synthesized or adopted from benchmark datasets (i.e., TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.

Machine learning (ML) is an important part of modern data science applications. Data scientists today have to manage the end-to-end ML life cycle that includes both model training and model serving, the latter of which is essential, as it makes their works available to end-users. Systems of model serving require high performance, low cost, and ease of management. Cloud providers are already offering model serving choices, including managed services and self-rented servers. Recently, serverless computing, whose advantages include high elasticity and a fine-grained cost model, brings another option for model serving.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems. In this work, in order to reduce the wear out of the cells, we propose a new coding scheme, called endurance-limited memories (ELM) codes, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an$\ell $-change$t$-write ELM code is a coding scheme that allows to write$t$messages into some$n$binary cells while guaranteeing that each cell is programmed at most$\ell $times. In case$\ell =1$, these codes coincide with the well-studied write-once memory (WOM) codes. We study some models of these codes which depend upon whether the encoder knows on each write the number of times each cell was programmed, knows only the memory state, or even does not know anything. For the decoder, we consider these similar three cases. We fully characterize the capacity regions and the maximum sum-rates of three models where the encoder knows on each write the number of times each cell was programmed. In particular, it is shown that in these models the maximum sum-rate is$\log \sum _{i=0}^{\ell } {\binom{t }{ i}}$. We also study and expose the capacity regions of the models where the decoder is informed with the number of times each cell was programmed. Finally we present the most practical model where the encoder read the memory before encoding new data and the decoder has no information about the previous states of the memory.

A multiset combinatorial batch code (MCBC) over vector space consists of a set of subspaces of$\mathbb{F}_{q}^{n}$, each corresponding to a server, such that requests consisting of$t$dimensional subspaces, can be retrieved from the servers. The code is said to be regular if all the subspaces in the code have the same dimension. The aim is to find the minimum number of total storage, and also the minimum number of servers in the regular case, fixing other parameters. In this paper, we provide bounds and constructions for this new class of batch codes.

Two dimensional (2D) error correcting codes have been investigated for a long time owing to their numerous applications. Recently, 2D codes correcting row-deletions and column-deletions, also known as criss-cross deletion correcting codes, have been studied as a generalisation of one dimensional deletion correcting codes. In this work, we show that 2D deletion correcting codes are useful to correct errors in racetrack memories. With motivation from both theoretical and practical point of view, we study these 2D codes and aim to improve the previous known results. Our first main result is a construction of an optimal (1,1)-criss-cross deletion correcting code with the redundancy is at most$2n+2\log n+o(\log n)$bits. Then, we also present a construction of an asymptotic optimal$(t_{r},\ t_{c})$-criss-cross deletion correcting code with less redundancy than the best known results. Furthermore, since a 2D binary code correcting multiple row-deletions is equivalent to a I1D q-ary code correcting multiple deletions with large$q$, we also improve some previous known results on 1D q-ary code correcting multiple deletions.

Transverse-read is a novel technique to detect the number of ‘1's stored in domain wall memory, also known as racetrack memory, without shifting any domains. Motivated by this technique, we propose a novel scheme to combine transverse-read and shift-operations such that the number of shift-operations can be reduced while still achieving high capacity. We also show that this scheme is helpful to correct errors in domain wall memory. A set of valid words in this transverse-read channel is called a transverse-read code. We first present several properties of transverse-read codes and show that they are equivalent to constrained codes. Then, we compute the maximal asymptotic rate of transverse-read codes for several parameters. Next, we construct achieving capacity codes with efficient encoding/decoding algorithms. Finally, we discuss transverse-read codes which correct shift-errors in domain wall memory.

In this work, given$n, p > 0$, efficient encoding/decoding algorithms are presented for mapping arbitrary data to and from$n\times n$binary arrays in which the weight of every row and every column is at most$pn$. Such constraint, referred as$p$-bounded-weight-constraint, is crucial for reducing the parasitic currents in the crossbar resistive memory arrays, and has also been proposed for certain applications of the holographic data storage. While low-complexity designs have been proposed in the literature for only the case$p=1/2$, this work provides efficient coding methods that work for arbitrary values of$p$. The coding rate of our proposed encoder approaches the channel capacity for all$p$.

An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

Thede Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be calledlocally-constrained de Bruijn sequencesand a set of such sequences will be called alocally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the$\ell $-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs), which are replication-based batch codes. The MCBCs allow multiple users to retrieve items in parallel in a distributed storage and a fundamental objective in this study is to determine the minimum total storage given certain requirements. We formulate linear programs so that the optimal solutions provide lower bounds on the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases. Furthermore, for some parameters, we showed that these lower bounds are either tight or asymptotically tight by constructing the corresponding codes.

The linear complexity of a sequence s is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence s of length N (where N is of some given form) over a finite field Fqin O(N) symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period 2n, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires βN bit operations for a small constant β, where N is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition.

Recovery sets for vectors and subspaces are important in constructions of distributed storage system codes. These concepts are also interesting in their own right. In this paper we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets if the recovered element is a d-dimensional subspace and the elements stored are the one-dimensional subspaces of an n-dimensional vector space over GF(q). Lower and upper bounds on the number of such recovery sets are provided. It is shown that generally these bounds are either tight or very close of being tight.

Codes correcting pair-errors (substitutions) for symbol-pair read channels were introduced recently by Cassuto and Blaum(2011). In this work, we study codes correcting synchronization errors, including deletions and sticky-insertions, for symbol-pair read channels owing to their application in racetrack memory. We first investigate deletion-correcting-code in symbol-pair read channels and then construct several codes that are larger than known codes in classical deletion-channels. Finally, we examine codes correcting a combination of deletions and substitutions.

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial \(S(t,t+1,v)\) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v , there is a Steiner triple system ( S (2, 3, v )) whose largest difference in block sums is within an additive constant of the lower bound.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. In this paper, we provide constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Furthermore, we modify our constructions to correct rank errors and obtain binary positioning patterns robust to any errors of rank less than a constant number. Additionally, we construct $q$-ary robust positioning sequences robust to a large number of errors, some of which have length attaining the upper bound. Our construction of binary positioning sequences that are robust to a constant number of errors has the least known redundancy among those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying both constructions run in time cubic in sequence length or array dimension.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. Such code constructions are almost optimal to combat tandem duplications of length at most k where k ≤ 3. However, the problem of designing efficient encoder/decoder for such codes has not been investigated. In addition, the method cannot be extended to deal with the case of arbitrary k, where k ≥ 4. In this work, we study efficient encoding/decoding methods for irreducible words over general q-ary alphabet. Our methods provide the first known efficient encoder/decoder for q-ary codes correcting tandem duplications of length at most k, where k ≤ 3. In particular, we describe an (1, m)-finite state encoder and show that when m = Θ(1/ε) and ϊ = Θ(1/ε), the encoder achieves rate that is ε away from the optimal rate. We also provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder. Over the DNA alphabet (or quaternary alphabet), we also impose weight constraint on the codewords. In particular, a quaternary word is GC-balanced if exactly half of the symbols of are either C or G. Via a modification of Knuth's balancing technique, we provide an efficient method that translates quaternary messages into GC-balanced codewords and the resulting codebook is able to correct tandem duplications of length at most k, where k ≤ 3. In addition, we provide the first known construction of codes to combat tandem duplications of length at most k, where k ≥ 4. Such codes can correct duplication errors in linear-time and they are almost optimal in terms of rate.

In a bus with n wires, each wire has two states, `0' or `1', representing one bit of information. Whenever the state transitions from `0' to `1', or `1' to `0', joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an (n, t, w)-LPC code is a coding scheme over n wires that (i) avoids state transitions on the t hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most w state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of w, several constructions are presented for large LPC codes that can be encoded and decoded in time O(n log2(n/w)) along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size (n/w)w-1, which are asymptotically optimal. We then modify these LPC codes to also correct errors in time O(n3). For the case where w is proportional to n, we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are O(n3).

Write-once memory (WOM) is a storage device consisting of binary cells that can only increase their levels. A t-write WOM code is a coding scheme that makes it possible to write t times to a WOM without decreasing the levels of any of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory during the t writes and the number of cells. It is known that the maximum possible sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound, both by information-theoretic arguments and through explicit constructions. While existing constructions of WOM codes are targeted at the sum-rate, we consider here two more figures of merit. The first one is the complexity of the encoding and decoding maps. The second figure of merit is the convergence rate, defined as the minimum code length n(δ) required to reach a point that is δ-close to the capacity region. One of our main results in this paper is a capacity-achieving construction of two-write WOM codes which has polynomial encoding/decoding complexity while the block length n(δ) required to be δ-close to capacity is significantly smaller than existing constructions. Using these two-write WOM codes, we then obtain three-write WOM codes that approach a sum-rate of 1.809 at relatively short block lengths. We also provide several explicit constructions of finite length three-write WOM codes; in particular, we achieve a sum-rate of 1.716 by using only 93 cells. Finally, we modify our two-write WOM codes to construct ε-error WOM codes of high rates and small probability of failure.

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length n, minimum distance d with (d + 1) log4n + O(1) redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing.

Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

A sequence s = (s1,⋯,sn) is called a (b, h)-constrained de Bruijn sequence if all substrings of length h starting within b consecutive positions are distinct. A set of (b, h)-constrained de Bruijn sequences is called a (b, h)-constrained de Bruijn code. A (b, h)-constrained de Bruijn sequence was constructed and used as a component of a code correcting multiple limited-shift-errors in racetrack memories. In this work, we show that a (b, h)-constrained de Bruijn code can correct deletions and sticky-insertions and also can determine the locations of these errors in an ℓ-symbol read channel. We also show that it is possible to use sequences from a (b, h)-constrained de Bruijn code to construct a code correcting shift-errors in racetrack memories. As a consequence, we improve the rates on previous known codes.It is shown in this work that a (b, h)-constrained de Bruijn code is a constrained code avoiding a set of specific patterns. Finally, we present some techniques to compute the maximum asymptotic rate and find some efficient encoding/decoding algorithms for (b, h)-constrained de Bruijn codes.

The class of multiset combinatorial batch codes (MCBCs) was introduced by Zhang et al. (2018) as a generalization of combinatorial batch codes (CBCs). MCBCs allow multiple users to retrieve items in parallel in a distributed storage system and a fundamental objective in this study is to determine the minimum total storage given certain requirements.We formulate an integer linear programming problem so that its optimal solution provides a lower bound of the total storage of MCBCs. Borrowing techniques from linear programming, we improve known lower bounds in some cases and also, determine the exact values for some parameters.

An indel refers to a single insertion or deletion, while an edit refers to either a single insertion, deletion or substitution. We investigate codes that combat either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with 2⌈log n⌉ + 2 redundant bits, while the other corrects a single indel with ⌈log n⌉ + 2 redundant bits. The latter encoder reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, exactly half of the symbols of a GC-balanced word are either C or G. Via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single edit. The redundancy of our encoder is 3⌈log n⌉ + 2 bits and this is the first known construction of a GC-balanced code that corrects a single edit.

In this work, we propose and study a new class of non-binary rewriting codes, called write ℓ-step-up memories (WℓM) codes. From an information-theoretic point of view, this coding scheme is a generalization of non-binary write-once memories (WOM) codes. From a practical point of view, this coding scheme can be used not only to increase the lifetime of flash memories but also mitigate their over-shooting problem. We first provide an exact formula for the capacity region and the maximum sum-rate of WℓM codes. Lastly, we present several explicit constructions of high-rate WℓM codes with efficient encoding/decoding algorithms.

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length n, minimum distance d with (d + 1) log4n + O(1) redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth's balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes.

Private Information Retrieval (PIR) array codes were introduced by Fazeli et al. (2015) to reduce the storage overhead in designing PIR protocols. Blackburn and Etzion (2017) introduced the (virtual server) rate to quantify the storage overhead of the codes, and when s > 2 (here, 1/s is the proportion of the database storing in one server), they gave a general construction of PIR array codes with the highest rate known so far. In this paper, we generalize their construction and reduce the number of servers, while maintaining the rate. In order to give PIR array codes with significantly fewer servers, we also construct classes of codes with a smaller rate s/2s-1.

Non-volatile resistive memories, such as phase change memories and resistive random access memories, have attracted significant attention recently due to their scalability, speed, and rewritability. However, in order to use these memories in large-scale memory and storage systems, the limited endurance deficiency of these memories must be addressed. In a recent paper, we proposed a new coding scheme, called endurance-limited memories (ELM) codes, which increases the endurance of these memories by limiting the number of cell programming operations. Namely, an l-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that the number of times each cell is programmed is at most l. There are several models of these codes which depend upon the information that is available to the encoder and the decoder before each write. This information can be one of the following three options: 1. the number of times each cell has been programmed, 2. only the memory state before programming, or 3. no information is available on the cells' state or previous writes. In this paper, we study the models in which the decoder knows on each write the number of times each cell has been programmed before the last write, while for the encoder we consider the aforementioned three possibilities.

A robust positioning pattern is a large array that allows a mobile device to locate its position by reading a possibly corrupted small window around it. This paper provides constructions of binary positioning patterns, equipped with efficient locating algorithms, that are robust to a constant number of errors and have redundancy within a constant factor of optimality. Our construction of binary robust positioning sequences has the least known redundancy amongst those explicit constructions with efficient locating algorithms. On the other hand, for binary robust positioning arrays, our construction is the first explicit construction whose redundancy is within a constant factor of optimality. The locating algorithms accompanying our constructions run in time cubic in sequence length or array dimensions.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes, group divisible codes, and multiply constant-weight codes. We achieve this via an application of the theory of decomposition of edge-colored digraphs.

Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ⩽-confusable if there exists a sequence of tandem duplications for each word, where each duplication is of length at most k , such that the resulting two words after duplications are equal. For k =3, we demonstrate that the problem of deciding whether two words is ⩽3-confusable is linear-time solvable through a characterisation that can be checked efficiently. Combining with previous results, the decision problem is linear-time solvable for k ⩽ 3. We conjecture that this problem is undecidable for k > 3. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to 20, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30.

We investigate constant-composition constrained codes for the mitigation of intercell interference for multilevel cell flash memories with a dynamic threshold scheme. The first explicit formula for the maximum size of a q-ary F-avoiding code with a given composition and certain families of substrings F is presented. In addition, we provide methods to determine the asymptotic rate for F-avoiding codes with any composition ratio and to find the optimal composition ratio that maximizes the asymptotic rate. We also give the first efficient encoder/decoder for these q-ary constant-composition codes achieving the channel capacity, for all q values.

As a fundamental problem in social influence propagation analysis, learning influence parameters has been extensively investigated. Most of the existing methods are proposed to estimate the propagation probability for each edge in social networks. However, they cannot effectively learn propagation parameters of all edges due to data sparsity, especially for the edges without sufficient observed propagation. Different from the conventional methods, we introduce a novel social influence embedding problem, which is to learn parameters for nodes rather than edges. Nodes are represented as vectors in a low-dimensional space, and thus social influence information can be reflected by these vectors. We develop a new model Inf2vec, which combines both the local influence neighborhood and global user similarity to learn the representations. We conduct extensive experiments on two real-world datasets, and the results indicate that Inf2vec significantly outperforms state-of-the-art baseline algorithms.

Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. We study efficient encoding/decoding methods for irreducible words. First, we describe an (ℓ, m) -finite state encoder and show that when m=Θ(1/ε) and ℓ = Θ(1/ε), the encoder has rate that is ε away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, were introduced recently. An (n,t,w)-LPC code is a coding scheme over n wires that (A) avoids state transitions on the t hottest wires (cooling), and (B) limit the number of transitions to w in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when w is fixed, we construct LPC codes of size (n/w)w-1and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes.

In this work, we study limited-shift errors in racetrack memories and propose several schemes to combat these errors. There are two kinds of shift errors, namely under-shift errors, that can be modeled as sticky-insertions and limited-over-shift errors, that can be modeled as bursts of deletions of limited length. One approach to tackle the problem is to use deletion/sticky-insertion-correcting codes. Using this approach, we present a new family of asymptotically optimal codes that correct multiple bursts of deletions of limited length and any number of sticky insertions. We then study another approach that takes advantage of the special features of racetrack memories and the ability to add extra heads for redundancy. Here, we propose how to place the extra heads and construct codes to correct these shift errors.

Resistive memories, such as phase change memories and resistive random access memories have attracted significant attention in recent years due to their better scalability, speed, rewritability, and yet non-volatility. However, their limited endurance is still a major drawback that has to be improved before they can be widely adapted in large-scale systems.In this work, in order to reduce the wearout of the cells, we propose a new coding scheme, called Endurance-Limited Memories (ELM) code, that increases the endurance of these memories by limiting the number of cell programming operations. Namely, an ℓ-change t-write ELM code is a coding scheme that allows to write t messages into some n binary cells while guaranteeing that each cell is programmed at most ℓ times. In case ℓ = 1 then these codes coincide with the well-studied write-once memory (WOM) codes. We study four models of these codes which depend upon whether the encoder knows, on each write, the number of times each cell was programmed or only knows its state. For the decoder, we consider two cases which depend upon whether the decoder knows the previous state of the memory or not. For two of these models we fully characterize the capacity regions and present partial results for another model. Although only one of the four models is suitable for resistive memories, we consider all four in order to carry out a complete information-theory study of endurance-limited codes.

In this work, we study a special case of the reconstruction problem in order to combat position errors in racetrack memories. In these memories, the information is stored in magnetic cells that can be sensed by shifting them under read heads. However, since this shifting operation is not error free, recent work has been dedicated towards correcting these so-called position errors, which manifest themselves as deletions and sticky insertions. A deletion is the event where the cells are over-shifted, and a sticky insertion occurs when the cells are not shifted.We first present a code construction that uses two heads to correct two deletions with at most log2(log2n) +4 redundant bits. This result improves upon a recent one that requires roughly log2n redundant bits. We then extend this construction to correct d deletions using d heads with at most log2(log2n) +c redundant bits. Lastly, we extend our results and derive codes for the classical reconstruction problem by Levenshtein over the insertion/deletion channel.

High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use n > k wires to encode a given k-bit bus. One of our goals herein is to determine the minimum possible number of wires n needed to encode k bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that n = k+t +1 suffices to cool the t hottest wires, and this is the best possibility. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

The class of geometric orthogonal codes (GOCs) was introduced by Doty and Winslow (2016) for more robust macrobonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters has never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

Racetrack memory is a new technology, which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape, which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this paper, we design codes, which combat shift errors in racetrack memory, called position errors, namely, shifting the domains is not an error-free operation and the domains may be over shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. This setup is a special case of the reconstruction problem studied by Levenshtein, however, in our case, the position errors from different heads are correlated. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions. In particular, under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d+1 heads if the heads are well separated. Similar results are provided for burst of deletions, sticky insertions, and combinations of both deletions and sticky insertions.

The Johnson-type upper bound on the maximum size of a code of length n, distance d = 2w - 1, and constant n composition w̅ is [n/w1] the largest component of w̅. Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let Nccc(w) be the smallest such length. The determination of Nccc(w̅) is trivial for binary codes. This paper provides a lower bound on Nccc(w̅), which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by the refining method, we determine the values of Nccc(w̅), for all q-ary constant-composition codes, provided that 3w1≥ w with finite possible exceptions.

Codes that can correct up to t symmetric errors and detect all unidirectional errors, known as t-EC-AUED codes, are studied in this paper. Given positive integers q, a, and t, let nq(a, t + 1) denote the length of the shortest q-ary t-EC-AUED code of size a. We introduce combinatorial constructions for q-ary t-EC-AUED codes via one-factorizations of complete graphs, and concatenation of MDS codes and codes from resolvable set systems. Consequently, we determine the exact values of nq(a, t + 1) for several new infinite families of q, a, and t.

With the increasing popularity of location-aware social media applications, Point-of-Interest (POI) recommendation has recently been extensively studied. However, most of the existing studies explore from the users' perspective, namely recommending POIs for users. In contrast, we consider a new research problem of predicting users who will visit a given POI in a given future period. The challenge of the problem lies in the difficulty to effectively learn POI sequential transition and user preference, and integrate them for prediction. In this work, we propose a new latent representation model POI2Vec that is able to incorporate the geographical influence, which has been shown to be very important in modeling user mobility behavior. Note that existing representation models fail to incorporate the geographical influence. We further propose a method to jointly model the user preference and POI sequential transition influence for predicting potential visitors for a given POI. We conduct experiments on 2 real-world datasets to demonstrate the superiority of our proposed approach over the state-of-the-art algorithms for both next POI prediction and future user prediction.

High temperatures have dramatic negative effects on interconnect performance. Numerous techniques have been proposed to reduce the power dissipation of on-chip buses but they fall short of fully addressing the thermal challenges posed by high-performance interconnects. We introduce new efficient coding schemes that directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. At the same time, we reduce the average power consumption by ensuring that the total number of state transitions on all the wires is bounded. Our solutions call for redundancy: we use n > k wires to encode a given k-bit bus. Therefore, it is important to determine the minimum possible number of wires n needed to encode k bits while satisfying the desired properties. We provide full analysis in each case, and show that the number of additional wires required to cool the t hottest wires is negligible when k is large. Moreover, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

The class of geometric orthogonal codes (GOCs) were introduced by Doty and Winslow (2016) for more robust macro-bonding in DNA origami. They observed that GOCs are closely related to optical orthogonal codes (OOCs). It is possible for GOCs to have size greater than OOCs of corresponding parameters due to slightly more relaxed constraints on correlations. However, the existence of GOCs exceeding the size of optimal OOCs of corresponding parameters have never been demonstrated. This paper gives the first infinite family of GOCs of size greater than optimal OOCs.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory has a tape-like structure which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. Each head outputs a noisy version of the stored data and the multiple outputs are combined in order to reconstruct the data. Under this paradigm, we will show that it is possible to correct, with at most a single bit of redundancy, d deletions with d + 1 heads if the heads are well-separated. Similar results are provided for burst of deletions, sticky insertions and combinations of both deletions and sticky insertions.

Write-once memory (WOM) is a storage device consisting of binary cells which can only increase their levels. A t-write WOM code is a coding scheme which allows to write t times to the WOM without decreasing the levels of the cells. The sum-rate of a WOM code is the ratio between the total number of bits written to the memory and the number of cells. It is known that the maximum sum-rate of a t-write WOM code is log(t + 1). This is also an achievable upper bound both by information theory arguments and explicit WOM code constructions. While existing constructions of WOM codes were targeted to increase the sum-rate, we consider here two more figures of merit in evaluating the constructions. The first one is the complexity of the encoding and decoding maps of the code. The second one is called the convergence rate, and is defined to be the minimum code length n(ε) in order to reach e close to a point in the capacity region. One of our main results in the paper is a specific capacity achieving construction for two-write WOM codes which has polynomial complexity and relatively short block length to be ε close to the capacity. Using these two-write WOM codes, we obtain three-write WOM codes that approach sum-rate 1.809 with relatively short block lengths. Finally, we provide another construction of three-write WOM that achieves sum-rate 1.71 by using only 100 cells.

We construct permutation codes capable of correcting bursts of stable deletions. For correcting a single burst of exactly s stable deletions, our code has size sn!/((2s)!n)2, while the upper bound n!/s!(n - s + 1). We also construct permutation codes for the cases of single burst of up to s stable deletions, and up to b bursts of at most s stable deletions each.

Racetrack memory is a new technology which utilizes magnetic domains along a nanoscopic wire in order to obtain extremely high storage density. In racetrack memory, each magnetic domain can store a single bit of information, which can be sensed by a reading port (head). The memory is structured like a tape which supports a shift operation that moves the domains to be read sequentially by the head. In order to increase the memory's speed, prior work studied how to minimize the latency of the shift operation, while the no less important reliability of this operation has received only a little attention. In this work we continue our recent study and design codes which combat shift errors in racetrack memory, called position errors. Namely, shifting the domains is not an error-free operation and the domains may be over-shifted or are not shifted, which can be modeled as deletions and sticky insertions. While it is possible to use conventional deletion and insertion-correcting codes, we tackle this problem with the special structure of racetrack memory, where the domains can be read by multiple heads. We will show how to take advantage of this special feature of racetrack memories in order to construct codes correcting deletions and sticky insertions.

Multiply constant-weight codes (MCWCs) have been recently studied to improve the reliability of certain physically unclonable function response. In this paper, we give combinatorial constructions for the MCWCs, which yield several new infinite families of optimal MCWCs. Furthermore, we demonstrate that the Johnson-type upper bounds of the MCWCs are asymptotically tight for fixed Hamming weights and distances. Finally, we provide bounds and constructions of the 2-D MCWCs.

For certain families of substrings F, we provide a closed formula for the maximum size of a q-ary F-avoiding code with a given composition. In addition, we provide numerical procedures to determine the asymptotic information rate for F-avoiding codes with certain composition ratios. Using our procedures, we recover known results and compute the information rates for certain classes of F-avoiding constant-composition codes for 2 ≤ q ≤ 8. For these values of q, we find composition ratios such that the rates of F-avoiding codes with constant composition achieve the capacity of the F-avoiding channel.

We give the first known efficient encoder/decoder for q-ary constant-composition ICI-free codes achieving ICI channel capacity, for all q. Previously, the best result known is an efficient encoder/decoder for binary constant-weight ICI-free codes with more than 2% loss over ICI channel capacity.

We construct codes for the Chebyshev permutation channels whose study was initiated by Langberg et al. (2015). We establish several recursive code constructions and present efficient decoding algorithms for our codes. In particular, our constructions yield a family of binary codes of rate 0.643 when r = 1. The upper bound on the rate in this case is 2/3 and the previous highest rate is 0.609.

Multiport switches are commonly used as data processing and routing devices in computer networks. A network switch routes data packets between its multiple input and output ports. Packets from input ports are stored upon arrival in a switch fabric comprising multiple memory banks. This can lead to memory contention when distinct output ports request packets from the same memory bank, resulting in a degraded switching bandwidth. To solve this problem, switch codes are introduced by Wang et al. [1] as a tradeoff between redundancy and service. Using techniques from combinatorial design theory, we improve their result on switch codes serving any one-burst request to a denser set of parameters. New constructions for switch codes serving repetition limited request and consecutive-generation request are also given.

Perfect deletion-correcting codes of the same length over the same alphabet can have different sizes. The interesting problem of determining the possible sizes of perfect deletion-correcting codes has previously been studied. In this paper, we study the corresponding problem for burst deletion-correcting codes. We completely determine the spectrum of sizes for perfect burst deletion-correcting codes for certain classes of parameters and also construct new classes of perfect deletion-correcting codes.

We construct the first class of permutation codes that are capable of correcting a burst of up to s unstable deletions, for general s. Efficient decoding algorithms are presented to show the correctness of our constructions.

The study of Armstrong codes is motivated by the problem of understanding complexities of dependences in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance n - k + 1, and for any set of k - 1 coordinates, there exist two codewords that agree exactly there. Let f (q, k) be the maximum n for which such a code exists. In this paper, f (q, 3) = 3q -1 is determined for all q ≥ 5 with three possible exceptions. This disproves a conjecture of Sali. Furthermore, we introduce generalized Armstrong codes for branching, or (s, t)-dependences, construct several classes of optimal Armstrong codes, and establish lower bounds for the maximum length n in this more general setting.

Influence maximization problem is to find a set of seed nodes in a social network such that their influence spread is maximized under certain propagation models. A few algorithms have been proposed for solving this problem. However, they have not considered the impact of novelty decay on influence propagation, i.e., repeated exposures will have diminishing influence on users. In this paper, we consider the problem of influence maximization with novelty decay (IMND). We investigate the effect of novelty decay on influence propagation on real-life datasets and formulate the IMND problem. We further analyze the problem properties and propose an influence estimation technique. We demonstrate the performance of our algorithms on four social networks.

We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes, namely, constant-composition codes, nonbinary constant-weight codes and multiply constant-weight codes. This was achieved via an interesting application of the theory of decomposition of edge-colored digraphs.

Flash memory is a nonvolatile memory technology that suffers from errors due to charge leakage, can tolerate limited erasures, and where erasures have to be performed in large blocks. We show that using cosets of a linear code can provide correction against uniform charge leakage, and can enhance the rewritability of flash memory which leads to fewer erasures. We introduce two coset coding schemes that are generalizations of the scheme in Jacobvitz et al. (2013). For the same worst case rewrite cost, we show that coset codes can encode more information than rank modulation codes. The average case performance of coset codes is demonstrated via numerical simulations.

Binary matrix codes with restricted row and column weights are a desirable method of coded modulation for power line communication. In this work, we construct such matrix codes that are obtained as products of affine codes - cosets of binary linear codes. Additionally, the constructions have the property that they are systematic. Subsequently, we generalize our construction to irregular product of affine codes, where the component codes are affine codes of different rates.

Permutation codes under the Cayley, Kendall tau, and Ulam metrics have been studied recently due to applications in flash memories. We consider permutation codes under more general metrics. We use breakpoints in permutations to gain additional insights to distances in codes. As a result, we construct codes under these general metrics that are larger than those previously known under more restricted metrics.

Locally correctable codes have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. Recently, Guo et al. [1], discovered a family of high rate locally correctable codes by considering lifting of multivariate polynomials. In this paper, we extend their method by lifting multivariate polynomials on curves, and generalize the “decoding on curve” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound.

We introduce the class of multiply constant-weight codes to improve the reliability of certain physically unclonable function response, and extend classical coding methods to construct multiply constant-weight codes from known \(q\) -ary and constant-weight codes. We derive analogs of Johnson bounds and give constructions showing these bounds to be asymptotically tight up to a constant factor under certain conditions. We also examine the rates of multiply constant-weight codes and demonstrate that these rates are the same as those of constant-weight codes of corresponding parameters.

The min-rank of a digraph was shown to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this paper, the graphs and digraphs of near-extreme min-ranks are studied. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. In particular, it is shown that the decision problem whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time. In addition, a circuit-packing bound is revisited, and several families of digraphs, optimal with respect to this bound, whose min-ranks can be found in polynomial time, are presented.

Influence maximization is a fundamental research problem in social networks. Viral marketing, one of its applications, is to get a small number of users to adopt a product, which subsequently triggers a large cascade of further adoptions by utilizing “Word-of-Mouth” effect in social networks. Time plays an important role in the influence spread from one user to another and the time needed for a user to influence another varies. In this paper, we propose the time constrained influence maximization problem. We show that the problem is NP-hard, and prove the monotonicity and submodularity of the time constrained influence spread function. Based on this, we develop a greedy algorithm. To improve the algorithm scalability, we propose the concept of Influence Spreading Path in social networks and develop a set of new algorithms for the time constrained influence maximization problem. We further parallelize the algorithms for achieving more time savings. Additionally, we generalize the proposed algorithms for the conventional influence maximization problem without time constraints. All of the algorithms are evaluated over four public available datasets. The experimental results demonstrate the efficiency and effectiveness of the algorithms for both conventional influence maximization problem and its time constrained version.

The study of Armstrong codes is motivated by the problem of understanding complexities of dependencies in relational database systems, where attributes have bounded domains. A (q, k, n)-Armstrong code is a q-ary code of length n with minimum Hamming distance n - k + 1, and for any set of k - 1 coordinates there exist two codewords that agree exactly there. Let f(q, k) be the maximum n for which such a code exists. In this paper, f(q, 3) = 3q - 1 is determined for all q ≥ 5 with three possible exceptions. This disproves a conjecture of Sali. Further, we introduce generalized Armstrong codes for branching, or (s, t)-dependencies and construct several classes of optimal Armstrong codes in this more general setting.

Coding in a new metric space, the Enomoto-Katona space, is considered recently in connection to the study of implication structures of functional dependencies and their generalizations in relational databases. The central problem here is the determination of C(n, k, d), the size of an optimal code of length n, weight k, and distance d in the Enomoto-Katona space. The value of C(n, k, d) is known only for some congruence classes of n when (k, d) ∈ {(2, 3), (3, 5)}. In this paper, we obtain new infinite families of optimal codes in the Enomoto-Katona space. In particular, C(n, k, 2k-1) is determined for all sufficiently large n satisfying either n ≡ 1 mod k and n(n-1) ≡ 0 mod 2k2, or n ≡ 0 mod k.

Single-tone frequency shift keying (FSK) modulation with permutation codes has been found to be useful in addressing the problem of narrowband noise disturbance in power line communications. However, this modulation scheme is restrictive since the number of frequencies used must be at least as large as the number of symbols in the permutation code. In this paper, we propose the use of multitone FSK and binary matrix codes to overcome this restriction. We construct infinite families of efficiently decodable matrix codes with rates and relative distances bounded away from zero, that uses only a logarithmic number of frequencies in the length of the code. Simulation results show that our multitone modulation scheme outperform single-tone modulation schemes.

Sequential processes can encounter faults as a result of improper ordering of subsets of the events. In order to reveal faults caused by the relative ordering of $t$ or fewer of $v$ events, for some fixed $t$, a test suite must provide tests so that every ordering of every set of $t$ or fewer events is exercised. Such a test suite is equivalent to a sequence covering array, a set of permutations on $v$ events for which every subsequence of $t$ or fewer events arises in at least one of the permutations. Equivalently it is a (different) set of permutations, a completely $t$-scrambling set of permutations, in which the images of every set of $t$ chosen events include each of the $t!$ possible “patterns.” In event sequence testing, minimizing the number of permutations used is the principal objective. By developing a connection with covering arrays, lower bounds on this minimum in terms of the minimum number of rows in covering arrays are obtained. An existing bound on the largest $v$ for which the minimum can equal $t!$ is improved. A conditional expectation algorithm is developed to generate sequence covering arrays whose number of permutations never exceeds a specified logarithmic function of $v$ when $t$ is fixed, and this method is shown to operate in polynomial time. A recursive product construction is established when $t=3$ to construct sequence covering arrays on $vw$ events from ones on $v$ and $w$ events. Finally computational results are given for $t \in \{3,4,5\}$ to demonstrate the utility of the conditional expectation algorithm and the product construction.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications system. In this paper, we extend this coded modulation scheme based on permutation codes to general codes and introduce an additional new parameter that more precisely captures a code's performance against permanent narrowband noise. As a result, we define a new class of codes, namely, equitable symbol weight codes, which are optimal with respect to this measure.

We study (symbol-pair) codes for symbol-pair read channels introduced recently by Cassuto and Blaum (2010). A Singleton-type bound on symbol-pair codes is established and infinite families of optimal symbol-pair codes are constructed. These codes are maximum distance separable (MDS) in the sense that they meet the Singleton-type bound. In contrast to classical codes, where all known q-ary MDS codes have length O(q), we show that q-ary MDS symbol-pair codes can have length Ω(q2). In addition, we completely determine the existence of MDS symbol-pair codes for certain parameters.

The study of codes for powerline communications has garnered much interest over the past decade. Various types of codes such as permutation codes, frequency permutation arrays, and constant composition codes have been proposed over the years. In this paper, we study a type of code called bounded symbol weight codes which was first introduced by Versfeld in 2005, and a related family of codes that we term constant symbol weight codes. We provide new upper and lower bounds on the size of bounded symbol weight and constant symbol weight codes. We also give direct and recursive constructions of codes for certain parameters.

A cross-bifix-free code is a set of words in which no prefix of any length of any word is the suffix of any word in the set. Cross-bifix-free codes arise in the study of distributed sequences for frame synchronization. We provide a new construction of cross-bifix-free codes which generalizes the construction by Bajic to longer code lengths and to any alphabet size. The codes are shown to be nearly optimal in size. We also establish new results on Fibonacci sequences, which are used in estimating the size of the cross-bifix-free codes.

A problem of index coding with side information was first considered by Birk and Kol in 1998. In this study, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ , what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ -bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with a maximum distance separable classical code is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Further, the problem of error-correcting decoding by a linear ECIC is studied. It is shown that in order to decode correctly the desired symbol, the decoder is required to find one of the vectors, belonging to an affine space containing the actual error vector. The syndrome decoding is shown to produce the correct output if the weight of the error pattern is less or equal to the error-correcting capability of the corresponding ECIC. Finally, the notion of static ECIC, which is suitable for use with a family of instances of an index coding problem, is introduced. Several bounds on the length of static ECICs are derived, and constructions for static ECICs are discussed. Connections of these codes to weakly resilient Boolean functions are established.

In this article we construct an infinite family of linear error correcting codes over Fqfor any prime power q. The code parameters are [q2t+ qt-1- q2t-1- qt, 2t+1, q2t+ q2t-2+ qt-1- 2q2t-1- qt]q, for any positive integer t. This family is a generalisation of the optimal self-complementary binary codes with parameters [2u2- u, 2t + 1, u2- u]2, where u = 2t-1. The codes are obtained by considering a submatrix of a specially constructed generalised Hadamard matrix. The optimality of the family is confirmed by using a recently derived generalisation of the Grey-Rankin bound when t >; 1, and the Griesmer bound when t = 1.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications (PLC) system. Equitable symbol weight codes was recently demonstrated to optimize the performance against narrowband noise in a general coded modulation scheme. This paper establishes the first infinite family of optimal equitable symbol weight codes with code lengths greater than alphabet size and whose relative narrowband noise error-correcting capabilities do not diminish to zero as the length grows. These families of codes meet the Plotkin bound. The construction method introduced is combinatorial and reveals interesting interplay with an extension of the concept of generalized balanced tournament designs from combinatorial design theory.

The use of multiple frequency shift keying modulation with permutation codes addresses the problem of permanent narrowband noise disturbance in a power line communications system. In this paper, we extend this coded modulation scheme based on permutation codes to general codes and introduce an additional new parameter that helps to more precisely capture a code's performance against permanent narrowband noise. As a result, we define a new class of codes, namely, equitable symbol weight codes, which are optimal with respect to this measure. In addition, we demonstrate via simulations that equitable symbol weight codes achieve lower symbol error rates than other codes of the same length and distance over the same alphabet.

We study (symbol-pair) codes for symbol-pair read channels introduced recently by Cassuto and Blaum (2010). A Singleton-type bound on symbol-pair codes is established and infinite families of optimal symbol-pair codes are constructed. These codes are maximum distance separable (MDS) in the sense that they meet the Singleton-type bound. In contrast to classical codes, where all known q-ary MDS codes have length O(q), we show that q-ary MDS symbol-pair codes can have length Ω(q2). We also construct equidistant cyclic MDS symbol-pair codes from Mendelsohn designs.

We study the decoding of permutation codes obtained from distance preserving maps and distance increasing maps from Hamming space. We provide efficient algorithms for estimating the q-ary digits of the Hamming space so that decoding can be performed in the Hamming space.

The min-rank of a digraph was shown by Bar-Yossef et al. (2006) to represent the length of an optimal scalar linear solution of the corresponding instance of the Index Coding with Side Information (ICSI) problem. In this work, the graphs and digraphs of near-extreme min-ranks are characterized. Those graphs and digraphs correspond to the ICSI instances having near-extreme transmission rates when using optimal scalar linear index codes. It is also shown that the decision problem of whether a digraph has min-rank two is NP-complete. By contrast, the same question for graphs can be answered in polynomial time.

Frameproof codes are used to preserve the security in the context of coalition when fingerprinting digital data. Let Mc,l(q) be the largest cardinality of a q-ary c-frameproof code of length l and Rc,l=limq→∞Mc,l(q)/q[ l/c]. It has been determined by Blackburn that Rc,l=1 when l≡1(mod c), Rc,l=2 when c=2 and l is even, and R3,5=5/3. In this paper, we give a recursive construction for c-frameproof codes of length l with respect to the alphabet size q . As applications of this construction, we establish the existence results for q-ary c-frameproof codes of length c+2 and size c+2/c(q-1)2+1 for all odd q when c=2 and for all q≡4 when c=3 . Furthermore, we show that Rc,c+2=(c+2)/c meeting the upper bound given by Blackburn, for all integers c such that c+1 is a prime power.

Security aspects of the index coding with side information (ICSI) problem are investigated. Building on the results of Bar-Yossef (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrixL, whose column space codeC(L) has lengthn, minimum distanced, and dual distanced⊥, is (d-1-t) -block secure (and hence also weakly secure) if the adversary knows in advancet≤d-2 messages, and is completely insecure if the adversary knows in advance more thann-d⊥messages. Strong security is examined under the conditions that the adversary: 1) possessestmessages in advance; 2) eavesdrops at most μ transmissions; 3) corrupts at most δ transmissions. We prove that for sufficiently largeq, an optimal linear index code which is strongly secure against such an adversary has length κq+μ+2δ . Here, κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

Security aspects of the Index Coding with Side Information (ICSI) problem are investigated. Building on the results of Bar-Yossef et al. (2006), the properties of linear index codes are further explored. The notion of weak security, considered by Bhattad and Narayanan (2005) in the context of network coding, is generalized to block security. It is shown that the linear index code based on a matrix L, whose column space code C(L) has length n, minimum distance d and dual distance d⊥, is (d-1-t)-block secure (and hence also weakly secure) if the adversary knows in advance t ≤ d - 2 messages, and is completely insecure if the adversary knows in advance more than n-d⊥messages. Strong security is examined under the conditions that the adversary: (i) possesses t messages in advance; (ii) eavesdrops at most μ transmissions; (iii) corrupts at most δ transmissions. We prove that for sufficiently large q, an optimal linear index code, which is strongly secure against such an adversary, has length κq+μ+2δ. Here κqis a generalization of the min-rank over Fqof the side information graph for the ICSI problem in its original formulation in the work of Bar-Yossef et al.

A problem of index coding with side information was first considered by Y. Birk and T. Kol (IEEE INFOCOM, 1998). In the present work, a generalization of index coding scheme, where transmitted symbols are subject to errors, is studied. Error-correcting methods for such a scheme, and their parameters, are investigated. In particular, the following question is discussed: given the side information hypergraph of index coding scheme and the maximal number of erroneous symbols δ, what is the shortest length of a linear index code, such that every receiver is able to recover the required information? This question turns out to be a generalization of the problem of finding a shortest-length error-correcting code with a prescribed error-correcting capability in the classical coding theory. The Singleton bound and two other bounds, referred to as the α-bound and the κ-bound, for the optimal length of a linear error-correcting index code (ECIC) are established. For large alphabets, a construction based on concatenation of an optimal index code with an MDS classical code, is shown to attain the Singleton bound. For smaller alphabets, however, this construction may not be optimal. A random construction is also analyzed. It yields another inexplicit bound on the length of an optimal linear ECIC. Finally, the decoding of linear ECIC's is discussed. The syndrome decoding is shown to output the exact message if the weight of the error vector is less or equal to the error-correcting capability of the corresponding ECIC.

α-acyclicity is an important notion in database theory. The α-arboricity of a hypergraph [Formula: see text] is the minimum number of α-acyclic hypergraphs that partition the edge set of [Formula: see text]. The α-arboricity of the complete 3-uniform hypergraph is determined completely.

One peculiarity with deletion-correcting codes is that perfect t-deletion-correcting codes of the same length over the same alphabet can have different numbers of codewords, because the balls of radius t with respect to the Levenshte[Formula: see text]n distance may be of different sizes. There is interest, therefore, in determining all possible sizes of a perfect t-deletion-correcting code, given the length n and the alphabet size q. In this paper, we determine completely the spectrum of possible sizes for perfect q-ary 1-deletion-correcting codes of length three for all q, and perfect q-ary 2-deletion-correcting codes of length four for almost all q, leaving only a small finite number of cases in doubt.

An optimal constant-composition or constant-weight code of weight $w$ has linear size if and only if its distance $d$ is at least $2w-1$. When $d\geq 2w$, the determination of the exact size of such a constant-composition or constant-weight code is trivial, but the case of $d=2w-1$ has been solved previously only for binary and ternary constant-composition and constant-weight codes, and for some sporadic instances. This paper provides a construction for quasicyclic optimal constant-composition and constant-weight codes of weight $w$ and distance $2w-1$ based on a new generalization of difference triangle sets. As a result, the sizes of optimal constant-composition codes and optimal constant-weight codes of weight $w$ and distance $2w-1$ are determined for all such codes of sufficiently large lengths. This solves an open problem of Etzion. The sizes of optimal constant-composition codes of weight $w$ and distance $2w-1$ are also determined for all $w\leq 6$, except in two cases.

Optimal partitioned cyclic difference packings (PCDPs) are shown to give rise to optimal frequency-hopping sequences and optimal comma-free codes. New constructions for PCDPs, based on almost difference sets and cyclic difference matrices, are given. These produce new infinite families of optimal PCDPs (and hence optimal frequency-hopping sequences and optimal comma-free codes). The existence problem for optimal PCDPs in BBZ3m, withmbase blocks of size three, is also solved for allm≠ 8,16 mod 24.

This paper proposes some simple propagation rules which give rise to new binary constant-weight codes.

This work addresses a novel spatial keyword query called the m-closest keywords (mCK) query. Given a database of spatial objects, each tuple is associated with some descriptive information represented in the form of keywords. The mCK query aims to find the spatially closest tuples which match m user-specified keywords. Given a set of keywords from a document, mCK query can be very useful in geotagging the document by comparing the keywords to other geotagged documents in a database. To answer mCK queries efficiently, we introduce a new index called the bR*-tree, which is an extension of the R*-tree. Based on bR*-tree, we exploit a priori-based search strategies to effectively reduce the search space. We also propose two monotone constraints, namely the distance mutex and keyword mutex, as our a priori properties to facilitate effective pruning. Our performance study demonstrates that our search strategy is indeed efficient in reducing query response time and demonstrates remarkable scalability in terms of the number of query keywords which is essential for our main application of searching by document.

Although prone to fabrication error, the nanowire crossbar is a promising candidate compoent for next generation nanometer-scale circuits. In the nanowire crossbar architecture, nanowires are addressed by controlling voltages on the mesowires. For area efficiency, we are interested in the maximum number of nanowires N(m,e) that can be addressed by m mesowires, in the face of up to e fabrication errors. Asymptotically tight bounds on N(m,e) are established in this paper. In particular, it is shown that N(m,e) = Theta(2m/ mepsiv+1/2). Interesting observations are made on the equivalence between this problem and the problem of constructing optimal EC/AUED codes, superimposed distance codes, pooling designs, and diffbounded set systems. Results in this paper also improve upon those in the EC/AUEC codes literature.

This correspondence introduces two new constructive techniques to complete the determination of the sizes of optimal$q$-ary codes of constant weight three and distance four.

The concept of group divisible codes, a generalization of group divisible designs with constant block size, is introduced in this paper. This new class of codes is shown to be useful in recursive constructions for constant-weight and constant-composition codes. Large classes of group divisible codes are constructed which enabled the determination of the sizes of optimal constant-composition codes of weight three (and specified distance), leaving only four cases undetermined. Previously, the sizes of constant-composition codes of weight three were known only for those of sufficiently large length.

The design of large libraries of oligonucleotides having constant-content and satisfying Hamming distance constraints between oligonucleotides and their Watson-Crick complements is important in reducing hybridization errors in DNA computing, DNA microarray technologies, and molecular bar coding. Various techniques have been studied for the construction of such oligonucleotide libraries, ranging from algorithmic constructions via stochastic local search to theoretical constructions via coding theory. A new stochastic local search method is introduced, which yields improvements for more than one third of the benchmark lower bounds of Gaborit and King (2005) for n-mer oligonucleotide libraries when n les 14. Several optimal libraries are also found by computing maximum cliques on certain graphs.

The problem of determining extremal hypergraphs containing at most r isomorphic copies of some element of a given hypergraph family was first studied by Boros et al. in 2001. There are not many hypergraph families for which exact results are known concerning the size of the corresponding extremal hypergraphs, except for those equivalent to the classical Turán numbers. In this paper, we determine the size of extremal k-uniform hypergraphs containing at most one pair of 2-intersecting edges for $k\in\{3,4\}$. We give a complete solution when $k=3$ and an almost complete solution (with eleven exceptions) when $k=4$.

This paper introduces a new combinatorial construction for$q$-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between$q$-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types.

We show an interesting pairwise balanced design (PBD)-closure result for the set of lengths of constant-composition codes whose distance and size meet certain conditions. A consequence of this PBD-closure result is that the size of optimal constant-composition codes can be determined for infinite families of parameter sets from just a single example of an optimal code. As an application, the sizes of several infinite families of optimal constant-composition codes are derived. In particular, the problem of determining the size of optimal constant-composition codes having distance four and weight three is solved for all lengths sufficiently large. This problem was previously unresolved for odd lengths, except for lengths seven and eleven.

Off-chip buses account for a significant portion of the total system power consumed in embedded systems. Bus encoding schemes have been proposed to minimize power dissipation, but none has been demonstrated to be optimal with respect to any measure. In this paper, we give the first provably optimal and explicit (polynomial-time constructible) families of memoryless codes for minimizing bit transitions in off-chip buses. Our results imply that having access to a clock does not make a memoryless encoding scheme that minimizes bit transitions more powerful.

Difference triangle sets are useful in many practical problems of information transmission. This article studies combinatorial and computational constructions for difference triangle sets having small scopes. Our algorithms have been used to produce difference triangle sets whose scopes are the best currently known.

The authors present an effective performance driven placement with global routing algorithm for macro cells. Their algorithm is a hierarchical, divide and conquer, quad-partitioning approach. The quad-partitioning routine uses the Tabu search technique. Their algorithm uses the concept of proximity of regions to approximate the interconnection delays during the placement process. In addition, their algorithm can handle modules whose positions are fixed or are restricted to a particular subregion on the layout frame. The experimental results indicate the superiority of their placement in terms of quality of solutions and run times when compared to those by I. Lin and D. Du (1990).>