OpenRaiser/Intern-Atlas huggingface dataset:
Quantized Iterative Message Passing Decoders with Low Error Floor for LDPC Codes
Venue: arXiv cs.IT 2013
Year: 2013

The error floor phenomenon observed with LDPC codes and their graph-based, iterative, message-passing (MP) decoders is commonly attributed to the existence of error-prone substructures -- variously referred to as near codewords, trapping sets, absorbing sets, or pseudocodewords -- in a Tanner graph representation of the code. Many approaches have been proposed to lower the error floor by designing new LDPC codes with fewer such substructures or by modifying the decoding algorithm. Using a theoretical analysis of iterative MP decoding in an idealized trapping set scenario, we show that a contributor to the error floors observed in the literature may be the imprecise implementation of decoding algorithms and, in particular, the message quantization rules used. We then propose a new quantization method -- (q+1)-bit quasi-uniform quantization -- that efficiently increases the dynamic range of messages, thereby overcoming a limitation of conventional quantization schemes. Finally, we use the quasi-uniform quantizer to decode several LDPC codes that suffer from high error floors with traditional fixed-point decoder implementations. The performance simulation results provide evidence that the proposed quantization scheme can, for a wide variety of codes, significantly lower error floors with minimal increase in decoder complexity.
L-Recursion and a new Logic for Logarithmic Space
Venue: arXiv cs.LO 2013
Year: 2013

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and Boolean formula evaluation. We prove that LREC is strictly more expressive than deterministic transitive closure logic with counting and incomparable in expressive power with symmetric transitive closure logic STC and transitive closure logic (with or without counting). LREC is strictly contained in fixed-point logic with counting FPC. We also study an extension LREC= of LREC that has nicer closure properties and is more expressive than both LREC and STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our main results are that LREC captures LOGSPACE on the class of directed trees and that LREC= captures LOGSPACE on the class of interval graphs.
Pushing the Limits of LTE: A Survey on Research Enhancing the Standard
Venue: arXiv cs.IT 2013
Year: 2013

Cellular networks are an essential part of todays communication infrastructure. The ever-increasing demand for higher data-rates calls for a close cooperation between researchers and industry/standardization experts which hardly exists in practice. In this article we give an overview about our efforts in trying to bridge this gap. Our research group provides a standard-compliant open-source simulation platform for 3GPP LTE that enables reproducible research in a well-defined environment. We demonstrate that much innovative research under the confined framework of a real-world standard is still possible, sometimes even encouraged. With examplary samples of our research work we investigate on the potential of several important research areas under typical practical conditions.
A Formal Model For Real-Time Parallel Computation
Venue: arXiv cs.LO 2013
Year: 2013

The imposition of real-time constraints on a parallel computing environment- specifically high-performance, cluster-computing systems- introduces a variety of challenges with respect to the formal verification of the system's timing properties. In this paper, we briefly motivate the need for such a system, and we introduce an automaton-based method for performing such formal verification. We define the concept of a consistent parallel timing system: a hybrid system consisting of a set of timed automata (specifically, timed Buchi automata as well as a timed variant of standard finite automata), intended to model the timing properties of a well-behaved real-time parallel system. Finally, we give a brief case study to demonstrate the concepts in the paper: a parallel matrix multiplication kernel which operates within provable upper time bounds. We give the algorithm used, a corresponding consistent parallel timing system, and empirical results showing that the system operates under the specified timing constraints.
A Framework for Analysing Driver Interactions with Semi-Autonomous Vehicles
Venue: arXiv cs.HC 2013
Year: 2013

Semi-autonomous vehicles are increasingly serving critical functions in various settings from mining to logistics to defence. A key characteristic of such systems is the presence of the human (drivers) in the control loop. To ensure safety, both the driver needs to be aware of the autonomous aspects of the vehicle and the automated features of the vehicle built to enable safer control. In this paper we propose a framework to combine empirical models describing human behaviour with the environment and system models. We then analyse, via model checking, interaction between the models for desired safety properties. The aim is to analyse the design for safe vehicle-driver interaction. We demonstrate the applicability of our approach using a case study involving semi-autonomous vehicles where the driver fatigue are factors critical to a safe journey.
Opportunistic DF-AF Selection Relaying with Optimal Relay Selection in Nakagami-m Fading Environments
Venue: arXiv cs.IT 2013
Year: 2013

An opportunistic DF-AF selection relaying scheme with maximal received signal-to-noise ratio (SNR) at the destination is investigated in this paper. The outage probability of the opportunistic DF-AF selection relaying scheme over Nakagami-m fading channels is analyzed, and a closed-form solution is obtained. We perform asymptotic analysis of the outage probability in high SNR domain. The coding gain and the diversity order are obtained. For the purpose of comparison, the asymptotic analysis of opportunistic AF scheme in Nakagami-m fading channels is also performed by using the Squeeze Theorem. In addition, we prove that compared with the opportunistic DF scheme and opportunistic AF scheme, the opportunistic DF-AF selection relaying scheme has better outage performance.
Compressed Sensing with Linear Correlation Between Signal and Measurement Noise
Venue: arXiv cs.IT 2013
Year: 2013

Existing convex relaxation-based approaches to reconstruction in compressed sensing assume that noise in the measurements is independent of the signal of interest. We consider the case of noise being linearly correlated with the signal and introduce a simple technique for improving compressed sensing reconstruction from such measurements. The technique is based on a linear model of the correlation of additive noise with the signal. The modification of the reconstruction algorithm based on this model is very simple and has negligible additional computational cost compared to standard reconstruction algorithms, but is not known in existing literature. The proposed technique reduces reconstruction error considerably in the case of linearly correlated measurements and noise. Numerical experiments confirm the efficacy of the technique. The technique is demonstrated with application to low-rate quantization of compressed measurements, which is known to introduce correlated noise, and improvements in reconstruction error compared to ordinary Basis Pursuit De-Noising of up to approximately 7 dB are observed for 1 bit/sample quantization. Furthermore, the proposed method is compared to Binary Iterative Hard Thresholding which it is demonstrated to outperform in terms of reconstruction error for sparse signals with a number of non-zero coefficients greater than approximately 1/10th of the number of compressed measurements.
Surprise maximization reveals the community structure of complex networks
Venue: arXiv cs.SI 2013
Year: 2013

How to determine the community structure of complex networks is an open question. It is critical to establish the best strategies for community detection in networks of unknown structure. Here, using standard synthetic benchmarks, we show that none of the algorithms hitherto developed for community structure characterization perform optimally. Significantly, evaluating the results according to their modularity, the most popular measure of the quality of a partition, systematically provides mistaken solutions. However, a novel quality function, called Surprise, can be used to elucidate which is the optimal division into communities. Consequently, we show that the best strategy to find the community structure of all the networks examined involves choosing among the solutions provided by multiple algorithms the one with the highest Surprise value. We conclude that Surprise maximization precisely reveals the community structure of complex networks.
Group theory, group actions, evolutionary algorithms, and global optimization
Venue: arXiv cs.NE 2013
Year: 2013

In this paper we use group, action and orbit to understand how evolutionary solve nonconvex optimization problems.
Constacyclic Codes over Finite Fields
Venue: arXiv cs.IT 2013
Year: 2013

An equivalence relation called isometry is introduced to classify constacyclic codes over a finite field; the polynomial generators of constacyclic codes of length $\ell^tp^s$ are characterized, where $p$ is the characteristic of the finite field and $\ell$ is a prime different from $p$.
Compressed Sensing Matrices from Fourier Matrices
Venue: arXiv cs.IT 2013
Year: 2013

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included.
Energy-Delay Tradeoffs in a Load-Balanced Router
Venue: arXiv cs.NI 2013
Year: 2013

The Load-Balanced Router architecture has received a lot of attention because it does not require centralized scheduling at the internal switch fabrics. In this paper we reexamine the architecture, motivated by its potential to turn off multiple components and thereby conserve energy in the presence of low traffic. We perform a detailed analysis of the queue and delay performance of a Load-Balanced Router under a simple random routing algorithm. We calculate probabilistic bounds for queue size and delay, and show that the probabilities drop exponentially with increasing queue size or delay. We also demonstrate a tradeoff in energy consumption against the queue and delay performance.
Supporting Sensing Application in Vehicular Networks
Venue: arXiv cs.NI 2013
Year: 2013

This research aims at using vehicular ad-hoc networks as infra-structure for an urban cyber-physical system in order to gather data about a city. In this scenario, all nodes are data sources and there is a gateway as ultimate destination for all packets. Because of the volatility of the network connections and uncertainty of actual node placement, we argue that a broadcast-based protocol is the most adequate solution, despite the high overhead. The Urban Data Collector (UDC) protocol has been proposed which uses a distributed election of the forwarding node among the nodes receiving the packet: nodes that are nearer to the gateway have shorter timers and a higher forwarding probabilities. The performance of the UDC protocol has been evaluated with different suppression levels in terms of the amount of collected data from each road segment using NS-3, and our results show that UDC can achieve significantly higher sensing accuracy than to other broadcast-based protocols.
Adaptive Intelligent Cooperative Spectrum Sensing In Cognitive Radio
Venue: arXiv cs.NE 2013
Year: 2013

Radio Spectrum is most precious and scarce resource and must be utilized efficiently and effectively. Cognitive radio is the promising solutions for the optimum utilization of the scared natural resource. The spectrum owned by the primary user should be shared among the secondary user, but primary user should not be interfered by the secondary user. In order to utilize the primary user spectrum, secondary user must detect accurately, the existence of primary in the band of interest. In cooperative spectrum sensing, the channel between the secondary users and the cognitive radio base station is non stationary and causes interference in the decision in decision fusion and in information in information due to multipath fading. In this paper neural network based cooperative spectrum sensing method is proposed, the performance of proposed method is evaluated and observed that, the neural network based scheme performance improve significantly over the AND,OR and Majority rule
Desingularization Explains Order-Degree Curves for Ore Operators
Venue: arXiv cs.SC 2013
Year: 2013

Desingularization is the problem of finding a left multiple of a given Ore operator in which some factor of the leading coefficient of the original operator is removed. An order-degree curve for a given Ore operator is a curve in the $(r,d)$-plane such that for all points $(r,d)$ above this curve, there exists a left multiple of order $r$ and degree $d$ of the given operator. We give a new proof of a desingularization result by Abramov and van Hoeij for the shift case, and show how desingularization implies order-degree curves which are extremely accurate in examples.
Upper Bounds on Matching Families in $\mathbb{Z}_{pq}^n$
Venue: arXiv cs.IT 2013
Year: 2013

\textit{Matching families} are one of the major ingredients in the construction of {\em locally decodable codes} (LDCs) and the best known constructions of LDCs with a constant number of queries are based on matching families. The determination of the largest size of any matching family in $\mathbb{Z}_m^n$, where $\mathbb{Z}_m$ is the ring of integers modulo $m$, is an interesting problem. In this paper, we show an upper bound of $O((pq)^{0.625n+0.125})$ for the size of any matching family in $\mathbb{Z}_{pq}^n$, where $p$ and $q$ are two distinct primes. Our bound is valid when $n$ is a constant, $p\rightarrow \infty$ and $p/q\rightarrow 1$. Our result improves an upper bound of Dvir {\it et al.}
GESPAR: Efficient Phase Retrieval of Sparse Signals
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of phase retrieval, namely, recovery of a signal from the magnitude of its Fourier transform, or of any other linear transform. Due to the loss of the Fourier phase information, this problem is ill-posed. Therefore, prior information on the signal is needed in order to enable its recovery. In this work we consider the case in which the signal is known to be sparse, i.e., it consists of a small number of nonzero elements in an appropriate basis. We propose a fast local search method for recovering a sparse signal from measurements of its Fourier transform (or other linear transform) magnitude which we refer to as GESPAR: GrEedy Sparse PhAse Retrieval. Our algorithm does not require matrix lifting, unlike previous approaches, and therefore is potentially suitable for large scale problems such as images. Simulation results indicate that GESPAR is fast and more accurate than existing techniques in a variety of settings.
Ascending auctions and Walrasian equilibrium
Venue: arXiv cs.GT 2013
Year: 2013

We present a family of submodular valuation classes that generalizes gross substitute. We show that Walrasian equilibrium always exist for one class in this family, and there is a natural ascending auction which finds it. We prove some new structural properties on gross-substitute auctions which, in turn, show that the known ascending auctions for this class (Gul-Stacchetti and Ausbel) are, in fact, identical. We generalize these two auctions, and provide a simple proof that they terminate in a Walrasian equilibrium.
A Logic Programming Approach to Integration Network Inference
Venue: arXiv cs.DB 2013
Year: 2013

The discovery, representation and reconstruction of (technical) integration networks from Network Mining (NM) raw data is a difficult problem for enterprises. This is due to large and complex IT landscapes within and across enterprise boundaries, heterogeneous technology stacks, and fragmented data. To remain competitive, visibility into the enterprise and partner IT networks on different, interrelated abstraction levels is desirable. We present an approach to represent and reconstruct the integration networks from NM raw data using logic programming based on first-order logic. The raw data expressed as integration network model is represented as facts, on which rules are applied to reconstruct the network. We have built a system that is used to apply this approach to real-world enterprise landscapes and we report on our experience with this system.
Translating NP-SPEC into ASP
Venue: arXiv cs.AI 2013
Year: 2013

NP-SPEC is a language for specifying problems in NP in a declarative way. Despite the fact that the semantics of the language was given by referring to Datalog with circumscription, which is very close to ASP, so far the only existing implementations are by means of ECLiPSe Prolog and via Boolean satisfiability solvers. In this paper, we present translations from NP-SPEC into various forms of ASP and analyze them. We also argue that it might be useful to incorporate certain language constructs of NP-SPEC into mainstream ASP.
Lloyd-Topor Completion and General Stable Models
Venue: arXiv cs.LO 2013
Year: 2013

We investigate the relationship between the generalization of program completion defined in 1984 by Lloyd and Topor and the generalization of the stable model semantics introduced recently by Ferraris et al. The main theorem can be used to characterize, in some cases, the general stable models of a logic program by a first-order formula. The proof uses Truszczynski's stable model semantics of infinitary propositional formulas.
Practical graph isomorphism, II
Venue: arXiv cs.DM 2013
Year: 2013

We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.
A novel processing pipeline for optical multi-touch surfaces
Venue: arXiv cs.CV 2013
Year: 2013

In this thesis a new approach for touch detection on optical multi-touch devices is proposed that exploits the fact that the camera images reveal not only the actual touch points but also objects above the screen such as the hand or arm of a user. The touch processing relies on the Maximally Stable Extremal Regions algorithm for finding the users' fingertips in the camera image. The hierarchical structure of the generated extremal regions serves as a starting point for agglomerative clustering of the fingertips into hands. Furthermore, a heuristic is suggested that supports the identification of individual fingers as well as the distinction between left hands and right hands if all five fingers of a hand are in contact with the touch surface. The evaluation confirmed that the system is robust against detection errors resulting from non-uniform illumination and reliably assigns touch points to individual hands based on the implicitly tracked context information. The efficient multi-threaded implementation handles two-handed input from multiple users in real-time.
BigDB: Automatic Machine Learning Optimizer
Venue: arXiv cs.DB 2013
Year: 2013

In this short vision paper, we introduce a machine learning optimizer for data management and describe its architecture and main functionality.
Three Simulation Algorithms for Labelled Transition Systems
Venue: arXiv cs.FL 2013
Year: 2013

Algorithms which compute the coarsest simulation preorder are generally designed on Kripke structures. Only in a second time they are extended to labelled transition systems. By doing this, the size of the alphabet appears in general as a multiplicative factor to both time and space complexities. Let $Q$ denotes the state space, $\rightarrow$ the transition relation, $Σ$ the alphabet and $P_{sim}$ the partition of $Q$ induced by the coarsest simulation equivalence. In this paper, we propose a base algorithm which minimizes, since the first stages of its design, the incidence of the size of the alphabet in both time and space complexities. This base algorithm, inspired by the one of Paige and Tarjan in 1987 for bisimulation and the one of Ranzato and Tapparo in 2010 for simulation, is then derived in three versions. One of them has the best bit space complexity up to now, $O(|P_{sim}|^2+|{\rightarrow}|.\log|{\rightarrow}|)$, while another one has the best time complexity up to now, $O(|P_{sim}|.|{\rightarrow}|)$. Note the absence of the alphabet in these complexities. A third version happens to be a nice compromise between space and time since it runs in $O(b.|P_{sim}|.|{\rightarrow}|)$ time, with $b$ a branching factor generally far below $|P_{sim}|$, and uses $O(|P_{sim}|^2.\log|P_{sim}|+|{\rightarrow}|.\log|{\rightarrow}|)$ bits.
Parallel Algorithms for Constructing Data Structures for Fast Multipole Methods
Venue: arXiv cs.MS 2013
Year: 2013

We present efficient algorithms to build data structures and the lists needed for fast multipole methods. The algorithms are capable of being efficiently implemented on both serial, data parallel GPU and on distributed architectures. With these algorithms it is possible to map the FMM efficiently on to the GPU or distributed heterogeneous CPU-GPU systems. Further, in dynamic problems, as the distribution of the particles change, the reduced cost of building the data structures improves performance. Using these algorithms, we demonstrate example high fidelity simulations with large problem sizes by using FMM on both single and multiple heterogeneous computing facilities equipped with multi-core CPU and many-core GPUs.