A normal rational curve of the (k-1) -dimensional projective space over Fq is an arc of size q+1 , since any k points of the curve span the whole space. In this paper, we will prove that if q is odd, then a subset of size 3k-6 of a normal rational curve cannot be extended to an arc of size q+2 . In fact, we prove something slightly stronger. Suppose that q is odd and E is a (2k-3) -subset of an arc G of size 3k-6 . If G projects to a subset of a conic from every (k-3) -subset of E , then G cannot be extended to an arc of size q+2 . Stated in terms of error-correcting codes we prove that a k -dimensional linear maximum distance separable code of length 3k-6 over a field Fq of odd characteristic, which can be extended to a Reed–Solomon code of length q+1 , cannot be extended to a linear maximum distance separable code of length q+2 .
The degrees of freedom (DoFs) of the K-user multiple-input multiple-output (MIMO) interference channel are studied when perfect, but delayed channel state information is available at the transmitter side (delayed CSIT). Recent works have proposed schemes improving the DoF knowledge of the interference channel, but at the cost of developing transmission involving many channel uses (long delay), thus increasing the complexity at both transmitter and receiver side. This paper proposes three linear precoding strategies, limited to at most three phases, based on the concept of interference alignment, and built upon three main ingredients: delayed CSIT precoding, user scheduling, and redundancy transmission. In this respect, the interference alignment is realized by exploiting delayed CSIT to align the interference at the non-intended receivers along the space-time domain. Moreover, a new framework is proposed where the number of transmitted symbols and duration of the phases is obtained as the solution of a maximization problem, and enabling the introduction of complexity constraints, which allows deriving the achievable DoF as a function of the transmission delay, i.e., the achievable DoF-delay trade-off. Finally, the latter part of this paper settles that the assumption of time-varying channels common along all the literature on delayed CSIT is indeed unnecessary.
Most performance measures of pilot-assisted multiple-input multiple-output systems are functions of the linear precoder and the pilot sequence. A framework for the optimization of these two parameters is proposed, based on a matrix-valued generalization of the concept of effective signal-to-noise ratio (SNR) introduced in the famous work by Hassibi and Hochwald. Our framework aims to extend the work of Hassibi and Hochwald by allowing for transmit-side fading correlations, and by considering a class of utility functions of said effective SNR matrix, most notably including the well-known capacity lower bound used by Hassibi and Hochwald. We tackle the joint optimization problem by recasting the optimization of the precoder (resp. pilot sequence) subject to a fixed pilot sequence (resp. precoder) into a convex problem. Furthermore, we prove that joint optimality requires that the eigenbases of the precoder and pilot sequence be both aligned along the eigenbasis of the channel correlation matrix. We finally describe how to wrap all studied subproblems into an iteration that converges to a local optimum of the joint optimization.
Beimel and Orlov proved that all information
inequalities on four or five variables, together with all information
inequalities on more than five variables that are known to date,
provide lower bounds on the size of the shares in secret sharing
schemes that are at most linear on the number of participants.
We present here another two negative results about the power of
information inequalities in the search for lower bounds in secret
sharing. First, we prove that all information inequalities on a
bounded number of variables can only provide lower bounds that
are polynomial on the number of participants. Second, we prove
that the rank inequalities that are derived from the existence of
two common informations can provide only lower bounds that
are at most cubic in the number of participants.
As shown by Médard, the capacity of fading channels with imperfect channel-state information can be lower-bounded by assuming a Gaussian channel input X with power P and by upper-bounding the conditional entropy h(X|Y,H) by the entropy of a Gaussian random variable with variance equal to the linear minimum mean-square error in estimating X from \(Y, H). We demonstrate that, using a rate-splitting approach, this lower bound can be sharpened: by expressing the Gaussian input X as the sum of two independent Gaussian variables X1 and X2 and by applying Médard's lower bound first to bound the mutual information between X1 and Y while treating X2 as noise, and by applying it a second time to the mutual information between X2 and Y while assuming X1 to be known, we obtain a capacity lower bound that is strictly larger than Médard's lower bound. We then generalize this approach to an arbitrary number L of layers, where X is expressed as the sum of L independent Gaussian random variables of respective variances Pl, l = 1, ¿ ,L summing up to P. Among all such rate-splitting bounds, we determine the supremum over power allocations Pl and total number of layers L. This supremum is achieved for L 8 and gives rise to an analytically expressible capacity lower bound. For Gaussian fading, this novel bound is shown to converge to the Gaussian-input mutual information as the signal-to-noise ratio (SNR) grows, provided that the variance of the channel estimation error H-H tends to zero as the SNR tends to infinity.
We present new families of access structures that, similarly to the multilevel and compartmented access structures introduced in previous works, are natural generalizations of threshold secret sharing. Namely, they admit ideal linear secret sharing schemes over every large enough finite field, they can be described by a small number of parameters, and they have useful properties for the applications of secret sharing. The use of integer polymatroids makes it possible to find many new such families and it simplifies in great measure the proofs for the existence of ideal secret sharing schemes for them.
Hierarchical secret sharing is among the most natural generalizations of threshold secret sharing, and it has attracted a lot of attention since the invention of secret sharing until nowadays. Several constructions of ideal hierarchical secret sharing schemes have been proposed, but it was not known what access structures admit such a scheme. We solve this problem by providing a natural definition for the family of the hierarchical access structures and, more importantly, by presenting a complete characterization of the ideal hierarchical access structures, that is, the ones admitting an ideal secret sharing scheme. Our characterization is based on the well known connection between ideal secret sharing schemes and matroids and, more specifically, on the connection between ideal multipartite secret sharing schemes and integer polymatroids. In particular, we prove that every hierarchical matroid port admits an ideal linear secret sharing scheme over every large enough finite field. Finally, we use our results to present a new proof for the existing characterization of the ideal weighted threshold access structures.
Following the seminal work by Zheng and Tse on
the diversity and multiplexing tradeoff (DMT) of multiple-input
multiple-output (MIMO) channels, in this paper, we introduce
the array gain to investigate the fundamental relation between
transmission rate and reliability inMIMO systems. The array gain
gives information on the power offset that results from exploiting
channel state information at the transmitter or as a consequence
of the channel model. Hence, the diversity, multiplexing, and
array gain (DMA) analysis is able to cope with the limitations
of the original DMT and provide an operational meaning in the
sense that the DMA gains of a particular system can be directly
translated into a parameterized characterization of its associated
outage probability performance. In this paper, we derive the
best DMA gains achievable by any scheme employing isotropic
signaling in uncorrelated Rayleigh, semicorrelated Rayleigh, and
uncorrelated Rician block-fading MIMO channels. We use these
results to analyze the effect of important channel parameters on
the outage performance at different points of the DMT curve.
A fingerprinting code is a set of codewords that are embedded in each copy of a digital object with the purpose of making each copy unique. If the fingerprinting code is c-secure with error, then the decoding of a pirate word created by a coalition of at most c dishonest users, will expose at least one of the guilty parties with probability 1-ϵ. The Boneh-Shaw fingerprinting codes are n-secure codes with ϵB error, where n also denotes the number of authorized users. Unfortunately, the length the Boneh-Shaw codes should be of order O(n3 log(n/ϵB)), which is prohibitive for practical applications. In this paper, we prove that the Boneh-Shaw codes are (c<; n)-secure for lengths of order O(nc2 log(n/ϵB)). Moreover, in this paper it is also shown how to use these codes to construct binary fingerprinting codes of length L=O(c6 log(c/ϵ) log n), with probability of error ϵ<;ϵB and an identification algorithm of complexity poly(log n)=poly(L). These results improve in some aspects the best known schemes and with a much more simple construction.
We present a mathematical formulation for the optimization
of query forgery for private information retrieval, in the
sense that the privacy risk is minimized for a given traffic and
processing overhead. The privacy risk is measured as an information-
theoretic divergence between the user’s query distribution
and the population’s, which includes the entropy of the user’s distribution
as a special case. We carefully justify and interpret our
privacy criterion from diverse perspectives. Our formulation poses
a mathematically tractable problem that bears substantial resemblance
with rate-distortion theory.
Maynou, J.; Gallardo, J.; Vallverdu, M.; Caminal, P.; Perera, A. IEEE transactions on information theory Vol. 52, num. 2, p. 734-741 DOI: 10.1109/TIT.2009.2037038 Data de publicació: 2010-02-15 Article en revista
Regulatory sequence detection is a critical facet for understanding the cell mechanisms in order to coordinate the response to stimuli. Protein synthesis involves the binding of a
transcription factor to specific sequences in a process related to the gene expression initiation. A characteristic of this binding process is that the same factor binds with different sequences placed along all genome. Thus, any computational approach shows many difficulties related with this variability observed from the binding sequences. This paper proposes the detection of transcription factor binding sites based on a parametric uncertainty measurement (Rényi entropy). This detection algorithm evaluates the variation on the total Rényi entropy of a set of sequences when a candidate sequence is assumed to be a true binding site belonging to the set. The efficiency of the method is measured in form of Receiver Operating Characteristic curves on different transcription factors from
Saccharomyces cerevisiae organism. The results are compared with other known motif
detection algorithms such as Motif Discovery scan (MDscan) and Multiple EM for Motif Elicitation (MEME)
Cramer, R.; Daza, V.; Gracia, I.; Jimenez, J.; Leander, G.; Martí-Farré, J.; Padro, C. IEEE transactions on information theory Vol. 54, num. 6, p. 2644-2657 Data de publicació: 2008-06 Article en revista
The inversion problem concerning the windowed Fourier transform is considered. It is shown that, out of the infinite solutions that the problem admits, the windowed Fourier transform is the "optimal" solution according to a maximum-entropy selection criterion.