OpenRaiser/Intern-Atlas huggingface dataset:
The Degrees of Freedom Regions of Two-User and Certain Three-User MIMO Broadcast Channels with Delayed CSIT
Venue: arXiv cs.IT 2011
Year: 2011

The degrees of freedom (DoF) region of the fast-fading MIMO (multiple-input multiple-output) Gaussian broadcast channel (BC) is studied when there is delayed channel state information at the transmitter (CSIT). In this setting, the channel matrices are assumed to vary independently across time and the transmitter is assumed to know the channel matrices with some arbitrary finite delay. An outer-bound to the DoF region of the general $K$-user MIMO BC (with an arbitrary number of antennas at each terminal) is derived. This outer-bound is then shown to be tight for two classes of MIMO BCs, namely, (a) the two-user MIMO BC with arbitrary number of antennas at all terminals, and (b) for certain three-user MIMO BCs where all three receivers have an equal number of antennas and the transmitter has no more than twice the number of antennas present at each receivers. The achievability results are obtained by developing an interference alignment scheme that optimally accounts for multiple, and possibly distinct, number of antennas at the receivers.
Lattice Sequential Decoding for LAST Coded MIMO Channels: Achievable Rate, DMT, and Complexity Analysis
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the asymptotic performance of the lattice sequential decoder for LAttice Space-Time (LAST) coded MIMO channel is analyzed. We determine the rates achievable by lattice coding and sequential decoding applied to such a channel. The diversity-multiplexing tradeoff (DMT) under lattice sequential decoding is derived as a function of its parameter---the bias term, which is critical for controlling the amount of computations required at the decoding stage. Achieving low decoding complexity requires increasing the value of the bias term. However, this is done at the expense of losing the optimal tradeoff of the channel. In this work, we derive the tail distribution of the decoder's computational complexity in the high signal-to-noise ratio regime. Our analysis reveals that the tail distribution of such a low complexity decoder is dominated by the outage probability of the channel for the underlying coding scheme. Also, the tail exponent of the complexity distribution is shown to be equivalent to the DMT achieved by lattice coding and lattice sequential decoding schemes. We derive the asymptotic average complexity of the sequential decoder as a function of the system parameters. In particular, we show that there exists a cut-off multiplexing gain for which the average computational complexity of the decoder remains bounded.
Graffiti Networks: A Subversive, Internet-Scale File Sharing Model
Venue: arXiv cs.NI 2011
Year: 2011

The proliferation of peer-to-peer (P2P) file sharing protocols is due to their efficient and scalable methods for data dissemination to numerous users. But many of these networks have no provisions to provide users with long term access to files after the initial interest has diminished, nor are they able to guarantee protection for users from malicious clients that wish to implicate them in incriminating activities. As such, users may turn to supplementary measures for storing and transferring data in P2P systems. We present a new file sharing paradigm, called a Graffiti Network, which allows peers to harness the potentially unlimited storage of the Internet as a third-party intermediary. Our key contributions in this paper are (1) an overview of a distributed system based on this new threat model and (2) a measurement of its viability through a one-year deployment study using a popular web-publishing platform. The results of this experiment motivate a discussion about the challenges of mitigating this type of file sharing in a hostile network environment and how web site operators can protect their resources.
Distributive Network Utility Maximization (NUM) over Time-Varying Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

Distributed network utility maximization (NUM) has received an increasing intensity of interest over the past few years. Distributed solutions (e.g., the primal-dual gradient method) have been intensively investigated under fading channels. As such distributed solutions involve iterative updating and explicit message passing, it is unrealistic to assume that the wireless channel remains unchanged during the iterations. Unfortunately, the behavior of those distributed solutions under time-varying channels is in general unknown. In this paper, we shall investigate the convergence behavior and tracking errors of the iterative primal-dual scaled gradient algorithm (PDSGA) with dynamic scaling matrices (DSC) for solving distributive NUM problems under time-varying fading channels. We shall also study a specific application example, namely the multi-commodity flow control and multi-carrier power allocation problem in multi-hop ad hoc networks. Our analysis shows that the PDSGA converges to a limit region rather than a single point under the finite state Markov chain (FSMC) fading channels. We also show that the order of growth of the tracking errors is given by O(T/N), where T and N are the update interval and the average sojourn time of the FSMC, respectively. Based on this analysis, we derive a low complexity distributive adaptation algorithm for determining the adaptive scaling matrices, which can be implemented distributively at each transmitter. The numerical results show the superior performance of the proposed dynamic scaling matrix algorithm over several baseline schemes, such as the regular primal-dual gradient algorithm.
On the Performance of Selection Cooperation with Outdated CSI and Channel Estimation Errors
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the performance of selection cooperation in the presence of imperfect channel estimation. In particular, we consider a cooperative scenario with multiple relays and amplify-and-forward protocol over frequency flat fading channels. In the selection scheme, only the "best" relay which maximizes the effective signal-to-noise ratio (SNR) at the receiver end is selected. We present lower and upper bounds on the effective SNR and derive closed-form expressions for the average symbol error rate (ASER), outage probability and average capacity per bandwidth of the received signal in the presence of channel estimation errors. A simulation study is presented to corroborate the analytical results and to demonstrate the performance of relay selection with imperfect channel estimation.
Personalized Event-Based Surveillance and Alerting Support for the Assessment of Risk
Venue: arXiv cs.CY 2011
Year: 2011

In a typical Event-Based Surveillance setting, a stream of web documents is continuously monitored for disease reporting. A structured representation of the disease reporting events is extracted from the raw text, and the events are then aggregated to produce signals, which are intended to represent early warnings against potential public health threats. To public health officials, these warnings represent an overwhelming list of "one-size-fits-all" information for risk assessment. To reduce this overload, two techniques are proposed. First, filtering signals according to the user's preferences (e.g., location, disease, symptoms, etc.) helps reduce the undesired noise. Second, re-ranking the filtered signals, according to an individual's feedback and annotation, allows a user-specific, prioritized ranking of the most relevant warnings. We introduce an approach that takes into account this two-step process of: 1) filtering and 2) re-ranking the results of reporting signals. For this, Collaborative Filtering and Personalization are common techniques used to support users in dealing with the large amount of information that they face.
GeoQuorum: Load Balancing and Energy Efficient Data Access in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

When data productions and consumptions are heavily unbalanced and when the origins of data queries are spatially and temporally distributed, the so called in-network data storage paradigm supersedes the conventional data collection paradigm in wireless sensor networks (WSNs). In this paper, we first introduce geometric quorum systems (along with their metrics) to incarnate the idea of in-network data storage. These quorum systems are "geometric" because curves (rather than discrete node sets) are used to form quorums. We then propose GeoQuorum as a new quorum system, for which the quorum forming curves are parameterized. Though our proposal stems from the existing work on using curves to guide data replication and retrieval in dense WSNs, we significantly expand this design methodology, by endowing GeoQuorum with a great flexibility to fine-tune itself towards different application requirements. In particular, the tunability allows GeoQuorum to substantially improve the load balancing performance and to remain competitive in energy efficiency. Both our analysis and simulations confirm the performance enhancement brought by GeoQuorum.
Energy Efficiency and Reliability in Wireless Biomedical Implant Systems
Venue: arXiv cs.IT 2011
Year: 2011

The use of wireless implant technology requires correct delivery of the vital physiological signs of the patient along with the energy management in power-constrained devices. Toward these goals, we present an augmentation protocol for the physical layer of the Medical Implant Communications Service (MICS) with focus on the energy efficiency of deployed devices over the MICS frequency band. The present protocol uses the rateless code with the Frequency Shift Keying (FSK) modulation scheme to overcome the reliability and power cost concerns in tiny implantable sensors due to the considerable attenuation of propagated signals across the human body. In addition, the protocol allows a fast start-up time for the transceiver circuitry. The main advantage of using rateless codes is to provide an inherent adaptive duty-cycling for power management, due to the flexibility of the rateless code rate. Analytical results demonstrate that an 80% energy saving is achievable with the proposed protocol when compared to the IEEE 802.15.4 physical layer standard with the same structure used for wireless sensor networks. Numerical results show that the optimized rateless coded FSK is more energy efficient than that of the uncoded FSK scheme for deep tissue (e.g., digestive endoscopy) applications, where the optimization is performed over modulation and coding parameters.
Beating the Gilbert-Varshamov Bound for Online Channels
Venue: arXiv cs.IT 2011
Year: 2011

In the online channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x =(x_1,...,x_n) in {0,1}^n bit by bit via a channel limited to at most pn corruptions. The channel is online in the sense that at the ith step the channel decides whether to flip the ith bit or not and its decision is based only on the bits transmitted so far, i.e., (x_1,...,x_i). This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge on the sent codeword x. The best known lower bound on the capacity of both the online channel and the classical adversarial channel is the well-known Gilbert-Varshamov bound. In this paper we prove a lower bound on the capacity of the online channel which beats the Gilbert-Varshamov bound for any positive p such that H(2p) < 0.5 (where H is the binary entropy function). To do so, we prove that for any such p, a code chosen at random combined with the nearest neighbor decoder achieves with high probability a rate strictly higher than the Gilbert-Varshamov bound (for the online channel).
Comparison of Loss ratios of different scheduling algorithms
Venue: arXiv cs.OS 2011
Year: 2011

It is well known that in a firm real time system with a renewal arrival process, exponential service times and independent and identically distributed deadlines till the end of service of a job, the earliest deadline first (EDF) scheduling policy has smaller loss ratio (expected fraction of jobs, not completed) than any other service time independent scheduling policy, including the first come first served (FCFS). Various modifications to the EDF and FCFS policies have been proposed in the literature, with a view to improving performance. In this article, we compare the loss ratios of these two policies along with some of the said modifications, as well as their counterparts with deterministic deadlines. The results include some formal inequalities and some counter-examples to establish non-existence of an order. A few relations involving loss ratios are posed as conjectures, and simulation results in support of these are reported. These results lead to a complete picture of dominance and non-dominance relations between pairs of scheduling policies, in terms of loss ratios.
Sharp Support Recovery from Noisy Random Measurements by L1 minimization
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we investigate the theoretical guarantees of penalized $\lun$ minimization (also called Basis Pursuit Denoising or Lasso) in terms of sparsity pattern recovery (support and sign consistency) from noisy measurements with non-necessarily random noise, when the sensing operator belongs to the Gaussian ensemble (i.e. random design matrix with i.i.d. Gaussian entries). More precisely, we derive sharp non-asymptotic bounds on the sparsity level and (minimal) signal-to-noise ratio that ensure support identification for most signals and most Gaussian sensing matrices by solving the Lasso problem with an appropriately chosen regularization parameter. Our first purpose is to establish conditions allowing exact sparsity pattern recovery when the signal is strictly sparse. Then, these conditions are extended to cover the compressible or nearly sparse case. In these two results, the role of the minimal signal-to-noise ratio is crucial. Our third main result gets rid of this assumption in the strictly sparse case, but this time, the Lasso allows only partial recovery of the support. We also provide in this case a sharp $\ell_2$-consistency result on the coefficient vector. The results of the present work have several distinctive features compared to previous ones. One of them is that the leading constants involved in all the bounds are sharp and explicit. This is illustrated by some numerical experiments where it is indeed shown that the sharp sparsity level threshold identified by our theoretical results below which sparsistency of the Lasso is guaranteed meets that empirically observed.
Probing a Self-Developed Aesthetics Measurement Application (SDA) in Measuring Aesthetics of Mandarin Learning Web Page Interfaces
Venue: arXiv cs.HC 2011
Year: 2011

This article describes the accurateness of our application namely Self-Developed Aesthetics Measurement Application (SDA) in measuring the aesthetics aspect by comparing the results of our application and users' perceptions in measuring the aesthetics of the web page interfaces. For this research, the positions of objects, images element and texts element are defined as objects in a web page interface. Mandarin learning web pages are used in this research. These learning web pages comprised of main pages, learning pages and exercise pages, on the first author's E-portfolio web site. The objects of the web pages were manipulated in order to produce the desired aesthetic values. The six aesthetics related elements used are balance, equilibrium, symmetry, sequence, rhythm, as well as order and complexity. Results from the research showed that the ranking of the aesthetics values of the web page interfaces measured of the users were congruent with the expected perceptions of our designed Mandarin learning web page interfaces (reported also in [18]). Thus, it implies that the subjectivity of aesthetics can be measured in an objective manner. For further understanding on our effort in doing aesthetics measurement, we discussed in details the object modelling used as well as the process in developing this application. We also explained the steps on how to run our application. Additionally, the strength and the weakness of our SDA application shared in this paper suggest that there is still room for the improvement for aesthetics measurement.
Finitary languages
Venue: arXiv cs.FL 2011
Year: 2011

The class of omega-regular languages provides a robust specification language in verification. Every omega-regular condition can be decomposed into a safety part and a liveness part. The liveness part ensures that something good happens "eventually". Finitary liveness was proposed by Alur and Henzinger as a stronger formulation of liveness. It requires that there exists an unknown, fixed bound b such that something good happens within b transitions. In this work we consider automata with finitary acceptance conditions defined by finitary Buchi, parity and Streett languages. We study languages expressible by such automata: we give their topological complexity and present a regular-expression characterization. We compare the expressive power of finitary automata and give optimal algorithms for classical decisions questions. We show that the finitary languages are Sigma 2-complete; we present a complete picture of the expressive power of various classes of automata with finitary and infinitary acceptance conditions; we show that the languages defined by finitary parity automata exactly characterize the star-free fragment of omega B-regular languages; and we show that emptiness is NLOGSPACE-complete and universality as well as language inclusion are PSPACE-complete for finitary parity and Streett automata.
Automata and temporal logic over arbitrary linear time
Venue: arXiv cs.LO 2011
Year: 2011

Linear temporal logic was introduced in order to reason about reactive systems. It is often considered with respect to infinite words, to specify the behaviour of long-running systems. One can consider more general models for linear time, using words indexed by arbitrary linear orderings. We investigate the connections between temporal logic and automata on linear orderings, as introduced by Bruyère and Carton. We provide a doubly exponential procedure to compute from any LTL formula with Until, Since, and the Stavi connectives an automaton that decides whether that formula holds on the input word. In particular, since the emptiness problem for these automata is decidable, this transformation gives a decision procedure for the satisfiability of the logic.
Constructive spherical codes near the Shannon bound
Venue: arXiv cs.IT 2011
Year: 2011

Shannon gave a lower bound in 1959 on the binary rate of spherical codes of given minimum Euclidean distance $ρ$. Using nonconstructive codes over a finite alphabet, we give a lower bound that is weaker but very close for small values of $ρ$. The construction is based on the Yaglom map combined with some finite sphere packings obtained from nonconstructive codes for the Euclidean metric. Concatenating geometric codes meeting the TVZ bound with a Lee metric BCH code over $GF(p),$ we obtain spherical codes that are polynomial time constructible. Their parameters outperform those obtained by Lachaud and Stern in 1994. At very high rate they are above 98 per cent of the Shannon bound.
Sorting, Searching, and Simulation in the MapReduce Framework
Venue: arXiv cs.DC 2011
Year: 2011

In this paper, we study the MapReduce framework from an algorithmic standpoint and demonstrate the usefulness of our approach by designing and analyzing efficient MapReduce algorithms for fundamental sorting, searching, and simulation problems. This study is motivated by a goal of ultimately putting the MapReduce framework on an equal theoretical footing with the well-known PRAM and BSP parallel models, which would benefit both the theory and practice of MapReduce algorithms. We describe efficient MapReduce algorithms for sorting, multi-searching, and simulations of parallel algorithms specified in the BSP and CRCW PRAM models. We also provide some applications of these results to problems in parallel computational geometry for the MapReduce framework, which result in efficient MapReduce algorithms for sorting, 2- and 3-dimensional convex hulls, and fixed-dimensional linear programming. For the case when mappers and reducers have a memory/message-I/O size of $M=Θ(N^ε)$, for a small constant $ε>0$, all of our MapReduce algorithms for these applications run in a constant number of rounds.
The graphs with the max-Mader-flow-min-multiway-cut property
Venue: arXiv cs.DM 2011
Year: 2011

We are given a graph $G$, an independant set $\mathcal{S} \subset V(G)$ of \emph{terminals}, and a function $w:V(G) \to \mathbb{N}$. We want to know if the maximum $w$-packing of vertex-disjoint paths with extremities in $\mathcal{S}$ is equal to the minimum weight of a vertex-cut separating $\mathcal{S}$. We call \emph{Mader-Mengerian} the graphs with this property for each independant set $\mathcal{S}$ and each weight function $w$. We give a characterization of these graphs in term of forbidden minors, as well as a recognition algorithm and a simple algorithm to find maximum packing of paths and minimum multicuts in those graphs.
The power and Arnoldi methods in an algebra of circulants
Venue: arXiv cs.NA 2011
Year: 2011

Circulant matrices play a central role in a recently proposed formulation of three-way data computations. In this setting, a three-way table corresponds to a matrix where each "scalar" is a vector of parameters defining a circulant. This interpretation provides many generalizations of results from matrix or vector-space algebra. We derive the power and Arnoldi methods in this algebra. In the course of our derivation, we define inner products, norms, and other notions. These extensions are straightforward in an algebraic sense, but the implications are dramatically different from the standard matrix case. For example, a matrix of circulants has a polynomial number of eigenvalues in its dimension; although, these can all be represented by a carefully chosen canonical set of eigenvalues and vectors. These results and algorithms are closely related to standard decoupling techniques on block-circulant matrices using the fast Fourier transform.
Fixed-complexity Sphere Encoder for Multi-user MIMO Systems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a fixed-complexity sphere encoder (FSE) for multi-user MIMO (MU-MIMO) systems. The proposed FSE accomplishes a scalable tradeoff between performance and complexity. Also, because it has a parallel tree-search structure, the proposed encoder can be easily pipelined, leading to a tremendous reduction in the precoding latency. The complexity of the proposed encoder is also analyzed, and we propose two techniques that reduce it. Simulation and analytical results demonstrate that in a 4 by 4 MU-MIMO system, the proposed FSE requires only 11.5% of the computational complexity needed by the conventional QRD-M encoder (QRDM-E). Also, the encoding throughput of the proposed encoder is 7.5 times that of the QRDM-E with tolerable degradation in the BER performance, while achieving the optimum diversity order.