OpenRaiser/Intern-Atlas huggingface dataset:
Mapping and Coding Design for Channel Coded Physical-layer Network Coding
Venue: arXiv cs.IT 2013
Year: 2013

Although BICM can significantly improves the BER performance by iteration processing between the demapping and the decoding in a traditional receiver, its design and performance in PNC system has fewer studied. This paper investigates a bit interleaved coded modulation (BICM) scheme in a Gaussian two-way relay channel operated with physical layer network coding (PNC). In particular, we first present an iterative demapping and decoding framework specially designed for PNC. After that, we compare different constellation mapping schemes in this framework, with the convergence analysis by using the EXIT chart. It is found that the anti-Gray mapping outperforms the Gray mapping, which is the best mapping in the traditional decoding schemes. Finally, the numerical simulation shows the better performance of our framework and verifies the mapping design.
Distributed computation of persistent homology
Venue: arXiv cs.CG 2013
Year: 2013

Persistent homology is a popular and powerful tool for capturing topological features of data. Advances in algorithms for computing persistent homology have reduced the computation time drastically -- as long as the algorithm does not exhaust the available memory. Following up on a recently presented parallel method for persistence computation on shared memory systems, we demonstrate that a simple adaption of the standard reduction algorithm leads to a variant for distributed systems. Our algorithmic design ensures that the data is distributed over the nodes without redundancy; this permits the computation of much larger instances than on a single machine. Moreover, we observe that the parallelism at least compensates for the overhead caused by communication between nodes, and often even speeds up the computation compared to sequential and even parallel shared memory algorithms. In our experiments, we were able to compute the persistent homology of filtrations with more than a billion (10^9) elements within seconds on a cluster with 32 nodes using less than 10GB of memory per node.
Advanced channel coding for space mission telecommand links
Venue: arXiv cs.IT 2013
Year: 2013

We investigate and compare different options for updating the error correcting code currently used in space mission telecommand links. Taking as a reference the solutions recently emerged as the most promising ones, based on Low-Density Parity-Check codes, we explore the behavior of alternative schemes, based on parallel concatenated turbo codes and soft-decision decoded BCH codes. Our analysis shows that these further options can offer similar or even better performance.
Formal verification in Coq of program properties involving the global state effect
Venue: arXiv cs.LO 2013
Year: 2013

The syntax of an imperative language does not mention explicitly the state, while its denotational semantics has to mention it. In this paper we present a framework for the verification in Coq of properties of programs manipulating the global state effect. These properties are expressed in a proof system which is close to the syntax, as in effect systems, in the sense that the state does not appear explicitly in the type of expressions which manipulate it. Rather, the state appears via decorations added to terms and to equations. In this system, proofs of programs thus present two aspects: properties can be verified {\em up to effects} or the effects can be taken into account. The design of our Coq library consequently reflects these two aspects: our framework is centered around the construction of two inductive and dependent types, one for terms up to effects and one for the manipulation of decorations.
Efficient pedestrian detection by directly optimize the partial area under the ROC curve
Venue: arXiv cs.CV 2013
Year: 2013

Many typical applications of object detection operate within a prescribed false-positive range. In this situation the performance of a detector should be assessed on the basis of the area under the ROC curve over that range, rather than over the full curve, as the performance outside the range is irrelevant. This measure is labelled as the partial area under the ROC curve (pAUC). Effective cascade-based classification, for example, depends on training node classifiers that achieve the maximal detection rate at a moderate false positive rate, e.g., around 40% to 50%. We propose a novel ensemble learning method which achieves a maximal detection rate at a user-defined range of false positive rates by directly optimizing the partial AUC using structured learning. By optimizing for different ranges of false positive rates, the proposed method can be used to train either a single strong classifier or a node classifier forming part of a cascade classifier. Experimental results on both synthetic and real-world data sets demonstrate the effectiveness of our approach, and we show that it is possible to train state-of-the-art pedestrian detectors using the proposed structured ensemble learning method.
Cudagrind: A Valgrind Extension for CUDA
Venue: arXiv cs.SE 2013
Year: 2013

Valgrind, and specifically the included tool Memcheck, offers an easy and reliable way for checking the correctness of memory operations in programs. This works in an unintrusive way where Valgrind translates the program into intermediate code and executes it on an emulated CPU. The heavy weight tool Memcheck uses this to keep a full shadow copy of the memory used by a program and tracking accesses to it. This allows the detection of memory leaks and checking the validity of accesses. Though suited for a wide variety of programs, this approach still fails when accelerator based programming models are involved. The code running on these devices is separate from the code running on the host. Access to memory on the device and starting of kernels is being handled by an API provided by the driver being used. Hence Valgrind is unable to understand and instrument operations being run on the device. To circumvent this limitation a new set of wrapper functions have been introduced. These wrap a subset of the CUDA Driver API function that is responsible for (de-)allocation memory regions on the device and the respective memory copy operations. This allows to check whether memory is fully allocated during a transfer and, through the functionality provided by Valgrind, whether the memory transfered to the device from the host is defined and addressable. Through this technique it is possible to detect a number of common programming mistakes, which are very difficult to debug by other means. The combination of these wrappers together with the Valgrind tool Memcheck is being called Cudagrind.
On the Parameterized Complexity of Associative and Commutative Unification
Venue: arXiv cs.SC 2013
Year: 2013

This paper studies the unification problem with associative, commutative, and associative-commutative functions mainly from a viewpoint of the parameterized complexity on the number of variables. It is shown that both associative and associative-commutative unification problems are $W[1]$-hard. A fixed-parameter algorithm and a polynomial-time algorithm are presented for special cases of commutative unification in which one input term is variable-free and the number of variables is bounded by a constant, respectively. Related results including those on the string and tree edit distance problems with variables are shown too.
Algorithmic Aspects of Switch Cographs
Venue: arXiv cs.DM 2013
Year: 2013

This paper introduces the notion of involution module, the first generalization of the modular decomposition of 2-structure which has a unique linear-sized decomposition tree. We derive an O(n^2) decomposition algorithm and we take advantage of the involution modular decomposition tree to state several algorithmic results. Cographs are the graphs that are totally decomposable w.r.t modular decomposition. In a similar way, we introduce the class of switch cographs, the class of graphs that are totally decomposable w.r.t involution modular decomposition. This class generalizes the class of cographs and is exactly the class of (Bull, Gem, Co-Gem, C_5)-free graphs. We use our new decomposition tool to design three practical algorithms for the maximum cut, vertex cover and vertex separator problems. The complexity of these problems was still unknown for this class of graphs. This paper also improves the complexity of the maximum clique, the maximum independant set, the chromatic number and the maximum clique cover problems by giving efficient algorithms, thanks to the decomposition tree. Eventually, we show that this class of graphs has Clique-Width at most 4 and that a Clique-Width expression can be computed in linear time.
Utility Fair Optimisation of Antenna Tilt Angles in LTE Networks
Venue: arXiv cs.NI 2013
Year: 2013

We formulate adaptation of antenna tilt angle as a utility fair optimisation task. This optimisation problem is non-convex, but in this paper we show that under reasonable conditions it can be reformulated as a convex optimisation. Using this insight, we develop a lightweight method for finding the optimal antenna tilt angles, making use of measurements which are already available at base stations, and suited to distributed implementation.
Distributed Control with Low-Rank Coordination
Venue: arXiv cs.SY 2013
Year: 2013

A common approach to distributed control design is to impose sparsity constraints on the controller structure. Such constraints, however, may greatly complicate the control design procedure. This paper puts forward an alternative structure, which is not sparse yet might nevertheless be well suited for distributed control purposes. The structure appears as the optimal solution to a class of coordination problems arising in multi-agent applications. The controller comprises a diagonal (decentralized) part, complemented by a rank-one coordination term. Although this term relies on information about all subsystems, its implementation only requires a simple averaging operation.
Cubic graphs with large circumference deficit
Venue: arXiv cs.DM 2013
Year: 2013

The circumference $c(G)$ of a graph $G$ is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically $4$-, $5$- and $6$-edge-connected cubic graphs with circumference ratio $c(G)/|V(G)|$ bounded from above by $0.876$, $0.960$ and $0.990$, respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically $4$-edge-connected cubic graph is at least $0.75$. In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Disc. Math. 312 (2012), 2540--2544].
Revisiting the Problem of Searching on a Line
Venue: arXiv cs.DS 2013
Year: 2013

We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. Prior to this work, only asymptotic bounds were known for the optimal competitive ratio achievable by any search strategy in the worst case. We present the first tight bounds on the exact optimal competitive ratio achievable, parameterized in terms of the given bounds on D, along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique. We characterize the conditions under which an optimal strategy can be computed exactly and, when it cannot, we explain how numerical methods can be used efficiently. In addition, we answer several related open questions, including the maximal reach problem, and we discuss how to generalize these results to m rays, for any m >= 2.
Review on Fragment Allocation by using Clustering Technique in Distributed Database System
Venue: arXiv cs.DB 2013
Year: 2013

Considerable Progress has been made in the last few years in improving the performance of the distributed database systems. The development of Fragment allocation models in Distributed database is becoming difficult due to the complexity of huge number of sites and their communication considerations. Under such conditions, simulation of clustering and data allocation is adequate tools for understanding and evaluating the performance of data allocation in Distributed databases. Clustering sites and fragment allocation are key challenges in Distributed database performance, and are considered to be efficient methods that have a major role in reducing transferred and accessed data during the execution of applications. In this paper a review on Fragment allocation by using Clustering technique is given in Distributed Database System.
Reading Stockholm Riots 2013 in social media by text-mining
Venue: arXiv cs.SI 2013
Year: 2013

The riots in Stockholm in May 2013 were an event that reverberated in the world media for its dimension of violence that had spread through the Swedish capital. In this study we have investigated the role of social media in creating media phenomena via text mining and natural language processing. We have focused on two channels of communication for our analysis: Twitter and Poloniainfo.se (Forum of Polish community in Sweden). Our preliminary results show some hot topics driving discussion related mostly to Swedish Police and Swedish Politics by counting word usage. Typical features for media intervention are presented. We have built networks of most popular phrases, clustered by categories (geography, media institution, etc.). Sentiment analysis shows negative connotation with Police. The aim of this preliminary exploratory quantitative study was to generate questions and hypotheses, which we could carefully follow by deeper more qualitative methods.
Binary Cyclic Codes from Explicit Polynomials over $\gf(2^m)$
Venue: arXiv cs.IT 2013
Year: 2013

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, monomials and trinomials over finite fields with even characteristic are employed to construct a number of families of binary cyclic codes. Lower bounds on the minimum weight of some families of the cyclic codes are developed. The minimum weights of other families of the codes constructed in this paper are determined. The dimensions of the codes are flexible. Some of the codes presented in this paper are optimal or almost optimal in the sense that they meet some bounds on linear codes. Open problems regarding binary cyclic codes from monomials and trinomials are also presented.
Space Efficient Linear Time Lempel-Ziv Factorization on Constant~Size~Alphabets
Venue: arXiv cs.DS 2013
Year: 2013

We present a new algorithm for computing the Lempel-Ziv Factorization (LZ77) of a given string of length $N$ in linear time, that utilizes only $N\log N + O(1)$ bits of working space, i.e., a single integer array, for constant size integer alphabets. This greatly improves the previous best space requirement for linear time LZ77 factorization (Kärkkäinen et al. CPM 2013), which requires two integer arrays of length $N$. Computational experiments show that despite the added complexity of the algorithm, the speed of the algorithm is only around twice as slow as previous fastest linear time algorithms.
Contraction Principle based Robust Iterative Algorithms for Machine Learning
Venue: arXiv cs.LG 2013
Year: 2013

Iterative algorithms are ubiquitous in the field of data mining. Widely known examples of such algorithms are the least mean square algorithm, backpropagation algorithm of neural networks. Our contribution in this paper is an improvement upon this iterative algorithms in terms of their respective performance metrics and robustness. This improvement is achieved by a new scaling factor which is multiplied to the error term. Our analysis shows that in essence, we are minimizing the corresponding LASSO cost function, which is the reason of its increased robustness. We also give closed form expressions for the number of iterations for convergence and the MSE floor of the original cost function for a minimum targeted value of the L1 norm. As a concluding theme based on the stochastic subgradient algorithm, we give a comparison between the well known Dantzig selector and our algorithm based on contraction principle. By these simulations we attempt to show the optimality of our approach for any widely used parent iterative optimization problem.
Three-Way Dissection of a Game-CAPTCHA: Automated Attacks, Relay Attacks, and Usability
Venue: arXiv cs.CR 2013
Year: 2013

Existing captcha solutions on the Internet are a major source of user frustration. Game captchas are an interesting and, to date, little-studied approach claiming to make captcha solving a fun activity for the users. One broad form of such captchas -- called Dynamic Cognitive Game (DCG) captchas -- challenge the user to perform a game-like cognitive task interacting with a series of dynamic images. We pursue a comprehensive analysis of a representative category of DCG captchas. We formalize, design and implement such captchas, and dissect them across: (1) fully automated attacks, (2) human-solver relay attacks, and (3) usability. Our results suggest that the studied DCG captchas exhibit high usability and, unlike other known captchas, offer some resistance to relay attacks, but they are also vulnerable to our novel dictionary-based automated attack.
A Workflow-Forecast Approach To The Task Scheduling Problem In Distributed Computing Systems
Venue: arXiv cs.DC 2013
Year: 2013

The aim of this paper is to provide a description of deep-learning-based scheduling approach for academic-purpose high-performance computing systems. The share of academic-purpose distributed computing systems (DCS) reaches 17.4 percents amongst TOP500 supercomputer sites (15.6 percents in performance scale) that makes them a valuable object of research. The core of this approach is to predict the future workflow of the system depending on the previously submitted tasks using deep learning algorithm. Information on predicted tasks is used by the resource management system (RMS) to perform efficient schedule.
Transmit Beamforming for MIMO Communication Systems with Low Precision ADC at the Receiver
Venue: arXiv cs.IT 2013
Year: 2013

Multiple antenna systems have been extensively used by standards designing multi-gigabit communication systems operating in bandwidth of several GHz. In this paper, we study the use of transmitter (Tx) beamforming techniques to improve the performance of a MIMO system with a low precision ADC. We motivate an approach to use eigenmode transmit beamforming (which imposes a diagonal structure in the complete MIMO system) and use an eigenmode power allocation which minimizes the uncoded BER of the finite precision system. Although we cannot guarantee optimality of this approach, we observe that even low with precision ADC, it performs comparably to full precision system with no eigenmode power allocation. For example, in a high throughput MIMO system with a finite precision ADC at the receiver, simulation results show that for a 3/4 LDPC coded 2x2 MIMO OFDM 16-QAM system with 3-bit precision ADC at the receiver, a BER of 0.0001 is achieved at an SNR of 26 dB. This is 1 dB better than that required for the same system with full precision but equal eigenmode power allocation.
MINT: Mutual Information based Transductive Feature Selection for Genetic Trait Prediction
Venue: arXiv cs.LG 2013
Year: 2013

Whole genome prediction of complex phenotypic traits using high-density genotyping arrays has attracted a great deal of attention, as it is relevant to the fields of plant and animal breeding and genetic epidemiology. As the number of genotypes is generally much bigger than the number of samples, predictive models suffer from the curse-of-dimensionality. The curse-of-dimensionality problem not only affects the computational efficiency of a particular genomic selection method, but can also lead to poor performance, mainly due to correlation among markers. In this work we proposed the first transductive feature selection method based on the MRMR (Max-Relevance and Min-Redundancy) criterion which we call MINT. We applied MINT on genetic trait prediction problems and showed that in general MINT is a better feature selection method than the state-of-the-art inductive method mRMR.
The Approximate Capacity Region of the Gaussian Y-Channel
Venue: arXiv cs.IT 2013
Year: 2013

A full-duplex wireless network with three users that want to establish full message-exchange via a relay is considered. Thus, the network known as the Y-channel has a total of 6 messages, 2 outgoing and 2 incoming at each user. The users are not physically connected, and thus the relay is essential for their communication. The linear-shift deterministic Y-channel is considered first, its capacity region is characterized and shown not to be given by the cut-set bounds. The capacity achieving scheme has three different components (strategies): a bi-directional, a cyclic, and a uni-directional strategy. Network coding is used to realize the bi-directional and the cyclic strategies, and thus to prove the achievability of the capacity region. The result is then extended to the Gaussian Y-channel where the capacity region is characterized within a constant gap independent of the channel parameters.
Adaptive Modulation in Multi-user Cognitive Radio Networks over Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the performance of adaptive modulation in multi-user cognitive radio networks over fading channels is analyzed. Multi-user diversity is considered for opportunistic user selection among multiple secondary users. The analysis is obtained for Nakagami-$m$ fading channels. Both adaptive continuous rate and adaptive discrete rate schemes are analysed in opportunistic spectrum access and spectrum sharing. Numerical results are obtained and depicted to quantify the effects of multi-user fading environments on adaptive modulation operating in cognitive radio networks.
Error Rate Analysis of Cognitive Radio Transmissions with Imperfect Channel Sensing
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the symbol error rate performance of cognitive radio transmissions in the presence of imperfect sensing decisions. Two different transmission schemes, namely sensing-based spectrum sharing (SSS) and opportunistic spectrum access (OSA), are considered. In both schemes, secondary users first perform channel sensing, albeit with possible errors. In SSS, depending on the sensing decisions, they adapt the transmission power level and coexist with primary users in the channel. On the other hand, in OSA, secondary users are allowed to transmit only when the primary user activity is not detected. Initially, for both transmission schemes, general formulations for the optimal decision rule and error probabilities are provided for arbitrary modulation schemes under the assumptions that the receiver is equipped with the sensing decision and perfect knowledge of the channel fading, and the primary user's received faded signals at the secondary receiver has a Gaussian mixture distribution. Subsequently, the general approach is specialized to rectangular quadrature amplitude modulation (QAM). More specifically, optimal decision rule is characterized for rectangular QAM, and closed-form expressions for the average symbol error probability attained with the optimal detector are derived under both transmit power and interference constraints. The effects of imperfect channel sensing decisions, interference from the primary user and its Gaussian mixture model, and the transmit power and interference constraints on the error rate performance of cognitive transmissions are analyzed.