OpenRaiser/Intern-Atlas huggingface dataset:
Central Approximation in Statistical Physics and Information Theory
Venue: arXiv cs.IT 2012
Year: 2012

In statistical physics and information theory, although the exponent of the partition function is often of our primary interest, there are cases where one needs more detailed information. In this paper, we present a general framework to study more precise asymptotic behaviors of the partition function, using the central approximation in conjunction with the method of types.
Joint Coding and Scheduling Optimization in Wireless Systems with Varying Delay Sensitivities
Venue: arXiv cs.NI 2012
Year: 2012

Throughput and per-packet delay can present strong trade-offs that are important in the cases of delay sensitive applications.We investigate such trade-offs using a random linear network coding scheme for one or more receivers in single hop wireless packet erasure broadcast channels. We capture the delay sensitivities across different types of network applications using a class of delay metrics based on the norms of packet arrival times. With these delay metrics, we establish a unified framework to characterize the rate and delay requirements of applications and optimize system parameters. In the single receiver case, we demonstrate the trade-off between average packet delay, which we view as the inverse of throughput, and maximum ordered inter-arrival delay for various system parameters. For a single broadcast channel with multiple receivers having different delay constraints and feedback delays, we jointly optimize the coding parameters and time-division scheduling parameters at the transmitters. We formulate the optimization problem as a Generalized Geometric Program (GGP). This approach allows the transmitters to adjust adaptively the coding and scheduling parameters for efficient allocation of network resources under varying delay constraints. In the case where the receivers are served by multiple non-interfering wireless broadcast channels, the same optimization problem is formulated as a Signomial Program, which is NP-hard in general. We provide approximation methods using successive formulation of geometric programs and show the convergence of approximations.
A Compression Algorithm Using Mis-aligned Side-information
Venue: arXiv cs.IT 2012
Year: 2012

We study the problem of compressing a source sequence in the presence of side-information that is related to the source via insertions, deletions and substitutions. We propose a simple algorithm to compress the source sequence when the side-information is present at both the encoder and decoder. A key attribute of the algorithm is that it encodes the edits contained in runs of different extents separately. For small insertion and deletion probabilities, the compression rate of the algorithm is shown to be asymptotically optimal.
Channel Capacity under General Nonuniform Sampling
Venue: arXiv cs.IT 2012
Year: 2012

This paper develops the fundamental capacity limits of a sampled analog channel under a sub-Nyquist sampling rate constraint. In particular, we derive the capacity of sampled analog channels over a general class of time-preserving sampling methods including irregular nonuniform sampling. Our results indicate that the optimal sampling structures extract out the set of frequencies that exhibits the highest SNR among all spectral sets of support size equal to the sampling rate. The capacity under sub-Nyquist sampling can be attained through filter-bank sampling, or through a single branch of modulation and filtering followed by uniform sampling. The capacity under sub-Nyquist sampling is a monotone function of the sampling rate. These results indicate that the optimal sampling schemes suppress aliasing, and that employing irregular nonuniform sampling does not provide capacity gain over uniform sampling sets with appropriate preprocessing for a large class of channels.
A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs
Venue: arXiv cs.IT 2012
Year: 2012

The multicast capacity of a directed network is closely related to the $s$-$t$ maximum flow, which is equal to the $s$-$t$ minimum cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or have stochastic nature, it is not so trivial to predict statistical properties on the maximum flow. In this paper, we present a coding theoretic approach for evaluating the accumulate distribution of the minimum cut capacity of weighted random graphs. The main feature of our approach is to utilize the correspondence between the cut space of a graph and a binary LDGM (low-density generator-matrix) code with column weight 2. The graph ensemble treated in the paper is a weighted version of Erdős-Rényi random graph ensemble. The main contribution of our work is a combinatorial lower bound for the accumulate distribution of the minimum cut capacity. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum cut capacity.
The Capacity of the Semi-Deterministic Cognitive Interference Channel with a Common Cognitive Message and Approximate Capacity for the Gaussian Case
Venue: arXiv cs.IT 2012
Year: 2012

In this paper the study of the cognitive interference channel with a common message, a variation of the classical cognitive interference channel in which the cognitive message is decoded at both receivers. We derive the capacity for the semideterministic channel in which the output at the cognitive decoder is a deterministic function of the channel inputs. We also show capacity to within a constant gap and a constant factor for the Gaussian channel in which the outputs are linear combinations of the channel inputs plus an additive Gaussian noise term. Most of these results are shown using an interesting transmission scheme in which the cognitive message, decoded at both receivers, is also pre-coded against the interference experienced at the cognitive decoder. The pre-coding of the cognitive message does not allow the primary decoder to reconstruct the interfering signal. The cognitive message acts instead as a side information at the primary receiver when decoding its intended message.
Wavelets for Single Carrier Communications
Venue: arXiv cs.NI 2012
Year: 2012

This paper and the following presentation aim to provide a report regarding the seminar presentation given on 23.02.2011 as a part of the postgraduate seminar course S-88.4223 Wavelets in Communications lectured by Dr. Sumesh Parameswaran at Aalto University School of Electrical Engineering. In particular, the topic on "wavelets for single carrier communications" has been considered herein. Furthermore, a summary of wavelets in Single Carrier (SC)-FDMA Systems is as well provided.
Topological approach to solve P versus NP
Venue: arXiv cs.CC 2012
Year: 2012

This paper talks about difference between P and NP by using topological space that mean resolution principle. I pay attention to restrictions of antecedent and consequent in resolution, and show what kind of influence the restrictions have for difference of structure between P and NP regarding relations of relation. First, I show the restrictions of antecedent and consequent in resolution principle. Antecedents connect each other, and consequent become a linkage between these antecedents. And we can make consequent as antecedents product by using some resolutions which have same joint variable. We can determine these consequents reducible and irreducible. Second, I introduce RCNF that mean topology of resolution principle in CNF. RCNF is HornCNF and that variable values are presence of restrictions of CNF formula clauses. RCNF is P-Complete. Last, I introduce TCNF that have 3CNF's character which relate 2 variables relations with 1 variable. I show CNF complexity by using CCNF that combine some TCNF. TCNF is NP-Complete and product irreducible. I introduce CCNF that connect TCNF like Moore graph. We cannot reduce CCNF to RCNF with polynomial size. Therefore, TCNF is not in P.
Modification of the Elite Ant System in Order to Avoid Local Optimum Points in the Traveling Salesman Problem
Venue: arXiv cs.AI 2012
Year: 2012

This article presents a new algorithm which is a modified version of the elite ant system (EAS) algorithm. The new version utilizes an effective criterion for escaping from the local optimum points. In contrast to the classical EAC algorithms, the proposed algorithm uses only a global updating, which will increase pheromone on the edges of the best (i.e. the shortest) route and will at the same time decrease the amount of pheromone on the edges of the worst (i.e. the longest) route. In order to assess the efficiency of the new algorithm, some standard traveling salesman problems (TSPs) were studied and their results were compared with classical EAC and other well-known meta-heuristic algorithms. The results indicate that the proposed algorithm has been able to improve the efficiency of the algorithms in all instances and it is competitive with other algorithms.
A Rate-Compatible Sphere-Packing Analysis of Feedback Coding with Limited Retransmissions
Venue: arXiv cs.IT 2012
Year: 2012

Recent work by Polyanskiy et al. and Chen et al. has excited new interest in using feedback to approach capacity with low latency. Polyanskiy showed that feedback identifying the first symbol at which decoding is successful allows capacity to be approached with surprisingly low latency. This paper uses Chen's rate-compatible sphere-packing (RCSP) analysis to study what happens when symbols must be transmitted in packets, as with a traditional hybrid ARQ system, and limited to relatively few (six or fewer) incremental transmissions. Numerical optimizations find the series of progressively growing cumulative block lengths that enable RCSP to approach capacity with the minimum possible latency. RCSP analysis shows that five incremental transmissions are sufficient to achieve 92% of capacity with an average block length of fewer than 101 symbols on the AWGN channel with SNR of 2.0 dB. The RCSP analysis provides a decoding error trajectory that specifies the decoding error rate for each cumulative block length. Though RCSP is an idealization, an example tail-biting convolutional code matches the RCSP decoding error trajectory and achieves 91% of capacity with an average block length of 102 symbols on the AWGN channel with SNR of 2.0 dB. We also show how RCSP analysis can be used in cases where packets have deadlines associated with them (leading to an outage probability).
Message-Passing Algorithms for Channel Estimation and Decoding Using Approximate Inference
Venue: arXiv cs.IT 2012
Year: 2012

We design iterative receiver schemes for a generic wireless communication system by treating channel estimation and information decoding as an inference problem in graphical models. We introduce a recently proposed inference framework that combines belief propagation (BP) and the mean field (MF) approximation and includes these algorithms as special cases. We also show that the expectation propagation and expectation maximization algorithms can be embedded in the BP-MF framework with slight modifications. By applying the considered inference algorithms to our probabilistic model, we derive four different message-passing receiver schemes. Our numerical evaluation demonstrates that the receiver based on the BP-MF framework and its variant based on BP-EM yield the best compromise between performance, computational complexity and numerical stability among all candidate algorithms.
Coding With Action-dependent Side Information and Additional Reconstruction Requirements
Venue: arXiv cs.IT 2012
Year: 2012

Constrained lossy source coding and channel coding with side information problems which extend the classic Wyner-Ziv and Gel'fand-Pinsker problems are considered. Inspired by applications in sensor networking and control, we first consider lossy source coding with two-sided partial side information where the quality/availability of the side information can be influenced by a cost-constrained action sequence. A decoder reconstructs a source sequence subject to the distortion constraint, and at the same time, an encoder is additionally required to be able to estimate the decoder's reconstruction. Next, we consider the channel coding "dual" where the channel state is assumed to depend on the action sequence, and the decoder is required to decode both the transmitted message and channel input reliably. Implications on the fundamental limits of communication in discrete memoryless systems due to the additional reconstruction constraints are investigated. Single-letter expressions for the rate-distortion-cost function and channel capacity for the respective source and channel coding problems are derived. The dual relation between the two problems is discussed. Additionally, based on the two-stage coding structure and the additional reconstruction constraint of the channel coding problem, we discuss and give an interpretation of the two-stage coding condition which appears in the channel capacity expression. Besides the rate constraint on the message, this condition is a necessary and sufficient condition for reliable transmission of the channel input sequence over the channel in our "two-stage" communication problem. It is also shown in one example that there exists a case where the two-stage coding condition can be active in computing the capacity, and it thus can actively restrict the set of capacity achieving input distributions.
Singular Values using Cholesky Decomposition
Venue: arXiv cs.MS 2012
Year: 2012

In this paper two ways to compute singular values are presented which use Cholesky decomposition as their basic operation.
Efficient Query Verification on Outsourced Data: A Game-Theoretic Approach
Venue: arXiv cs.GT 2012
Year: 2012

To save time and money, businesses and individuals have begun outsourcing their data and computations to cloud computing services. These entities would, however, like to ensure that the queries they request from the cloud services are being computed correctly. In this paper, we use the principles of economics and competition to vastly reduce the complexity of query verification on outsourced data. We consider two cases: First, we consider the scenario where multiple non-colluding data outsourcing services exist, and then we consider the case where only a single outsourcing service exists. Using a game theoretic model, we show that given the proper incentive structure, we can effectively deter dishonest behavior on the part of the data outsourcing services with very few computational and monetary resources. We prove that the incentive for an outsourcing service to cheat can be reduced to zero. Finally, we show that a simple verification method can achieve this reduction through extensive experimental evaluation.
Classification with High-Dimensional Sparse Samples
Venue: arXiv cs.IT 2012
Year: 2012

The task of the binary classification problem is to determine which of two distributions has generated a length-$n$ test sequence. The two distributions are unknown; two training sequences of length $N$, one from each distribution, are observed. The distributions share an alphabet of size $m$, which is significantly larger than $n$ and $N$. How does $N,n,m$ affect the probability of classification error? We characterize the achievable error rate in a high-dimensional setting in which $N,n,m$ all tend to infinity, under the assumption that probability of any symbol is $O(m^{-1})$. The results are: 1. There exists an asymptotically consistent classifier if and only if $m=o(\min\{N^2,Nn\})$. This extends the previous consistency result in [1] to the case $N\neq n$. 2. For the sparse sample case where $\max\{n,N\}=o(m)$, finer results are obtained: The best achievable probability of error decays as $-\log(P_e)=J \min\{N^2, Nn\}(1+o(1))/m$ with $J>0$. 3. A weighted coincidence-based classifier has non-zero generalized error exponent $J$. 4. The $\ell_2$-norm based classifier has J=0.
Combined Haar-Hilbert and Log-Gabor Based Iris Encoders
Venue: arXiv cs.CV 2012
Year: 2012

This chapter shows that combining Haar-Hilbert and Log-Gabor improves iris recognition performance leading to a less ambiguous biometric decision landscape in which the overlap between the experimental intra- and interclass score distributions diminishes or even vanishes. Haar-Hilbert, Log-Gabor and combined Haar-Hilbert and Log-Gabor encoders are tested here both for single and dual iris approach. The experimental results confirm that the best performance is obtained for the dual iris approach when the iris code is generated using the combined Haar-Hilbert and Log-Gabor encoder, and when the matching score fuses the information from both Haar-Hilbert and Log-Gabor channels of the combined encoder.
A family of weakly universal cellular automata in the hyperbolic plane with two states
Venue: arXiv cs.FL 2012
Year: 2012

In this paper, we construct a family of weakly universal rotation invariant cellular automaton for all grids $\{p,3\}$ of the hyperbolic plane for $p\geq 13$. The scheme is general for $p\geq 17$ and for $13\leq p<17$, we give such a cellular automaton for $p=13$, which is enough. Also, an important property of this family is that the set of cells of the cellular automaton which are subject to changes is actually a planar set. The problem for $p<13$ for a truly planar construction is still open. The best result, for $p=7$, is four states and was obtained by the same author.
Improve the Practice of Software Development in India by Having a Software Development Career Track in Indian CS & IT Academia
Venue: arXiv cs.CY 2012
Year: 2012

Many, but not all, Indian CS & IT academics tend to have a focus on theory and research. They do not give much importance to the practice of software development. This paper proposes an additional software development career track for Indian CS & IT academics different from the existing research oriented career track. A measure of software contribution record is suggested. It opines that adoption of such changes to academic regulations will result in significant improvement of software development skill set in Indian CS & IT academia which, in turn, will result in better software development skill set in Indian CS & IT graduates.
Performance evaluation aodv, dymo, olsr and zrpad hoc routing protocol for ieee 802.11 mac and 802.11 dcf in vanet using qualnet
Venue: arXiv cs.NI 2012
Year: 2012

In VANET high speed is the real characteristics which leads to frequent breakdown, interference etc. Therefore Performance of adhoc routing protocols is helpful to improve the Quality of Service (QOS). In this paper we studied various adhoc routing protocols, Reactive, Proactive & Hybrid, taking in to consideration parameters like speed, altitude, mobility etc in real VANET scenario. The AODV and DYMO (Reactive), OLSR (Proactive) and ZRP (hybrid) protocols are compared for IEEE 802.11(MAC) and IEEE 802.11(DCF) standard using Qualnet as a Simulation tool. Since IEEE 802.11, covers both physical and data link layer. Hence performance of the protocols in these layers helps to make a right selection of Protocol for high speed mobility. Varying parameters of VANET shows that in the real traffic scenarios proactive protocol performs more efficiently for IEEE 802.11 (MAC) and IEEE 802.11(DCF).
Superiority of TDMA in a Class of Gaussian Multiple-Access Channels with a MIMO-AF-Relay
Venue: arXiv cs.IT 2012
Year: 2012

We consider a Gaussian multiple-access channel (MAC) with an amplify-and-forward (AF) relay, where all nodes except the receiver have multiple antennas and the direct links between transmitters and receivers are neglected. Thus, spatial processing can be applied both at the transmitters and at the relay, which is subject to optimization for increasing the data rates. In general, this optimization problem is non-convex and hard to solve. While in prior work on this problem, it is assumed that all transmitters access the channel jointly, we propose a solution where each transmitter accesses the channel exclusively, using a time-division multiple-access (TDMA) scheme. It is shown that this scheme provides higher achievable sum rates, which raises the question of the need for TDMA to achieve the general capacity region of MACs with AF relay.
A Diversity-Multiplexing-Delay Tradeoff of ARQ Protocols in The Z-interference Channel
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we analyze the fundamental performance tradeoff of the single-antenna Automatic Retransmission reQuest (ARQ) Z-interference channel (ZIC). Specifically, we characterize the achievable three-dimensional tradeoff between diversity (reliability), multiplexing (throughput), and delay (maximum number of retransmissions) of two ARQ protocols: A non-cooperative protocol and a cooperative one. Considering no cooperation exists, we study the achievable tradeoff of the fixed-power split Han-Kobayashi (HK) approach. Interestingly, we demonstrate that if the second user transmits the common part only of its message in the event of its successful decoding and a decoding failure at the first user, communication is improved over that achieved by keeping or stopping the transmission of both the common and private messages. We obtain closed-form expressions for the achievable tradeoff under the HK splitting. Under cooperation, two special cases of the HK are considered for static and dynamic decoders. The difference between the two decoders lies in the ability of the latter to dynamically choose which HK special-case decoding to apply. Cooperation is shown to dramatically increase the achievable first user diversity.
Cross-point architecture for spin transfer torque magnetic random access memory
Venue: arXiv cs.ET 2012
Year: 2012

Spin transfer torque magnetic random access memory (STT-MRAM) is considered as one of the most promising candidates to build up a true universal memory thanks to its fast write/read speed, infinite endurance and non-volatility. However the conventional access architecture based on 1 transistor + 1 memory cell limits its storage density as the selection transistor should be large enough to ensure the write current higher than the critical current for the STT operation. This paper describes a design of cross-point architecture for STT-MRAM. The mean area per word corresponds to only two transistors, which are shared by a number of bits (e.g. 64). This leads to significant improvement of data density (e.g. 1.75 F2/bit). Special techniques are also presented to address the sneak currents and low speed issues of conventional cross-point architecture, which are difficult to surmount and few efficient design solutions have been reported in the literature. By using a STT-MRAM SPICE model including precise experimental parameters and STMicroelectronics 65 nm technology, some chip characteristic results such as cell area, data access speed and power have been calculated or simulated to demonstrate the expected performances of this new memory architecture.
Global Maps of Science based on the new Web-of-Science Categories
Venue: arXiv cs.DL 2012
Year: 2012

In August 2011, Thomson Reuters launched version 5 of the Science and Social Science Citation Index in the Web of Science (WoS). Among other things, the 222 ISI Subject Categories (SCs) for these two databases in version 4 of WoS were renamed and extended to 225 WoS Categories (WCs). A new set of 151 Subject Categories (SCs) was added, but at a higher level of aggregation. Since we previously used the ISI SCs as the baseline for a global map in Pajek (Rafols et al., 2010) and brought this facility online (at http://www.leydesdorff.net/overlaytoolkit), we recalibrated this map for the new WC categories using the Journal Citation Reports 2010. In the new installation, the base maps can also be made using VOSviewer (Van Eck & Waltman, 2010).