OpenRaiser/Intern-Atlas huggingface dataset:
Volume Rendering of AMR Simulations
Venue: arXiv cs.DS 2013
Year: 2013

High-resolution simulations often rely on the Adaptive Mesh Resolution (AMR) technique to optimize memory consumption versus attainable precision. While this technique allows for dramatic improvements in terms of computing performance, the analysis and visualization of its data outputs remain challenging. The lack of effective volume renderers for the octree-based AMR used by the RAMSES simulation program has led to the development of the solutions presented in this paper. Two custom algorithms are discussed, based on the splatting and the ray-casting techniques. Their usage is illustrated in the context of the visualization of a high-resolution, 6000-processor simulation of a Milky Way-like galaxy. Performance obtained in terms of memory management and parallelism speedup are presented.
Forbidden Configurations: Finding the number predicted by the Anstee-Sali Conjecture is NP-hard
Venue: arXiv cs.DM 2013
Year: 2013

Let F be a hypergraph and let forb(m,F) denote the maximum number of edges a hypergraph with m vertices can have if it doesn't contain F as a subhypergraph. A conjecture of Anstee and Sali predicts the asymptotic behaviour of forb(m,F) for fixed F. In this paper we prove that even finding this predicted asymptotic behaviour is an NP-hard problem, meaning that if the Anstee-Sali conjecture were true, finding the asymptotics of forb(m,F) would be NP-hard.
Stabilization Based Networked Predictive Controller Design for Switched Plants
Venue: arXiv cs.SY 2013
Year: 2013

Stabilizing state feedback controller has been designed in this paper for a switched DC motor plant, controlled over communication network. The switched system formulation for the networked control system (NCS) with additional switching in a plant parameter along with the switching due to random packet losses, have been formulated as few set of non-strict Linear Matrix Inequalities (LMIs). In order to solve non-strict LMIs using standard LMI solver and to design the stabilizing state feedback controller, the Cone Complementary Linearization (CCL) technique has been adopted. Simulation studies have been carried out for a DC motor plant, operating at two different sampling times with random switching in the moment of inertia, representing sudden jerks.
Algorithms and Hardness for Robust Subspace Recovery
Venue: arXiv cs.CC 2013
Year: 2013

We consider a fundamental problem in unsupervised learning called \emph{subspace recovery}: given a collection of $m$ points in $\mathbb{R}^n$, if many but not necessarily all of these points are contained in a $d$-dimensional subspace $T$ can we find it? The points contained in $T$ are called {\em inliers} and the remaining points are {\em outliers}. This problem has received considerable attention in computer science and in statistics. Yet efficient algorithms from computer science are not robust to {\em adversarial} outliers, and the estimators from robust statistics are hard to compute in high dimensions. Are there algorithms for subspace recovery that are both robust to outliers and efficient? We give an algorithm that finds $T$ when it contains more than a $\frac{d}{n}$ fraction of the points. Hence, for say $d = n/2$ this estimator is both easy to compute and well-behaved when there are a constant fraction of outliers. We prove that it is Small Set Expansion hard to find $T$ when the fraction of errors is any larger, thus giving evidence that our estimator is an {\em optimal} compromise between efficiency and robustness. As it turns out, this basic problem has a surprising number of connections to other areas including small set expansion, matroid theory and functional analysis that we make use of here.
A Framework for Investigating the Performance of Chaotic-Map Truly Random Number Generators
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we approximate the hidden Markov model of chaotic-map truly random number generators (TRNGs) and describe its fundamental limits based on the approximate entropy-rate of the underlying bit-generation process. We demonstrate that entropy-rate plays a key role in the performance and robustness of chaotic-map TRNGs, which must be taken into account in the circuit design optimization. We further derive optimality conditions for post-processing units that extract truly random bits from a raw-RNG.
A Distributed Differential Space-Time Coding Scheme With Analog Network Coding in Two-Way Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider general two-way relay networks (TWRNs) with two source and N relay nodes. A distributed differential space time coding with analog network coding (DDSTC-ANC) scheme is proposed. A simple blind estimation and a differential signal detector are developed to recover the desired signal at each source. The pairwise error probability (PEP) and block error rate (BLER) of the DDSTC-ANC scheme are analyzed. Exact and simplified PEP expressions are derived. To improve the system performance, the optimum power allocation (OPA) between the source and relay nodes is determined based on the simplified PEP expression. The analytical results are verified through simulations.
Efficient learning of simplices
Venue: arXiv cs.LG 2013
Year: 2013

We show an efficient algorithm for the following problem: Given uniformly random points from an arbitrary n-dimensional simplex, estimate the simplex. The size of the sample and the number of arithmetic operations of our algorithm are polynomial in n. This answers a question of Frieze, Jerrum and Kannan [FJK]. Our result can also be interpreted as efficiently learning the intersection of n+1 half-spaces in R^n in the model where the intersection is bounded and we are given polynomially many uniform samples from it. Our proof uses the local search technique from Independent Component Analysis (ICA), also used by [FJK]. Unlike these previous algorithms, which were based on analyzing the fourth moment, ours is based on the third moment. We also show a direct connection between the problem of learning a simplex and ICA: a simple randomized reduction to ICA from the problem of learning a simplex. The connection is based on a known representation of the uniform measure on a simplex. Similar representations lead to a reduction from the problem of learning an affine transformation of an n-dimensional l_p ball to ICA.
A SVD accelerated kernel-independent fast multipole method and its application to BEM
Venue: arXiv cs.NA 2013
Year: 2013

The kernel-independent fast multipole method (KIFMM) proposed in [1] is of almost linear complexity. In the original KIFMM the time-consuming M2L translations are accelerated by FFT. However, when more equivalent points are used to achieve higher accuracy, the efficiency of the FFT approach tends to be lower because more auxiliary volume grid points have to be added. In this paper, all the translations of the KIFMM are accelerated by using the singular value decomposition (SVD) based on the low-rank property of the translating matrices. The acceleration of M2L is realized by first transforming the associated translating matrices into more compact form, and then using low-rank approximations. By using the transform matrices for M2L, the orders of the translating matrices in upward and downward passes are also reduced. The improved KIFMM is then applied to accelerate BEM. The performance of the proposed algorithms are demonstrated by three examples. Numerical results show that, compared with the original KIFMM, the present method can reduce about 40% of the iterating time and 25% of the memory requirement.
GPU-accelerated generation of correctly-rounded elementary functions
Venue: arXiv cs.MS 2013
Year: 2013

The IEEE 754-2008 standard recommends the correct rounding of some elementary functions. This requires to solve the Table Maker's Dilemma which implies a huge amount of CPU computation time. We consider in this paper accelerating such computations, namely Lefe'vre algorithm on Graphics Processing Units (GPUs) which are massively parallel architectures with a partial SIMD execution (Single Instruction Multiple Data). We first propose an analysis of the Lefèvre hard-to-round argument search using the concept of continued fractions. We then propose a new parallel search algorithm much more efficient on GPU thanks to its more regular control flow. We also present an efficient hybrid CPU-GPU deployment of the generation of the polynomial approximations required in Lefèvre algorithm. In the end, we manage to obtain overall speedups up to 53.4x on one GPU over a sequential CPU execution, and up to 7.1x over a multi-core CPU, which enable a much faster solving of the Table Maker's Dilemma for the double precision format.
Secure Computation of Top-K Eigenvectors for Shared Matrices in the Cloud
Venue: arXiv cs.CR 2013
Year: 2013

With the development of sensor network, mobile computing, and web applications, data are now collected from many distributed sources to form big datasets. Such datasets can be hosted in the cloud to achieve economical processing. However, these data might be highly sensitive requiring secure storage and processing. We envision a cloud-based data storage and processing framework that enables users to economically and securely share and handle big datasets. Under this framework, we study the matrix-based data mining algorithms with a focus on the secure top-k eigenvector algorithm. Our approach uses an iterative processing model in which the authorized user interacts with the cloud to achieve the result. In this process, both the source matrix and the intermediate results keep confidential and the client-side incurs low costs. The security of this approach is guaranteed by using Paillier Encryption and a random perturbation technique. We carefully analyze its security under a cloud-specific threat model. Our experimental results show that the proposed method is scalable to big matrices while requiring low client-side costs.
New algorithm for footstep localization using seismic sensors in an indoor environment
Venue: arXiv cs.CE 2013
Year: 2013

In this study, we consider the use of seismic sensors for footstep localization in indoor environments. A popular strategy of localization is to use the measured differences in arrival times of source signals at multiple pairs of receivers. In the literature, most algorithms that are based on time differences of arrival (TDOA) assume that the propagation velocity is a constant as a function of the source position, which is valid for air propagation or even for narrow band signals. However a bounded medium such as a concrete slab (encountered in indoor environement) is usually dispersive and damped. In this study, we demonstrate that under such conditions, the concrete slab can be assimilated to a thin plate; considering a Kelvin-Voigt damping model, we introduce the notion of {\em perceived propagation velocity}, which decreases when the source-sensor distance increases. This peculiar behaviour precludes any possibility to rely on existing localization methods in indoor environment. Therefore, a new localization algorithm that is adapted to a damped and dispersive medium is proposed, using only on the sign of the measured TDOA (SO-TDOA). A simulation and some experimental results are included, to define the performance of this SO-TDOA algorithm.
The Degrees of Freedom Region of Temporally-Correlated MIMO Networks with Delayed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

We consider the temporally-correlated Multiple-Input Multiple-Output (MIMO) broadcast channels (BC) and interference channels (IC) where the transmitter(s) has/have (i) delayed channel state information (CSI) obtained from a latency-prone feedback channel as well as (ii) imperfect current CSIT, obtained, e.g., from prediction on the basis of these past channel samples based on the temporal correlation. The degrees of freedom (DoF) regions for the two-user broadcast and interference MIMO networks with general antenna configuration under such conditions are fully characterized, as a function of the prediction quality indicator. Specifically, a simple unified framework is proposed, allowing to attain optimal DoF region for the general antenna configurations and current CSIT qualities. Such a framework builds upon block-Markov encoding with interference quantization, optimally combining the use of both outdated and instantaneous CSIT. A striking feature of our work is that, by varying the power allocation, every point in the DoF region can be achieved with one single scheme. As a result, instead of checking the achievability of every corner point of the outer bound region, as typically done in the literature, we propose a new systematic way to prove the achievability.
Lending Petri nets and contracts
Venue: arXiv cs.LO 2013
Year: 2013

Choreography-based approaches to service composition typically assume that, after a set of services has been found which correctly play the roles prescribed by the choreography, each service respects his role. Honest services are not protected against adversaries. We propose a model for contracts based on a extension of Petri nets, which allows services to protect themselves while still realizing the choreography. We relate this model with Propositional Contract Logic, by showing a translation of formulae into our Petri nets which preserves the logical notion of agreement, and allows for compositional verification.
Hypothesis Testing in Feedforward Networks with Broadcast Failures
Venue: arXiv cs.IT 2013
Year: 2013

Consider a countably infinite set of nodes, which sequentially make decisions between two given hypotheses. Each node takes a measurement of the underlying truth, observes the decisions from some immediate predecessors, and makes a decision between the given hypotheses. We consider two classes of broadcast failures: 1) each node broadcasts a decision to the other nodes, subject to random erasure in the form of a binary erasure channel; 2) each node broadcasts a randomly flipped decision to the other nodes in the form of a binary symmetric channel. We are interested in whether there exists a decision strategy consisting of a sequence of likelihood ratio tests such that the node decisions converge in probability to the underlying truth. In both cases, we show that if each node only learns from a bounded number of immediate predecessors, then there does not exist a decision strategy such that the decisions converge in probability to the underlying truth. However, in case 1, we show that if each node learns from an unboundedly growing number of predecessors, then the decisions converge in probability to the underlying truth, even when the erasure probabilities converge to 1. We also derive the convergence rate of the error probability. In case 2, we show that if each node learns from all of its previous predecessors, then the decisions converge in probability to the underlying truth when the flipping probabilities of the binary symmetric channels are bounded away from 1/2. In the case where the flipping probabilities converge to 1/2, we derive a necessary condition on the convergence rate of the flipping probabilities such that the decisions still converge to the underlying truth. We also explicitly characterize the relationship between the convergence rate of the error probability and the convergence rate of the flipping probabilities.
Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
Venue: arXiv cs.IT 2013
Year: 2013

We show that real-value approximations of Kolmogorov-Chaitin (K_m) using the algorithmic Coding theorem as calculated from the output frequency of a large set of small deterministic Turing machines with up to 5 states (and 2 symbols), is in agreement with the number of instructions used by the Turing machines producing s, which is consistent with strict integer-value program-size complexity. Nevertheless, K_m proves to be a finer-grained measure and a potential alternative approach to lossless compression algorithms for small entities, where compression fails. We also show that neither K_m nor the number of instructions used shows any correlation with Bennett's Logical Depth LD(s) other than what's predicted by the theory. The agreement between theory and numerical calculations shows that despite the undecidability of these theoretical measures, approximations are stable and meaningful, even for small programs and for short strings. We also announce a first Beta version of an Online Algorithmic Complexity Calculator (OACC), based on a combination of theoretical concepts, as a numerical implementation of the Coding Theorem Method.
Mahotas: Open source software for scriptable computer vision
Venue: arXiv cs.CV 2013
Year: 2013

Mahotas is a computer vision library for Python. It contains traditional image processing functionality such as filtering and morphological operations as well as more modern computer vision functions for feature computation, including interest point detection and local descriptors. The interface is in Python, a dynamic programming language, which is very appropriate for fast development, but the algorithms are implemented in C++ and are tuned for speed. The library is designed to fit in with the scientific software ecosystem in this language and can leverage the existing infrastructure developed in that language. Mahotas is released under a liberal open source license (MIT License) and is available from (http://github.com/luispedro/mahotas) and from the Python Package Index (http://pypi.python.org/pypi/mahotas).
Angle Optimization of Graphs Embedded in the Plane
Venue: arXiv cs.CG 2013
Year: 2013

In this paper we study problems of drawing graphs in the plane using edge length constraints and angle optimization. Specifically we consider the problem of maximizing the minimum angle, the MMA problem. We solve the MMA problem using a spring-embedding approach where two forces are applied to the vertices of the graph: a force optimizing edge lengths and a force optimizing angles. We solve analytically the problem of computing an optimal displacement of a graph vertex optimizing the angles between edges incident to it if the degree of the vertex is at most three. We also apply a numerical approach for computing the forces applied to vertices of higher degree. We implemented our algorithm in Java and present drawings of some graphs.
Privacy in Content-Oriented Networking: Threats and Countermeasures
Venue: arXiv cs.CR 2013
Year: 2013

As the Internet struggles to cope with scalability, mobility, and security issues, new network architectures are being proposed to better accommodate the needs of modern systems and applications. In particular, Content-Oriented Networking (CON) has emerged as a promising next-generation Internet architecture: it sets to decouple content from hosts, at the network layer, by naming data rather than hosts. CON comes with a potential for a wide range of benefits, including reduced congestion and improved delivery speed by means of content caching, simpler configuration of network devices, and security at the data level. However, it remains an interesting open question whether or not, and to what extent, this emerging networking paradigm bears new privacy challenges. In this paper, we provide a systematic privacy analysis of CON and the common building blocks among its various architectural instances in order to highlight emerging privacy threats, and analyze a few potential countermeasures. Finally, we present a comparison between CON and today's Internet in the context of a few privacy concepts, such as, anonymity, censoring, traceability, and confidentiality.
Spectrum Sensing using Distributed Sequential Detection via Noisy Reporting MAC
Venue: arXiv cs.IT 2013
Year: 2013

This paper considers cooperative spectrum sensing algorithms for Cognitive Radios which focus on reducing the number of samples to make a reliable detection. We develop an energy efficient detector with low detection delay using decentralized sequential hypothesis testing. Our algorithm at the Cognitive Radios employs an asynchronous transmission scheme which takes into account the noise at the fusion center. We start with a distributed algorithm, DualSPRT, in which Cognitive Radios sequentially collect the observations, make local decisions using SPRT (Sequential Probability Ratio Test) and send them to the fusion center. The fusion center sequentially processes these received local decisions corrupted by noise, using an SPRT-like procedure to arrive at a final decision. We theoretically analyse its probability of error and average detection delay. We also asymptotically study its performance. Even though DualSPRT performs asymptotically well, a modification at the fusion node provides more control over the design of the algorithm parameters which then performs better at the usual operating probabilities of error in Cognitive Radio systems. We also analyse the modified algorithm theoretically. Later we modify these algorithms to handle uncertainties in SNR and fading.
Low-Complexity LP Decoding of Nonbinary Linear Codes
Venue: arXiv cs.IT 2013
Year: 2013

Linear Programming (LP) decoding of Low-Density Parity-Check (LDPC) codes has attracted much attention in the research community in the past few years. LP decoding has been derived for binary and nonbinary linear codes. However, the most important problem with LP decoding for both binary and nonbinary linear codes is that the complexity of standard LP solvers such as the simplex algorithm remains prohibitively large for codes of moderate to large block length. To address this problem, two low-complexity LP (LCLP) decoding algorithms for binary linear codes have been proposed by Vontobel and Koetter, henceforth called the basic LCLP decoding algorithm and the subgradient LCLP decoding algorithm. In this paper, we generalize these LCLP decoding algorithms to nonbinary linear codes. The computational complexity per iteration of the proposed nonbinary LCLP decoding algorithms scales linearly with the block length of the code. A modified BCJR algorithm for efficient check-node calculations in the nonbinary basic LCLP decoding algorithm is also proposed, which has complexity linear in the check node degree. Several simulation results are presented for nonbinary LDPC codes defined over Z_4, GF(4), and GF(8) using quaternary phase-shift keying and 8-phase-shift keying, respectively, over the AWGN channel. It is shown that for some group-structured LDPC codes, the error-correcting performance of the nonbinary LCLP decoding algorithms is similar to or better than that of the min-sum decoding algorithm.
Modelling the Strategic Alignment of Software Requirements using Goal Graphs
Venue: arXiv cs.SE 2013
Year: 2013

This paper builds on existing Goal Oriented Requirements Engineering (GORE) research by presenting a methodology with a supporting tool for analysing and demonstrating the alignment between software requirements and business objectives. Current GORE methodologies can be used to relate business goals to software goals through goal abstraction in goal graphs. However, we argue that unless the extent of goal-goal contribution is quantified with verifiable metrics and confidence levels, goal graphs are not sufficient for demonstrating the strategic alignment of software requirements. We introduce our methodology using an example software project from Rolls-Royce. We conclude that our methodology can improve requirements by making the relationships to business problems explicit, thereby disambiguating a requirement's underlying purpose and value.