OpenRaiser/Intern-Atlas huggingface dataset:
Pareto Region Characterization for Rate Control in Multi-User Systems and Nash Bargaining
Venue: arXiv cs.GT 2010
Year: 2010

The problem of rate control in multi-user multiple-input multiple-output (MIMO) interference systems is formulated as a multicriteria optimization (MCO) problem. The Pareto rate region of the MCO problem is characterized. It is shown that for the convexity of the Pareto rate region it is sufficient that the interference-plus-noise covariance matrices (INCMs) of multiple users with conflicting objectives approach identity matrix. The latter can be achieved by using either orthogonal signaling, time-sharing, or interference cancellation strategies. In the case of high interference, the interference cancellation is preferable in order to increase the Pareto boundary and guarantee the convexity of the Pareto rate region. The Nash bargaining (NB) is applied to transform the MCO problem into a single-objective one. The characteristics of the NB over MIMO interference systems such as the uniqueness, existence of the NB solution, and feasibility of the NB set are investigated. When the NB solution exists, the sufficient condition for the corresponding single-objective problem to have a unique solution is that the INCMs of users approach identity matrix. A simple multi-stage interference cancellation scheme, which leads to a larger convex Pareto rate region and, correspondingly, a unique NB solution with larger user rates compared to the orthogonal and time-sharing signaling schemes, is proposed. The convexity of the rate region, effectiveness of the proposed interference cancellation technique, and existence of the NB solution for MIMO interference systems are examined by means of numerical studies. The fairness of the NB solution is also demonstrated. Finally, the special cases of multi-input single-output (MISO) and single-input single-output (SISO) interference systems are also considered.
On Regret of Parametric Mismatch in Minimum Mean Square Error Estimation
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies the effect of parametric mismatch in minimum mean square error (MMSE) estimation. In particular, we consider the problem of estimating the input signal from the output of an additive white Gaussian channel whose gain is fixed, but unknown. The input distribution is known, and the estimation process consists of two algorithms. First, a channel estimator blindly estimates the channel gain using past observations. Second, a mismatched MMSE estimator, optimized for the estimated channel gain, estimates the input signal. We analyze the regret, i.e., the additional mean square error, that is raised in this process. We derive upper-bounds on both absolute and relative regrets. Bounds are expressed in terms of the Fisher information. We also study regret for unbiased, efficient channel estimators, and derive a simple trade-off between Fisher information and relative regret. This trade-off shows that the product of a certain function of relative regret and Fisher information equals the signal-to-noise ratio, independent of the input distribution. The trade-off relation implies that higher Fisher information results to smaller expected relative regret.
Discounting in Games across Time Scales
Venue: arXiv cs.LO 2010
Year: 2010

We introduce two-level discounted games played by two players on a perfect-information stochastic game graph. The upper level game is a discounted game and the lower level game is an undiscounted reachability game. Two-level games model hierarchical and sequential decision making under uncertainty across different time scales. We show the existence of pure memoryless optimal strategies for both players and an ordered field property for such games. We show that if there is only one player (Markov decision processes), then the values can be computed in polynomial time. It follows that whether the value of a player is equal to a given rational constant in two-level discounted games can be decided in NP intersected coNP. We also give an alternate strategy improvement algorithm to compute the value.
Playing Muller Games in a Hurry
Venue: arXiv cs.GT 2010
Year: 2010

This work studies the following question: can plays in a Muller game be stopped after a finite number of moves and a winner be declared. A criterion to do this is sound if Player 0 wins an infinite-duration Muller game if and only if she wins the finite-duration version. A sound criterion is presented that stops a play after at most 3^n moves, where n is the size of the arena. This improves the bound (n!+1)^n obtained by McNaughton and the bound n!+1 derived from a reduction to parity games.
Formats of Winning Strategies for Six Types of Pushdown Games
Venue: arXiv cs.GT 2010
Year: 2010

The solution of parity games over pushdown graphs (Walukiewicz '96) was the first step towards an effective theory of infinite-state games. It was shown that winning strategies for pushdown games can be implemented again as pushdown automata. We continue this study and investigate the connection between game presentations and winning strategies in altogether six cases of game arenas, among them realtime pushdown systems, visibly pushdown systems, and counter systems. In four cases we show by a uniform proof method that we obtain strategies implementable by the same type of pushdown machine as given in the game arena. We prove that for the two remaining cases this correspondence fails. In the conclusion we address the question of an abstract criterion that explains the results.
Equilibrium and Termination
Venue: arXiv cs.LO 2010
Year: 2010

We present a reduction of the termination problem for a Turing machine (in the simplified form of the Post correspondence problem) to the problem of determining whether a continuous-time Markov chain presented as a set of Kappa graph-rewriting rules has an equilibrium. It follows that the problem of whether a computable CTMC is dissipative (ie does not have an equilibrium) is undecidable.
Distortion Outage Probability in MIMO Block-Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

We study analogue source transmission over MIMO block-fading channels with receiver-only channel state information. Unlike previous work which considers the end-to-end expected distortion as a figure of merit, we study the distortion outage probability. We first consider the well known transmitter informed bound, which yields a benchmark lower bound to the distortion outage probability of any coding scheme. We next compare the results with source-channel separation. The key difference from the expected distortion approach is that if the channel code rate is chosen appropriately, source-channel separation can not only achieve the same diversity exponent, but also the same distortion outage probability as the transmitter informed lower bound.
The DCA:SOMe Comparison A comparative study between two biologically-inspired algorithms
Venue: arXiv cs.AI 2010
Year: 2010

The Dendritic Cell Algorithm (DCA) is an immune-inspired algorithm, developed for the purpose of anomaly detection. The algorithm performs multi-sensor data fusion and correlation which results in a 'context aware' detection system. Previous applications of the DCA have included the detection of potentially malicious port scanning activity, where it has produced high rates of true positives and low rates of false positives. In this work we aim to compare the performance of the DCA and of a Self-Organizing Map (SOM) when applied to the detection of SYN port scans, through experimental analysis. A SOM is an ideal candidate for comparison as it shares similarities with the DCA in terms of the data fusion method employed. It is shown that the results of the two systems are comparable, and both produce false positives for the same processes. This shows that the DCA can produce anomaly detection results to the same standard as an established technique.
The Motif Tracking Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper we introduce the Motif Tracking Algorithm, a novel immune inspired pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilisation of an intuitive symbolic representation. The resulting population of motifs is shown to have considerable potential value for other applications such as forecasting and algorithm seeding.
Tree-structure Expectation Propagation for Decoding LDPC codes over Binary Erasure Channels
Venue: arXiv cs.IT 2010
Year: 2010

Expectation Propagation is a generalization to Belief Propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pair-wise marginal distribution constraints in some check nodes of the LDPC Tanner graph. These additional constraints allow decoding the received codeword when the BP decoder gets stuck. In this paper, we first present the new decoding algorithm, whose complexity is identical to the BP decoder, and we then prove that it is able to decode codewords with a larger fraction of erasures, as the block size tends to infinity. The proposed algorithm can be also understood as a simplification of the Maxwell decoder, but without its computational complexity. We also illustrate that the new algorithm outperforms the BP decoder for finite block-size
EcoHomeHelper: An Expert System to Empower End-Users in Climate Change Action
Venue: arXiv cs.CY 2010
Year: 2010

Climate change has been a popular topic for a number of years now. Computer Science has contributed to aiding humanity in reducing energy requirements and consequently global warming. Much of this work is through calculators which determine a user's carbon footprint. However there are no expert systems which can offer advice in an efficient and time saving way. There are many publications which do offer advice on reducing greenhouse gas (GHG) emissions but to find the advice the reader seeks will involve reading a lot of irrelevant material. This work built an expert system (which we call EcoHomeHelper) and attempted to show that it is useful in changing people's behaviour with respect to their GHG emissions and that they will be able to find the information in a more efficient manner. Twelve participants were used. Seven of which used the program and five who read and attempted to find advice by reading from a list. The application itself has current implementations and the concept further developed, has applications for the future.
Information Theory and Statistical Physics - Lecture Notes
Venue: arXiv cs.IT 2010
Year: 2010

This document consists of lecture notes for a graduate course, which focuses on the relations between Information Theory and Statistical Physics. The course is aimed at EE graduate students in the area of Communications and Information Theory, as well as to graduate students in Physics who have basic background in Information Theory. Strong emphasis is given to the analogy and parallelism between Information Theory and Statistical Physics, as well as to the insights, the analysis tools and techniques that can be borrowed from Statistical Physics and `imported' to certain problem areas in Information Theory. This is a research trend that has been very active in the last few decades, and the hope is that by exposing the student to the meeting points between these two disciplines, we will enhance his/her background and perspective to carry out research in the field. A short outline of the course is as follows: Introduction; Elementary Statistical Physics and its Relation to Information Theory; Analysis Tools in Statistical Physics; Systems of Interacting Particles and Phase Transitions; The Random Energy Model (REM) and Random Channel Coding; Additional Topics (optional).
Information-theoretic Capacity of Clustered Random Networks
Venue: arXiv cs.IT 2010
Year: 2010

We analyze the capacity scaling laws of clustered ad hoc networks in which nodes are distributed according to a doubly stochastic shot-noise Cox process. We identify five different operational regimes, and for each regime we devise a communication strategy that allows to achieve a throughput to within a poly-logarithmic factor (in the number of nodes) of the maximum theoretical capacity.
Object-oriented modelling with unified modelling language 2.0 for simple software application based on agile methodology
Venue: arXiv cs.SE 2010
Year: 2010

Unified modelling language (UML) 2.0 introduced in 2002 has been developing and influencing object-oriented software engineering and has become a standard and reference for information system analysis and design modelling. There are many concepts and theories to model the information system or software application with UML 2.0, which can make ambiguities and inconsistencies for a novice to learn to how to model the system with UML especially with UML 2.0. This article will discuss how to model the simple software application by using some of the diagrams of UML 2.0 and not by using the whole diagrams as suggested by agile methodology. Agile methodology is considered as convenient for novices because it can deliver the information technology environment to the end-user quickly and adaptively with minimal documentation. It also has the ability to deliver best performance software application according to the customer's needs. Agile methodology will make simple model with simple documentation, simple team and simple tools.
Indonesian Earthquake Decision Support System
Venue: arXiv cs.AI 2010
Year: 2010

Earthquake DSS is an information technology environment which can be used by government to sharpen, make faster and better the earthquake mitigation decision. Earthquake DSS can be delivered as E-government which is not only for government itself but in order to guarantee each citizen's rights for education, training and information about earthquake and how to overcome the earthquake. Knowledge can be managed for future use and would become mining by saving and maintain all the data and information about earthquake and earthquake mitigation in Indonesia. Using Web technology will enhance global access and easy to use. Datawarehouse as unNormalized database for multidimensional analysis will speed the query process and increase reports variation. Link with other Disaster DSS in one national disaster DSS, link with other government information system and international will enhance the knowledge and sharpen the reports.
Algebraic Attack on the Alternating Step(r,s)Generator
Venue: arXiv cs.CR 2010
Year: 2010

The Alternating Step(r,s) Generator, ASG(r,s), is a clock-controlled sequence generator which is recently proposed by A. Kanso. It consists of three registers of length l, m and n bits. The first register controls the clocking of the two others. The two other registers are clocked r times (or not clocked) (resp. s times or not clocked) depending on the clock-control bit in the first register. The special case r=s=1 is the original and well known Alternating Step Generator. Kanso claims there is no efficient attack against the ASG(r,s) since r and s are kept secret. In this paper, we present an Alternating Step Generator, ASG, model for the ASG(r,s) and also we present a new and efficient algebraic attack on ASG(r,s) using 3(m+n) bits of the output sequence to find the secret key with O((m^2+n^2)*2^{l+1}+ (2^{m-1})*m^3 + (2^{n-1})*n^3) computational complexity. We show that this system is no more secure than the original ASG, in contrast to the claim of the ASG(r,s)'s constructor.
Optimal Power Allocation for GSVD-Based Beamforming in the MIMO Wiretap Channel
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers a multiple-input multiple-output (MIMO) Gaussian wiretap channel model, where there exists a transmitter, a legitimate receiver and an eavesdropper, each equipped with multiple antennas. Perfect secrecy is achieved when the transmitter and the legitimate receiver can communicate at some positive rate, while ensuring that the eavesdropper gets zero bits of information. In this paper, the perfect secrecy capacity of the multiple antenna MIMO wiretap channel is found for aribtrary numbers of antennas under the assumption that the transmitter performs beamforming based on the generalized singular value decomposition (GSVD). More precisely, the optimal allocation of power for the GSVD-based precoder that achieves the secrecy capacity is derived. This solution is shown to have several advantages over prior work that considered secrecy capacity for the general MIMO Gaussian wiretap channel under a high SNR assumption. Numerical results are presented to illustrate the proposed theoretical findings.
An entropy inequality for q-ary random variables and its application to channel polarization
Venue: arXiv cs.IT 2010
Year: 2010

It is shown that given two copies of a q-ary input channel $W$, where q is prime, it is possible to create two channels $W^-$ and $W^+$ whose symmetric capacities satisfy $I(W^-)\le I(W)\le I(W^+)$, where the inequalities are strict except in trivial cases. This leads to a simple proof of channel polarization in the q-ary case.
A Geometric Approach to Low-Rank Matrix Completion
Venue: arXiv cs.IT 2010
Year: 2010

The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise search procedures with provable performance guarantees for a broad class of matrix models. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence or large matrix size.
Multi-Cell MIMO Downlink with Cell Cooperation and Fair Scheduling: a Large-System Limit Analysis
Venue: arXiv cs.IT 2010
Year: 2010

We consider the downlink of a cellular network with multiple cells and multi-antenna base stations, including a realistic distance-dependent pathloss model, clusters of cooperating cells, and general "fairness" requirements. Beyond Monte Carlo simulation, no efficient computation method to evaluate the ergodic throughput of such systems has been presented so far. We propose an analytic solution based on the combination of large random matrix results and convex optimization. The proposed method is computationally much more efficient than Monte Carlo simulation and provides surprisingly accurate approximations for the actual finite-dimensional systems, even for a small number of users and base station antennas. Numerical examples include 2-cell linear and three-sectored 7-cell planar layouts, with no inter-cell cooperation, sector cooperation, or full inter-cell cooperation.
Highly Parallel Sparse Matrix-Matrix Multiplication
Venue: arXiv cs.DC 2010
Year: 2010

Generalized sparse matrix-matrix multiplication is a key primitive for many high performance graph algorithms as well as some linear solvers such as multigrid. We present the first parallel algorithms that achieve increasing speedups for an unbounded number of processors. Our algorithms are based on two-dimensional block distribution of sparse matrices where serial sections use a novel hypersparse kernel for scalability. We give a state-of-the-art MPI implementation of one of our algorithms. Our experiments show scaling up to thousands of processors on a variety of test scenarios.
Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
Venue: arXiv cs.IT 2010
Year: 2010

We describe a new algorithm, termed subspace evolution and transfer (SET), for solving low-rank matrix completion problems. The algorithm takes as its input a subset of entries of a low-rank matrix, and outputs one low-rank matrix consistent with the given observations. The completion task is accomplished by searching for a column space on the Grassmann manifold that matches the incomplete observations. The SET algorithm consists of two parts -- subspace evolution and subspace transfer. In the evolution part, we use a gradient descent method on the Grassmann manifold to refine our estimate of the column space. Since the gradient descent algorithm is not guaranteed to converge, due to the existence of barriers along the search path, we design a new mechanism for detecting barriers and transferring the estimated column space across the barriers. This mechanism constitutes the core of the transfer step of the algorithm. The SET algorithm exhibits excellent empirical performance for both high and low sampling rate regimes.
MDPs with Unawareness
Venue: arXiv cs.AI 2010
Year: 2010

Markov decision processes (MDPs) are widely used for modeling decision-making problems in robotics, automated control, and economics. Traditional MDPs assume that the decision maker (DM) knows all states and actions. However, this may not be true in many situations of interest. We define a new framework, MDPs with unawareness (MDPUs) to deal with the possibilities that a DM may not be aware of all possible actions. We provide a complete characterization of when a DM can learn to play near-optimally in an MDPU, and give an algorithm that learns to play near-optimally when it is possible to do so, as efficiently as possible. In particular, we characterize when a near-optimal solution can be found in polynomial time.
Advanced Software Protection Now
Venue: arXiv cs.CR 2010
Year: 2010

Software digital rights management is a pressing need for the software development industry which remains, as no practical solutions have been acclamaimed succesful by the industry. We introduce a novel software-protection method, fully implemented with today's technologies, that provides traitor tracing and license enforcement and requires no additional hardware nor inter-connectivity. Our work benefits from the use of secure triggers, a cryptographic primitive that is secure assuming the existence of an ind-cpa secure block cipher. Using our framework, developers may insert license checks and fingerprints, and obfuscate the code using secure triggers. As a result, this rises the cost that software analysis tools have detect and modify protection mechanisms. Thus rising the complexity of cracking this system.