OpenRaiser/Intern-Atlas huggingface dataset:
Massive MIMO Systems with Non-Ideal Hardware: Energy Efficiency, Estimation, and Capacity Limits
Venue: arXiv cs.IT 2014
Year: 2014

The use of large-scale antenna arrays can bring substantial improvements in energy and/or spectral efficiency to wireless systems due to the greatly improved spatial resolution and array gain. Recent works in the field of massive multiple-input multiple-output (MIMO) show that the user channels decorrelate when the number of antennas at the base stations (BSs) increases, thus strong signal gains are achievable with little inter-user interference. Since these results rely on asymptotics, it is important to investigate whether the conventional system models are reasonable in this asymptotic regime. This paper considers a new system model that incorporates general transceiver hardware impairments at both the BSs (equipped with large antenna arrays) and the single-antenna user equipments (UEs). As opposed to the conventional case of ideal hardware, we show that hardware impairments create finite ceilings on the channel estimation accuracy and on the downlink/uplink capacity of each UE. Surprisingly, the capacity is mainly limited by the hardware at the UE, while the impact of impairments in the large-scale arrays vanishes asymptotically and inter-user interference (in particular, pilot contamination) becomes negligible. Furthermore, we prove that the huge degrees of freedom offered by massive MIMO can be used to reduce the transmit power and/or to tolerate larger hardware impairments, which allows for the use of inexpensive and energy-efficient antenna elements.
Non-Elitist Genetic Algorithm as a Local Search Method
Venue: arXiv cs.NE 2014
Year: 2014

Sufficient conditions are found under which the iterated non-elitist genetic algorithm with tournament selection first visits a local optimum in polynomially bounded time on average. It is shown that these conditions are satisfied on a class of problems with guaranteed local optima (GLO) if appropriate parameters of the algorithm are chosen.
Verifying Time Complexity of Deterministic Turing Machines
Venue: arXiv cs.LO 2014
Year: 2014

We show that, for all reasonable functions $T(n)=o(n\log n)$, we can algorithmically verify whether a given one-tape Turing machine runs in time at most $T(n)$. This is a tight bound on the order of growth for the function $T$ because we prove that, for $T(n)\geq(n+1)$ and $T(n)=Ω(n\log n)$, there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most $T(n)$. We give results also for the case of multi-tape Turing machines. We show that we can verify whether a given multi-tape Turing machine runs in time at most $T(n)$ iff $T(n_0)< (n_0+1)$ for some $n_0\in\mathbb{N}$. We prove a very general undecidability result stating that, for any class of functions $\mathcal{F}$ that contains arbitrary large constants, we cannot verify whether a given Turing machine runs in time $T(n)$ for some $T\in\mathcal{F}$. In particular, we cannot verify whether a Turing machine runs in constant, polynomial or exponential time.
Uplink Linear Receivers for Multi-cell Multiuser MIMO with Pilot Contamination: Large System Analysis
Venue: arXiv cs.IT 2014
Year: 2014

Base stations with a large number of transmit antennas have the potential to serve a large number of users at high rates. However, the receiver processing in the uplink relies on channel estimates which are known to suffer from pilot interference. In this work, making use of the similarity of the uplink received signal in CDMA with that of a multi-cell multi-antenna system, we perform a large system analysis when the receiver employs an MMSE filter with a pilot contaminated estimate. We assume a Rayleigh fading channel with different received powers from users. We find the asymptotic Signal to Interference plus Noise Ratio (SINR) as the number of antennas and number of users per base station grow large while maintaining a fixed ratio. Through the SINR expression we explore the scenario where the number of users being served are comparable to the number of antennas at the base station. The SINR explicitly captures the effect of pilot contamination and is found to be the same as that employing a matched filter with a pilot contaminated estimate. We also find the exact expression for the interference suppression obtained using an MMSE filter which is an important factor when there are significant number of users in the system as compared to the number of antennas. In a typical set up, in terms of the five percentile SINR, the MMSE filter is shown to provide significant gains over matched filtering and is within 5 dB of MMSE filter with perfect channel estimate. Simulation results for achievable rates are close to large system limits for even a 10-antenna base station with 3 or more users per cell.
Enabling Complexity-Performance Trade-Offs for Successive Cancellation Decoding of Polar Codes
Venue: arXiv cs.IT 2014
Year: 2014

Polar codes are one of the most recent advancements in coding theory and they have attracted significant interest. While they are provably capacity achieving over various channels, they have seen limited practical applications. Unfortunately, the successive nature of successive cancellation based decoders hinders fine-grained adaptation of the decoding complexity to design constraints and operating conditions. In this paper, we propose a systematic method for enabling complexity-performance trade-offs by constructing polar codes based on an optimization problem which minimizes the complexity under a suitably defined mutual information based performance constraint. Moreover, a low-complexity greedy algorithm is proposed in order to solve the optimization problem efficiently for very large code lengths.
Random Binary Mappings for Kernel Learning and Efficient SVM
Venue: arXiv cs.CV 2014
Year: 2014

Support Vector Machines (SVMs) are powerful learners that have led to state-of-the-art results in various computer vision problems. SVMs suffer from various drawbacks in terms of selecting the right kernel, which depends on the image descriptors, as well as computational and memory efficiency. This paper introduces a novel kernel, which serves such issues well. The kernel is learned by exploiting a large amount of low-complex, randomized binary mappings of the input feature. This leads to an efficient SVM, while also alleviating the task of kernel selection. We demonstrate the capabilities of our kernel on 6 standard vision benchmarks, in which we combine several common image descriptors, namely histograms (Flowers17 and Daimler), attribute-like descriptors (UCI, OSR, and a-VOC08), and Sparse Quantization (ImageNet). Results show that our kernel learning adapts well to the different descriptors types, achieving the performance of the kernels specifically tuned for each image descriptor, and with similar evaluation cost as efficient SVM methods.
Dimension Reduction via Colour Refinement
Venue: arXiv cs.DS 2014
Year: 2014

Colour refinement is a basic algorithmic routine for graph isomorphism testing, appearing as a subroutine in almost all practical isomorphism solvers. It partitions the vertices of a graph into "colour classes" in such a way that all vertices in the same colour class have the same number of neighbours in every colour class. Tinhofer (Disc. App. Math., 1991), Ramana, Scheinerman, and Ullman (Disc. Math., 1994) and Godsil (Lin. Alg. and its App., 1997) established a tight correspondence between colour refinement and fractional isomorphisms of graphs, which are solutions to the LP relaxation of a natural ILP formulation of graph isomorphism. We introduce a version of colour refinement for matrices and extend existing quasilinear algorithms for computing the colour classes. Then we generalise the correspondence between colour refinement and fractional automorphisms and develop a theory of fractional automorphisms and isomorphisms of matrices. We apply our results to reduce the dimensions of systems of linear equations and linear programs. Specifically, we show that any given LP L can efficiently be transformed into a (potentially) smaller LP L' whose number of variables and constraints is the number of colour classes of the colour refinement algorithm, applied to a matrix associated with the LP. The transformation is such that we can easily (by a linear mapping) map both feasible and optimal solutions back and forth between the two LPs. We demonstrate empirically that colour refinement can indeed greatly reduce the cost of solving linear programs.
Beyond the entropy power inequality, via rearrangements
Venue: arXiv cs.IT 2014
Year: 2014

A lower bound on the Rényi differential entropy of a sum of independent random vectors is demonstrated in terms of rearrangements. For the special case of Boltzmann-Shannon entropy, this lower bound is better than that given by the entropy power inequality. Several applications are discussed, including a new proof of the classical entropy power inequality and an entropy inequality involving symmetrization of Lévy processes.
Secrecy Wireless Information and Power Transfer with MISO Beamforming
Venue: arXiv cs.IT 2014
Year: 2014

The dual use of radio signals for simultaneous wireless information and power transfer (SWIPT) has recently drawn significant attention. To meet the practical requirement that energy receivers (ERs) operate with significantly higher received power as compared to information receivers (IRs), ERs need to be deployed in more proximity to the transmitter than IRs. However, due to the broadcast nature of wireless channels, one critical issue arises that the messages sent to IRs can be eavesdropped by ERs, which possess better channels from the transmitter. In this paper, we address this new secrecy communication problem in a multiuser multiple-input single-output (MISO) SWIPT system where one multi-antenna transmitter sends information and energy simultaneously to an IR and multiple ERs, each with one single antenna. To optimally design transmit beamforming vectors and their power allocation, two problems are investigated with different aims: the first problem maximizes the secrecy rate for IR subject to individual harvested energy constraints of ERs, while the second problem maximizes the weighted sum-energy transferred to ERs subject to a secrecy rate constraint for IR. We solve these two non-convex problems optimally by reformulating each of them into a two-stage problem. First, by fixing the signal-to-interference-plus-noise ratio (SINR) target for ERs (for the first problem) or IR (for the second problem), we obtain the optimal beamforming and power allocation solution by applying the technique of semidefinite relaxation (SDR). Then, the original problems are solved by a one-dimension search over the optimal SINR target for ERs or IR. Furthermore, for each of the two studied problems, suboptimal solutions of lower complexity are also proposed in which the information and energy beamforming vectors are separately designed with their power allocation.
Interference alignment using finite and dependent channel extensions: the single beam case
Venue: arXiv cs.IT 2014
Year: 2014

Vector space interference alignment (IA) is known to achieve high degrees of freedom (DoF) with infinite independent channel extensions, but its performance is largely unknown for a finite number of possibly dependent channel extensions. In this paper, we consider a $K$-user $M_t \times M_r$ MIMO interference channel (IC) with arbitrary number of channel extensions $T$ and arbitrary channel diversity order $L$ (i.e., each channel matrix is a generic linear combination of $L$ fixed basis matrices). We study the maximum DoF achievable via vector space IA in the single beam case (i.e. each user sends one data stream). We prove that the total number of users $K$ that can communicate interference-free using linear transceivers is upper bounded by $NL+N^2/4$, where $N = \min\{M_tT, M_rT \}$. An immediate consequence of this upper bound is that for a SISO IC the DoF in the single beam case is no more than $\min\left\{\sqrt{ 5K/4}, L + T/4\right\}$. When the channel extensions are independent, i.e. $ L$ achieves the maximum $M_r M_t T $, we show that this maximum DoF lies in $[M_r+M_t-1, M_r+M_t]$ regardless of $T$. Unlike the well-studied constant MIMO IC case, the main difficulty is how to deal with a hybrid system of equations (zero-forcing condition) and inequalities (full rank condition). Our approach combines algebraic tools that deal with equations with an induction analysis that indirectly considers the inequalities.
Distinguisher-Based Attacks on Public-Key Cryptosystems Using Reed-Solomon Codes
Venue: arXiv cs.CR 2014
Year: 2014

Because of their interesting algebraic properties, several authors promote the use of generalized Reed-Solomon codes in cryptography. Niederreiter was the first to suggest an instantiation of his cryptosystem with them but Sidelnikov and Shestakov showed that this choice is insecure. Wieschebrink proposed a variant of the McEliece cryptosystem which consists in concatenating a few random columns to a generator matrix of a secretly chosen generalized Reed-Solomon code. More recently, new schemes appeared which are the homomorphic encryption scheme proposed by Bogdanov and Lee, and a variation of the McEliece cryptosystem proposed by Baldi et \textit{al.} which hides the generalized Reed-Solomon code by means of matrices of very low rank. In this work, we show how to mount key-recovery attacks against these public-key encryption schemes. We use the concept of distinguisher which aims at detecting a behavior different from the one that one would expect from a random code. All the distinguishers we have built are based on the notion of component-wise product of codes. It results in a powerful tool that is able to recover the secret structure of codes when they are derived from generalized Reed-Solomon codes. Lastly, we give an alternative to Sidelnikov and Shestakov attack by building a filtration which enables to completely recover the support and the non-zero scalars defining the secret generalized Reed-Solomon code.
MacWilliams Extension Theorems and the Local-Global Property for Codes over Rings
Venue: arXiv cs.IT 2014
Year: 2014

The MacWilliams extension theorem is investigated for various weight functions over finite Frobenius rings. The problem is reformulated in terms of a local-global property for subgroups of the general linear group. Among other things, it is shown that the extension theorem holds true for poset weights if and only if the underlying poset is hierarchical. Specifically, the Rosenbloom-Tsfasman weight for vector codes satisfies the extension theorem, whereas the Niederreiter-Rosenbloom-Tsfasman weight for matrix codes does not. A short character-theoretic proof of the well-known MacWilliams extension theorem for the homogeneous weight is provided. Moreover it is shown that the extension theorem carries over to direct products of weights, but not to symmetrized products.
Impact of Propagation Environment on Energy-Efficient Relay Placement: Model and Performance Analysis
Venue: arXiv cs.NI 2014
Year: 2014

The performance of a relay-based cellular network is greatly affected by the relay location within a cell. Existing results for optimal relay placement do not reflect how the radio propagation environment and choice of the coding scheme can impact system performance. In this paper, we analyze the impact on relaying performance of node distances, relay height and line-of-sight conditions for both uplink and downlink transmissions, using several relay coding schemes. Our first objective is to propose a geometrical model for energy-efficient relay placement that requires only a small number of characteristic distances. Our second objective is to estimate the maximum cell coverage of a relay-aided cell given power constraints, and conversely, the averaged energy consumption given a cell radius. We show that the practical full decode-forward scheme performs close to the energy-optimized partial decode-forward scheme when the relay is ideally located. However, away from this optimum relay location, performance rapidly degrades and more advanced coding scheme, such as partial decode-forward, is needed to maintain good performance and allow more freedom in the relay placement. Finally, we define a trade-off between cell coverage and energy efficiency, and show that there exists a relay location for which increasing the cell coverage has a minimal impact on the average energy consumed per unit area.
Cost-Aware Automatic Program Repair
Venue: arXiv cs.PL 2014
Year: 2014

We present a formal framework for repairing infinite-state, imperative, sequential programs, with (possibly recursive) procedures and multiple assertions; the framework can generate repaired programs by modifying the original erroneous program in multiple program locations, and can ensure the readability of the repaired program using user-defined expression templates; the framework also generates a set of inductive assertions that serve as a proof of correctness of the repaired program. As a step toward integrating programmer intent and intuition in automated program repair, we present a " cost-aware" formulation - given a cost function associated with permissible statement modifications, the goal is to ensure that the total program modification cost does not exceed a given repair budget. As part of our predicate abstraction-based solution framework, we present a sound and complete algorithm for repair of Boolean programs. We have developed a prototype tool based on SMT solving and used it successfully to repair diverse errors in benchmark C programs.
Manipulation of Stable Matchings using Minimal Blacklists
Venue: arXiv cs.GT 2014
Year: 2014

Gale and Sotomayor (1985) have shown that in the Gale-Shapley matching algorithm (1962), the proposed-to side W (referred to as women there) can strategically force the W-optimal stable matching as the M-optimal one by truncating their preference lists, each woman possibly blacklisting all but one man. As Gusfield and Irving have already noted in 1989, no results are known regarding achieving this feat by means other than such preference-list truncation, i.e. by also permuting preference lists. We answer Gusfield and Irving's open question by providing tight upper bounds on the amount of blacklists and their combined size, that are required by the women to force a given matching as the M-optimal stable matching, or, more generally, as the unique stable matching. Our results show that the coalition of all women can strategically force any matching as the unique stable matching, using preference lists in which at most half of the women have nonempty blacklists, and in which the average blacklist size is less than 1. This allows the women to manipulate the market in a manner that is far more inconspicuous, in a sense, than previously realized. When there are less women than men, we show that in the absence of blacklists for men, the women can force any matching as the unique stable matching without blacklisting anyone, while when there are more women than men, each to-be-unmatched woman may have to blacklist as many as all men. Together, these results shed light on the question of how much, if at all, do given preferences for one side a priori impose limitations on the set of stable matchings under various conditions. All of the results in this paper are constructive, providing efficient algorithms for calculating the desired strategies.
Upcoming Standards in Wireless Local Area Networks
Venue: arXiv cs.NI 2014
Year: 2014

Network technologies are traditionally centered on wireline solutions. Wireless broadband technologies nowadays provide unlimited broadband usage to users that have been previously offered simply to wireline users. In this paper, we discuss some of the upcoming standards of one of the emerging wireless broadband technology i.e. IEEE 802.11. The newest and the emerging standards fix technology issues or add functionality that will be expected to overcome many of the current standing problems with IEEE 802.11.
A space-time parallel solver for the three-dimensional heat equation
Venue: arXiv cs.NA 2014
Year: 2014

The paper presents a combination of the time-parallel "parallel full approximation scheme in space and time" (PFASST) with a parallel multigrid method (PMG) in space, resulting in a mesh-based solver for the three-dimensional heat equation with a uniquely high degree of efficient concurrency. Parallel scaling tests are reported on the Cray XE6 machine "Monte Rosa" on up to 16,384 cores and on the IBM Blue Gene/Q system "JUQUEEN" on up to 65,536 cores. The efficacy of the combined spatial- and temporal parallelization is shown by demonstrating that using PFASST in addition to PMG significantly extends the strong-scaling limit. Implications of using spatial coarsening strategies in PFASST's multi-level hierarchy in large-scale parallel simulations are discussed.
A Tractable Model for Non-Coherent Joint-Transmission Base Station Cooperation
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents a tractable model for analyzing non-coherent joint transmission base station (BS) cooperation, taking into account the irregular BS deployment typically encountered in practice. Besides cellular-network specific aspects such as BS density, channel fading, average path loss and interference, the model also captures relevant cooperation mechanisms including user-centric BS clustering and channel-dependent cooperation activation. The locations of all BSs are modeled by a Poisson point process. Using tools from stochastic geometry, the signal-to-interference-plus-noise ratio ($\mathtt{SINR}$) distribution with cooperation is precisely characterized in a generality-preserving form. The result is then applied to practical design problems of recent interest. We find that increasing the network-wide BS density improves the $\mathtt{SINR}$, while the gains increase with the path loss exponent. For pilot-based channel estimation, the average spectral efficiency saturates at cluster sizes of around $7$ BSs for typical values, irrespective of backhaul quality. Finally, it is shown that intra-cluster frequency reuse is favorable in moderately loaded cells with generous cooperation activation, while intra-cluster coordinated scheduling may be better in lightly loaded cells with conservative cooperation activation.
An Enhanced Features Extractor for a Portfolio of Constraint Solvers
Venue: arXiv cs.AI 2014
Year: 2014

Recent research has shown that a single arbitrarily efficient solver can be significantly outperformed by a portfolio of possibly slower on-average solvers. The solver selection is usually done by means of (un)supervised learning techniques which exploit features extracted from the problem specification. In this paper we present an useful and flexible framework that is able to extract an extensive set of features from a Constraint (Satisfaction/Optimization) Problem defined in possibly different modeling languages: MiniZinc, FlatZinc or XCSP. We also report some empirical results showing that the performances that can be obtained using these features are effective and competitive with state of the art CSP portfolio techniques.
Barycentric Coordinates as Interpolants
Venue: arXiv cs.GR 2014
Year: 2014

Barycentric coordinates are frequently used as interpolants to shade computer graphics images. A simple equation transforms barycentric coordinates from screen space into eye space in order to undo the perspective transformation and permit accurate interpolative shading of texture maps. This technique is amenable to computation using a block-normalized integer representation.