OpenRaiser/Intern-Atlas huggingface dataset:
Using Graphics Processors for Parallelizing Hash-based Data Carving
Venue: arXiv cs.DC 2009
Year: 2009

The ability to detect fragments of deleted image files and to reconstruct these image files from all available fragments on disk is a key activity in the field of digital forensics. Although reconstruction of image files from the file fragments on disk can be accomplished by simply comparing the content of sectors on disk with the content of known files, this brute-force approach can be time consuming. This paper presents results from research into the use of Graphics Processing Units (GPUs) in detecting specific image file byte patterns in disk clusters. Unique identifying pattern for each disk sector is compared against patterns in known images. A pattern match indicates the potential presence of an image and flags the disk sector for further in-depth examination to confirm the match. The GPU-based implementation outperforms the software implementation by a significant margin.
Communication over Individual Channels
Venue: arXiv cs.IT 2009
Year: 2009

We consider the problem of communicating over a channel for which no mathematical model is specified. We present achievable rates as a function of the channel input and output known a-posteriori for discrete and continuous channels, as well as a rate-adaptive scheme employing feedback which achieves these rates asymptotically without prior knowledge of the channel behavior.
On the Degrees-of-Freedom of the K-User Gaussian Interference Channel
Venue: arXiv cs.IT 2009
Year: 2009

The degrees-of-freedom of a K-user Gaussian interference channel (GIFC) has been defined to be the multiple of (1/2)log_2(P) at which the maximum sum of achievable rates grows with increasing P. In this paper, we establish that the degrees-of-freedom of three or more user, real, scalar GIFCs, viewed as a function of the channel coefficients, is discontinuous at points where all of the coefficients are non-zero rational numbers. More specifically, for all K>2, we find a class of K-user GIFCs that is dense in the GIFC parameter space for which K/2 degrees-of-freedom are exactly achievable, and we show that the degrees-of-freedom for any GIFC with non-zero rational coefficients is strictly smaller than K/2. These results are proved using new connections with number theory and additive combinatorics.
A Tight Estimate for Decoding Error-Probability of LT Codes Using Kovalenko's Rank Distribution
Venue: arXiv cs.IT 2009
Year: 2009

A new approach for estimating the Decoding Error-Probability (DEP) of LT codes with dense rows is derived by using the conditional Kovalenko's rank distribution. The estimate by the proposed approach is very close to the DEP approximated by Gaussian Elimination, and is significantly less complex. As a key application, we utilize the estimates for obtaining optimal LT codes with dense rows, whose DEP is very close to the Kovalenko's Full-Rank Limit within a desired error-bound. Experimental evidences which show the viability of the estimates are also provided.
A Highly Nonlinear Differentially 4 Uniform Power Mapping That Permutes Fields of Even Degree
Venue: arXiv cs.IT 2009
Year: 2009

Functions with low differential uniformity can be used as the s-boxes of symmetric cryptosystems as they have good resistance to differential attacks. The AES (Advanced Encryption Standard) uses a differentially-4 uniform function called the inverse function. Any function used in a symmetric cryptosystem should be a permutation. Also, it is required that the function is highly nonlinear so that it is resistant to Matsui's linear attack. In this article we demonstrate that a highly nonlinear permutation discovered by Hans Dobbertin has differential uniformity of four and hence, with respect to differential and linear cryptanalysis, is just as suitable for use in a symmetric cryptosystem as the inverse function.
Binary Causal-Adversary Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x=(x_1,...,x_n) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits x_i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each bit x_i the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on x_j for j <= i. This is in contrast to the "classical" adversarial jammer which may base its decisions on its complete knowledge of x. We present a non-trivial upper bound on the amount of information that can be communicated. We show that the achievable rate can be asymptotically no greater than min{1-H(p),(1-4p)^+}. Here H(.) is the binary entropy function, and (1-4p)^+ equals 1-4p for p < 0.25, and 0 otherwise.
Belief Propagation Based Decoding of Large Non-Orthogonal STBCs
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we present a belief propagation (BP) based algorithm for decoding non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) having {\em large dimensions}. The proposed approach involves message passing on Markov random field (MRF) representation of the STBC MIMO system. Adoption of BP approach to decode non-orthogonal STBCs of large dimensions has not been reported so far. Our simulation results show that the proposed BP-based decoding achieves increasingly closer to SISO AWGN performance for increased number of dimensions. In addition, it also achieves near-capacity turbo coded BER performance; for e.g., with BP decoding of $24\times 24$ STBC from CDA using BPSK (i.e., 576 real dimensions) and rate-1/2 turbo code (i.e., 12 bps/Hz spectral efficiency), coded BER performance close to within just about 2.5 dB from the theoretical MIMO capacity is achieved.
Cooperative Multiplexing in the Multiple Antenna Half Duplex Relay Channel
Venue: arXiv cs.IT 2009
Year: 2009

Cooperation between terminals has been proposed to improve the reliability and throughput of wireless communication. While recent work has shown that relay cooperation provides increased diversity, increased multiplexing gain over that offered by direct link has largely been unexplored. In this work we show that cooperative multiplexing gain can be achieved by using a half duplex relay. We capture relative distances between terminals in the high SNR diversity multiplexing tradeoff (DMT) framework. The DMT performance is then characterized for a network having a single antenna half-duplex relay between a single-antenna source and two-antenna destination. Our results show that the achievable multiplexing gain using cooperation can be greater than that of the direct link and is a function of the relative distance between source and relay compared to the destination. Moreover, for multiplexing gains less than 1, a simple scheme of the relay listening 1/3 of the time and transmitting 2/3 of the time can achieve the 2 by 2 MIMO DMT.
Slepian-Wolf Coding over Cooperative Networks
Venue: arXiv cs.IT 2009
Year: 2009

We present sufficient conditions for multicasting a set of correlated sources over cooperative networks. We propose joint source-Wyner-Ziv encoding/sliding-window decoding scheme, in which each receiver considers an ordered partition of other nodes. Subject to this scheme, we obtain a set of feasibility constraints for each ordered partition. We consolidate the results of different ordered partitions by utilizing a result of geometrical approach to obtain the sufficient conditions. We observe that these sufficient conditions are indeed necessary conditions for Aref networks. As a consequence of the main result, we obtain an achievable rate region for networks with multicast demands. Also, we deduce an achievability result for two-way relay networks, in which two nodes want to communicate over a relay network.
On the Capacity of the Discrete-Time Channel with Uniform Output Quantization
Venue: arXiv cs.IT 2009
Year: 2009

This paper provides new insight into the classical problem of determining both the capacity of the discrete-time channel with uniform output quantization and the capacity achieving input distribution. It builds on earlier work by Gallager and Witsenhausen to provide a detailed analysis of two particular quantization schemes. The first is saturation quantization where overflows are mapped to the nearest quantization bin, and the second is wrapping quantization where overflows are mapped to the nearest quantization bin after reduction by some modulus. Both the capacity of wrapping quantization and the capacity achieving input distribution are determined. When the additive noise is gaussian and relatively small, the capacity of saturation quantization is shown to be bounded below by that of wrapping quantization. In the limit of arbitrarily many uniform quantization levels, it is shown that the difference between the upper and lower bounds on capacity given by Ihara is only 0.26 bits.
On the Delay Limited Secrecy Capacity of Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, the delay limited secrecy capacity of the flat fading channel is investigated under two different assumptions on the available transmitter channel state information (CSI). The first scenario assumes perfect prior knowledge of both the main and eavesdropper channel gains. Here, upper and lower bounds on the secure delay limited capacity are derived and shown to be tight in the high signal-to-noise ratio (SNR) regime (for a wide class of channel distributions). In the second scenario, only the main channel CSI is assumed to be available at the transmitter. Remarkably, under this assumption, we establish the achievability of non-zero secure rate (for a wide class of channel distributions) under a strict delay constraint. In the two cases, our achievability arguments are based on a novel two-stage approach that overcomes the secrecy outage phenomenon observed in earlier works.
A Density Matrix-based Algorithm for Solving Eigenvalue Problems
Venue: arXiv cs.CE 2009
Year: 2009

A new numerical algorithm for solving the symmetric eigenvalue problem is presented. The technique deviates fundamentally from the traditional Krylov subspace iteration based techniques (Arnoldi and Lanczos algorithms) or other Davidson-Jacobi techniques, and takes its inspiration from the contour integration and density matrix representation in quantum mechanics. It will be shown that this new algorithm - named FEAST - exhibits high efficiency, robustness, accuracy and scalability on parallel architectures. Examples from electronic structure calculations of Carbon nanotubes (CNT) are presented, and numerical performances and capabilities are discussed.
Self-stabilizing Numerical Iterative Computation
Venue: arXiv cs.NA 2009
Year: 2009

Many challenging tasks in sensor networks, including sensor calibration, ranking of nodes, monitoring, event region detection, collaborative filtering, collaborative signal processing, {\em etc.}, can be formulated as a problem of solving a linear system of equations. Several recent works propose different distributed algorithms for solving these problems, usually by using linear iterative numerical methods. The main problem with previous approaches is that once the problem inputs change during the process of computation, the computation may output unexpected results. In real life settings, sensor measurements are subject to varying environmental conditions and to measurement noise. We present a simple iterative scheme called SS-Iterative for solving systems of linear equations, and examine its properties in the self-stabilizing perspective. We analyze the behavior of the proposed scheme under changing input sequences using two different assumptions on the input: a box bound, and a probabilistic distribution. As a case study, we discuss the sensor calibration problem and provide simulation results to support the applicability of our approach.
Distributed Large Scale Network Utility Maximization
Venue: arXiv cs.IT 2009
Year: 2009

Recent work by Zymnis et al. proposes an efficient primal-dual interior-point method, using a truncated Newton method, for solving the network utility maximization (NUM) problem. This method has shown superior performance relative to the traditional dual-decomposition approach. Other recent work by Bickson et al. shows how to compute efficiently and distributively the Newton step, which is the main computational bottleneck of the Newton method, utilizing the Gaussian belief propagation algorithm. In the current work, we combine both approaches to create an efficient distributed algorithm for solving the NUM problem. Unlike the work of Zymnis, which uses a centralized approach, our new algorithm is easily distributed. Using an empirical evaluation we show that our new method outperforms previous approaches, including the truncated Newton method and dual-decomposition methods. As an additional contribution, this is the first work that evaluates the performance of the Gaussian belief propagation algorithm vs. the preconditioned conjugate gradient method, for a large scale problem.
Online validation of the pi and pi' failure functions
Venue: arXiv cs.DS 2009
Year: 2009

Let pi_w denote the failure function of the Morris-Pratt algorithm for a word w. In this paper we study the following problem: given an integer array A[1..n], is there a word w over arbitrary alphabet such that A[i]=pi_w[i] for all i? Moreover, what is the minimum required cardinality of the alphabet? We give a real time linear algorithm for this problem in the unit-cost RAM model with Θ(log n) bits word size. Our algorithm returns a word w over minimal alphabet such that pi_w = A as well and uses just o(n) words of memory. Then we consider function pi' instead of pi and give an online O(n log n) algorithm for this case. This is the first polynomial algorithm for online version of this problem.
Noisy DPC and Application to a Cognitive Channel
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we first consider a channel that is contaminated by two independent Gaussian noises $S ~ N(0,Q)$ and $Z_0 ~ N(0,N_0)$. The capacity of this channel is computed when independent noisy versions of $S$ are known to the transmitter and/or receiver. It is shown that the channel capacity is greater then the capacity when $S$ is completely unknown, but is less then the capacity when $S$ is perfectly known at the transmitter or receiver. For example, if there is one noisy version of $S$ known at the transmitter only, the capacity is $0.5log(1+P/(Q(N_1/(Q+N_1))+N_0))$, where $P$ is the input power constraint and $N_1$ is the power of the noise corrupting $S$. We then consider a Gaussian cognitive interference channel (IC) and propose a causal noisy dirty paper coding (DPC) strategy. We compute the achievable region using this noisy DPC strategy and quantify the regions when it achieves the upper bound on the rate.
Secure Communication in the Low-SNR Regime: A Characterization of the Energy-Secrecy Tradeoff
Venue: arXiv cs.IT 2009
Year: 2009

Secrecy capacity of a multiple-antenna wiretap channel is studied in the low signal-to-noise ratio (SNR) regime. Expressions for the first and second derivatives of the secrecy capacity with respect to SNR at SNR = 0 are derived. Transmission strategies required to achieve these derivatives are identified. In particular, it is shown that it is optimal in the low-SNR regime to transmit in the maximum-eigenvalue eigenspace of H_m* H_m - N_m/N_e H_e* H_e where H_m and H_e denote the channel matrices associated with the legitimate receiver and eavesdropper, respectively, and N_m and N_e are the noise variances at the receiver and eavesdropper, respectively. Energy efficiency is analyzed by finding the minimum bit energy required for secure and reliable communications, and the wideband slope. Increased bit energy requirements under secrecy constraints are quantified. Finally, the impact of fading is investigated.
Energy Efficiency of Fixed-Rate Wireless Transmissions under Queueing Constraints and Channel Uncertainty
Venue: arXiv cs.IT 2009
Year: 2009

Energy efficiency of fixed-rate transmissions is studied in the presence of queueing constraints and channel uncertainty. It is assumed that neither the transmitter nor the receiver has channel side information prior to transmission. The channel coefficients are estimated at the receiver via minimum mean-square-error (MMSE) estimation with the aid of training symbols. It is further assumed that the system operates under statistical queueing constraints in the form of limitations on buffer violation probabilities. The optimal fraction of of power allocated to training is identified. Spectral efficiency--bit energy tradeoff is analyzed in the low-power and wideband regimes by employing the effective capacity formulation. In particular, it is shown that the bit energy increases without bound in the low-power regime as the average power vanishes. On the other hand, it is proven that the bit energy diminishes to its minimum value in the wideband regime as the available bandwidth increases. For this case, expressions for the minimum bit energy and wideband slope are derived. Overall, energy costs of channel uncertainty and queueing constraints are identified.
A Low Density Lattice Decoder via Non-Parametric Belief Propagation
Venue: arXiv cs.IT 2009
Year: 2009

The recent work of Sommer, Feder and Shalvi presented a new family of codes called low density lattice codes (LDLC) that can be decoded efficiently and approach the capacity of the AWGN channel. A linear time iterative decoding scheme which is based on a message-passing formulation on a factor graph is given. In the current work we report our theoretical findings regarding the relation between the LDLC decoder and belief propagation. We show that the LDLC decoder is an instance of non-parametric belief propagation and further connect it to the Gaussian belief propagation algorithm. Our new results enable borrowing knowledge from the non-parametric and Gaussian belief propagation domains into the LDLC domain. Specifically, we give more general convergence conditions for convergence of the LDLC decoder (under the same assumptions of the original LDLC convergence analysis). We discuss how to extend the LDLC decoder from Latin square to full rank, non-square matrices. We propose an efficient construction of sparse generator matrix and its matching decoder. We report preliminary experimental results which show our decoder has comparable symbol to error rate compared to the original LDLC decoder.%
A Distributed Trust Diffusion Protocol for Ad Hoc Networks
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we propose and evaluate a distributed protocol to manage trust diffusion in ad hoc networks. In this protocol, each node i maintains a \trust value" about an other node j which is computed both as a result of the exchanges with node j itself and as a function of the opinion that other nodes have about j. These two aspects are respectively weighted by a trust index that measures the trust quality the node has in its own experiences and by a trust index representing the trust the node has in the opinions of the other nodes. Simulations have been realized to validate the robustness of this protocol against three kinds of attacks: simple coalitions, Trojan attacks and detonator attacks.
Sending a Bi-Variate Gaussian over a Gaussian MAC
Venue: arXiv cs.IT 2009
Year: 2009

We study the power versus distortion trade-off for the distributed transmission of a memoryless bi-variate Gaussian source over a two-to-one average-power limited Gaussian multiple-access channel. In this problem, each of two separate transmitters observes a different component of a memoryless bi-variate Gaussian source. The two transmitters then describe their source component to a common receiver via an average-power constrained Gaussian multiple-access channel. From the output of the multiple-access channel, the receiver wishes to reconstruct each source component with the least possible expected squared-error distortion. Our interest is in characterizing the distortion pairs that are simultaneously achievable on the two source components. We present sufficient conditions and necessary conditions for the achievability of a distortion pair. These conditions are expressed as a function of the channel signal-to-noise ratio (SNR) and of the source correlation. In several cases the necessary conditions and sufficient conditions are shown to agree. In particular, we show that if the channel SNR is below a certain threshold, then an uncoded transmission scheme is optimal. We also derive the precise high-SNR asymptotics of an optimal scheme.
Enterprise model verification and validation: an approach
Venue: arXiv cs.SE 2009
Year: 2009

This article presents a Verification and Validation approach which is used here in order to complete the classical tool box the industrial user may utilize in Enterprise Modeling and Integration domain. This approach, which has been defined independently from any application domain is based on several formal concepts and tools presented in this paper. These concepts are property concepts, property reference matrix, properties graphs, enterprise modeling domain ontology, conceptual graphs and formal reasoning mechanisms.
Capacity Scaling of Single-source Wireless Networks: Effect of Multiple Antennas
Venue: arXiv cs.IT 2009
Year: 2009

We consider a wireless network in which a single source node located at the center of a unit area having $m$ antennas transmits messages to $n$ randomly located destination nodes in the same area having a single antenna each. To achieve the sum-rate proportional to $m$ by transmit beamforming, channel state information (CSI) is essentially required at the transmitter (CSIT), which is hard to obtain in practice because of the time-varying nature of the channels and feedback overhead. We show that, even without CSIT, the achievable sum-rate scales as $Θ(m\log m)$ if a cooperation between receivers is allowed. By deriving the cut-set upper bound, we also show that $Θ(m\log m)$ scaling is optimal. Specifically, for $n=ω(m^2)$, the simple TDMA-based quantize-and-forward is enough to achieve the capacity scaling. For $n=ω(m)$ and $n=\operatorname{O}(m^2)$, on the other hand, we apply the hierarchical cooperation to achieve the capacity scaling.
Model-Based Event Detection in Wireless Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

In this paper we present an application of techniques from statistical signal processing to the problem of event detection in wireless sensor networks used for environmental monitoring. The proposed approach uses the well-established Principal Component Analysis (PCA) technique to build a compact model of the observed phenomena that is able to capture daily and seasonal trends in the collected measurements. We then use the divergence between actual measurements and model predictions to detect the existence of discrete events within the collected data streams. Our preliminary results show that this event detection mechanism is sensitive enough to detect the onset of rain events using the temperature modality of a wireless sensor network.