OpenRaiser/Intern-Atlas huggingface dataset:
A tabu search heuristic for the Equitable Coloring Problem
Venue: arXiv cs.DM 2014
Year: 2014

The Equitable Coloring Problem is a variant of the Graph Coloring Problem where the sizes of two arbitrary color classes differ in at most one unit. This additional condition, called equity constraints, arises naturally in several applications. Due to the hardness of the problem, current exact algorithms can not solve large-sized instances. Such instances must be addressed only via heuristic methods. In this paper we present a tabu search heuristic for the Equitable Coloring Problem. This algorithm is an adaptation of the dynamic TabuCol version of Galinier and Hao. In order to satisfy equity constraints, new local search criteria are given. Computational experiments are carried out in order to find the best combination of parameters involved in the dynamic tenure of the heuristic. Finally, we show the good performance of our heuristic over known benchmark instances.
On minimal sets of graded attribute implications
Venue: arXiv cs.AI 2014
Year: 2014

We explore the structure of non-redundant and minimal sets consisting of graded if-then rules. The rules serve as graded attribute implications in object-attribute incidence data and as similarity-based functional dependencies in a similarity-based generalization of the relational model of data. Based on our observations, we derive a polynomial-time algorithm which transforms a given finite set of rules into an equivalent one which has the least size in terms of the number of rules.
Optimal query complexity for estimating the trace of a matrix
Venue: arXiv cs.CC 2014
Year: 2014

Given an implicit $n\times n$ matrix $A$ with oracle access $x^TA x$ for any $x\in \mathbb{R}^n$, we study the query complexity of randomized algorithms for estimating the trace of the matrix. This problem has many applications in quantum physics, machine learning, and pattern matching. Two metrics are commonly used for evaluating the estimators: i) variance; ii) a high probability multiplicative-approximation guarantee. Almost all the known estimators are of the form $\frac{1}{k}\sum_{i=1}^k x_i^T A x_i$ for $x_i\in \mathbb{R}^n$ being i.i.d. for some special distribution. Our main results are summarized as follows. We give an exact characterization of the minimum variance unbiased estimator in the broad class of linear nonadaptive estimators (which subsumes all the existing known estimators). We also consider the query complexity lower bounds for any (possibly nonlinear and adaptive) estimators: (1) We show that any estimator requires $Ω(1/ε)$ queries to have a guarantee of variance at most $ε$. (2) We show that any estimator requires $Ω(\frac{1}{ε^2}\log \frac{1}δ)$ queries to achieve a $(1\pmε)$-multiplicative approximation guarantee with probability at least $1 - δ$. Both above lower bounds are asymptotically tight. As a corollary, we also resolve a conjecture in the seminal work of Avron and Toledo (Journal of the ACM 2011) regarding the sample complexity of the Gaussian Estimator.
Secure Transmission in Multi-Cell Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider physical layer security provisioning in multi-cell massive multiple-input multiple-output (MIMO) systems. Specifically, we consider secure downlink transmission in a multi-cell massive MIMO system with matched-filter precoding and artificial noise (AN) generation at the base station (BS) in the presence of a passive multi-antenna eavesdropper. We investigate the resulting achievable ergodic secrecy rate and the secrecy outage probability for the cases of perfect training and pilot contamination. Thereby, we consider two different AN shaping matrices, namely, the conventional AN shaping matrix, where the AN is transmitted in the null space of the matrix formed by all user channels, and a random AN shaping matrix, which avoids the complexity associated with finding the null space of a large matrix. Our analytical and numerical results reveal that in multi-cell massive MIMO systems employing matched-filter precoding (1) AN generation is required to achieve a positive ergodic secrecy rate if the user and the eavesdropper experience the same path-loss, (2) even with AN generation secure transmission may not be possible if the number of eavesdropper antennas is too large and not enough power is allocated to channel estimation, (3) for a given fraction of power allocated to AN and a given number of users, in case of pilot contamination, the ergodic secrecy rate is not a monotonically increasing function of the number of BS antennas, and (4) random AN shaping matrices provide a favourable performance/complexity tradeoff and are an attractive alternative to conventional AN shaping matrices.
Data-Driven Stochastic Models and Policies for Energy Harvesting Sensor Communications
Venue: arXiv cs.NI 2014
Year: 2014

Energy harvesting from the surroundings is a promising solution to perpetually power-up wireless sensor communications. This paper presents a data-driven approach of finding optimal transmission policies for a solar-powered sensor node that attempts to maximize net bit rates by adapting its transmission parameters, power levels and modulation types, to the changes of channel fading and battery recharge. We formulate this problem as a discounted Markov decision process (MDP) framework, whereby the energy harvesting process is stochastically quantized into several representative solar states with distinct energy arrivals and is totally driven by historical data records at a sensor node. With the observed solar irradiance at each time epoch, a mixed strategy is developed to compute the belief information of the underlying solar states for the choice of transmission parameters. In addition, a theoretical analysis is conducted for a simple on-off policy, in which a predetermined transmission parameter is utilized whenever a sensor node is active. We prove that such an optimal policy has a threshold structure with respect to battery states and evaluate the performance of an energy harvesting node by analyzing the expected net bit rate. The design framework is exemplified with real solar data records, and the results are useful in characterizing the interplay that occurs between energy harvesting and expenditure under various system configurations. Computer simulations show that the proposed policies significantly outperform other schemes with or without the knowledge of short-term energy harvesting and channel fading patterns.
Improper Signaling for Symbol Error Rate Minimization in K-User Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

The rate maximization for the $K$-user interference channels (ICs) has been investigated extensively in the literature. However, the dual problem of minimizing the error probability with given signal modulations and/or data rates of the users is less exploited. In this paper, by utilizing the additional degrees of freedom attained from the improper signaling (versus the conventional proper signaling), we optimize the precoding matrices for the $K$-user single-input single-output (SISO) ICs to achieve minimal pair-wise error probability (PEP) and symbol error rate (SER) with two proposed algorithms, respectively. Compared to conventional proper signaling as well as other state-of-the-art improper signaling designs, our proposed improper signaling schemes achieve notable SER improvement in SISO-ICs under both additive white Gaussian noise (AWGN) channel and cellular system setups. Our study provides another viewpoint for optimizing transmissions in ICs and further justifies the practical benefit of improper signaling in interference-limited communication systems.
Cross-Error Correcting Integer Codes over $\mathbb{Z}_{2^m}$
Venue: arXiv cs.IT 2014
Year: 2014

In this work we investigate codes in $\mathbb{Z}_{2^m}^n$ that can correct errors that occur in just one coordinate of the codeword, with a magnitude of up to a given parameter $t$. We will show upper bounds on these cross codes, derive constructions for linear codes and respective decoding algorithm. The constructions (and decoding algorithms) are given for length $n = 2$ and $n = 3$, but for general $m$ and $t$.
Experimental Demonstration of Array-level Learning with Phase Change Synaptic Devices
Venue: arXiv cs.NE 2014
Year: 2014

The computational performance of the biological brain has long attracted significant interest and has led to inspirations in operating principles, algorithms, and architectures for computing and signal processing. In this work, we focus on hardware implementation of brain-like learning in a brain-inspired architecture. We demonstrate, in hardware, that 2-D crossbar arrays of phase change synaptic devices can achieve associative learning and perform pattern recognition. Device and array-level studies using an experimental 10x10 array of phase change synaptic devices have shown that pattern recognition is robust against synaptic resistance variations and large variations can be tolerated by increasing the number of training iterations. Our measurements show that increase in initial variation from 9 % to 60 % causes required training iterations to increase from 1 to 11.
ELM Solutions for Event-Based Systems
Venue: arXiv cs.NE 2014
Year: 2014

Whilst most engineered systems use signals that are continuous in time, there is a domain of systems in which signals consist of events. Events, like Dirac delta functions, have no meaningful time duration. Many important real-world systems are intrinsically event-based, including the mammalian brain, in which the primary packets of data are spike events, or action potentials. In this domain, signal processing requires responses to spatio-temporal patterns of events. We show that some straightforward modifications to the standard ELM topology produce networks that are able to perform spatio-temporal event processing online with a high degree of accuracy. The modifications involve the re-definition of hidden layer units as synaptic kernels, in which the input delta functions are transformed into continuous-valued signals using a variety of impulse-response functions. This permits the use of linear solution methods in the output layer, which can produce events as output, if modeled as a classifier; the output classes are 'event' or 'no event'. We illustrate the method in application to a spike-processing problem.
Improving Computer Assisted Speech Therapy Through Speech Based Emotion Recognition
Venue: arXiv cs.CY 2014
Year: 2014

Speech therapy consists in a wide range of services whose aim is to prevent, diagnose and treat different types of speech impairments. One of the most important conditions for obtaining favourable and steady results is the "immersing" of the subject as long as possible into therapeutic context: at home, at school/work, on the street. Since nowadays portable computers tend to become habitual accessories, it seems a good idea to create virtual versions of human SLTs and to integrate them into these devices. However one of the main distinctions between a Speech and Language Therapist (SLT) and a Computer Based Speech Therapy System (CBST) arise from the field of emotion intelligence. The inability of current CBSTs to detect emotional state of human subjects leads to inadequate behavioural responses. Furthermore, this "unresponsive" behaviour is perceived as a lack of empathy and, especially when subjects are children, leads to negative emotional state such as frustration. Thus in this article we propose an original emotions recognition framework - named PhonEM - to be integrated in our previous developed CBST - Logomon. The originality consists in both emotions representation (a fuzzy model) and detection (using only subjects' speech stream). These exceptional restrictions along with the fuzzy representation of emotions lie at the origin of our approach and make our task a difficult and, in the same time, an innovative one. As far as we know, this is the first attempt to combine these techniques in order to improve assisted speech therapy and the obtained results encourage as to further develop our CBST.
Kahler: An Implementation of Discrete Exterior Calculus on Hermitian Manifolds
Venue: arXiv cs.NA 2014
Year: 2014

This paper details the techniques and algorithms implemented in Kahler, a Python library that implements discrete exterior calculus on arbitrary Hermitian manifolds. Borrowing techniques and ideas first implemented in PyDEC, Kahler provides a uniquely general framework for computation using discrete exterior calculus. Manifolds can have arbitrary dimension, topology, bilinear Hermitian metrics, and embedding dimension. Kahler comes equipped with tools for generating triangular meshes in arbitrary dimensions with arbitrary topology. Kahler can also generate discrete sharp operators and implement de Rham maps. Computationally intensive tasks are automatically parallelized over the number of cores detected. The program itself is written in Cython--a superset of the Python language that is translated to C and compiled for extra speed. Kahler is applied to several example problems: normal modes of a vibrating membrane, electromagnetic resonance in a cavity, the quantum harmonic oscillator, and the Dirac-Kahler equation. Convergence is demonstrated on random meshes.
Military Simulator - A Case Study of Behaviour Tree and Unity based architecture
Venue: arXiv cs.AI 2014
Year: 2014

In this paper we show how the combination of Behaviour Tree and Utility Based AI architecture can be used to design more realistic bots for Military Simulators. In this work, we have designed a mathematical model of a simulator system which in turn helps in analyzing the results and finding out the various spaces on which our favorable situation might exist, this is done geometrically. In the mathematical model, we have explained the matrix formation and its significance followed up in dynamic programming approach we explained the possible graph formation which will led improvisation of AI, latter we explained the possible geometrical structure of the matrix operations and its impact on a particular decision, we also explained the conditions under which it tend to fail along with a possible solution in future works.
Region Templates: Data Representation and Management for Large-Scale Image Analysis
Venue: arXiv cs.DC 2014
Year: 2014

Distributed memory machines equipped with CPUs and GPUs (hybrid computing nodes) are hard to program because of the multiple layers of memory and heterogeneous computing configurations. In this paper, we introduce a region template abstraction for the efficient management of common data types used in analysis of large datasets of high resolution images on clusters of hybrid computing nodes. The region template provides a generic container template for common data structures, such as points, arrays, regions, and object sets, within a spatial and temporal bounding box. The region template abstraction enables different data management strategies and data I/O implementations, while providing a homogeneous, unified interface to the application for data storage and retrieval. The execution of region templates applications is coordinated by a runtime system that supports efficient execution in hybrid machines. Region templates applications are represented as hierarchical dataflow in which each computing stage may be represented as another dataflow of finer-grain tasks. A number of optimizations for hybrid machines are available in our runtime system, including performance-aware scheduling for maximizing utilization of computing devices and techniques to reduce impact of data transfers between CPUs and GPUs. An experimental evaluation on a state-of-the-art hybrid cluster using a microscopy imaging study shows that this abstraction adds negligible overhead (about 3%) and achieves good scalability.
SAT Modulo Monotonic Theories
Venue: arXiv cs.LO 2014
Year: 2014

We define the concept of a monotonic theory and show how to build efficient SMT (SAT Modulo Theory) solvers, including effective theory propagation and clause learning, for such theories. We present examples showing that monotonic theories arise from many common problems, e.g., graph properties such as reachability, shortest paths, connected components, minimum spanning tree, and max-flow/min-cut, and then demonstrate our framework by building SMT solvers for each of these theories. We apply these solvers to procedural content generation problems, demonstrating major speed-ups over state-of-the-art approaches based on SAT or Answer Set Programming, and easily solving several instances that were previously impractical to solve.
Joint Source-Channel Vector Quantization for Compressed Sensing
Venue: arXiv cs.IT 2014
Year: 2014

We study joint source-channel coding (JSCC) of compressed sensing (CS) measurements using vector quantizer (VQ). We develop a framework for realizing optimum JSCC schemes that enable encoding and transmitting CS measurements of a sparse source over discrete memoryless channels, and decoding the sparse source signal. For this purpose, the optimal design of encoder-decoder pair of a VQ is considered, where the optimality is addressed by minimizing end-to-end mean square error (MSE). We derive a theoretical lower-bound on the MSE performance, and propose a practical encoder-decoder design through an iterative algorithm. The resulting coding scheme is referred to as channel- optimized VQ for CS, coined COVQ-CS. In order to address the encoding complexity issue of the COVQ-CS, we propose to use a structured quantizer, namely low complexity multi-stage VQ (MSVQ). We derive new encoding and decoding conditions for the MSVQ, and then propose a practical encoder-decoder design algorithm referred to as channel-optimized MSVQ for CS, coined COMSVQ-CS. Through simulation studies, we compare the proposed schemes vis-a-vis relevant quantizers.
Power Allocation and Transmitter Switching for Broadcasting with Multiple Energy Harvesting Transmitters
Venue: arXiv cs.IT 2014
Year: 2014

With the advancement of battery technology, energy harvesting communication systems attracted great research attention in recent years. However, energy harvesting communication systems with multiple transmitters and multiple receivers have not been considered yet. In this paper, the problem of broadcasting in a communication system with multiple energy harvesting transmitters and multiple receivers is studied. First, regarding the transmitters as a 'hole transmitter' [1], the optimal total transmission power is obtained and the optimal power allocation policy in [2] is extended to our system setup, with the aim of minimizing the transmission completion time. Then, a simpler power allocation policy is developed to allocate the optimal total transmission power to the data transmissions. As transmitter switching can provide flexibility and robustness to an energy harvesting communication system, especially when a transmitter is broken or the energy harvested by a transmitter is insufficient, a transmitter switching policy is further developed to choose a suitable transmitter to work whenever necessary. The results show that the proposed power allocation policy performs close to the optimal one and outperforms some heuristic ones in terms of transmission completion time. Besides, the proposed transmitter switching policy outperforms some heuristic ones in terms of number of switches.
Continuous Action Recognition Based on Sequence Alignment
Venue: arXiv cs.CV 2014
Year: 2014

Continuous action recognition is more challenging than isolated recognition because classification and segmentation must be simultaneously carried out. We build on the well known dynamic time warping (DTW) framework and devise a novel visual alignment technique, namely dynamic frame warping (DFW), which performs isolated recognition based on per-frame representation of videos, and on aligning a test sequence with a model sequence. Moreover, we propose two extensions which enable to perform recognition concomitant with segmentation, namely one-pass DFW and two-pass DFW. These two methods have their roots in the domain of continuous recognition of speech and, to the best of our knowledge, their extension to continuous visual action recognition has been overlooked. We test and illustrate the proposed techniques with a recently released dataset (RAVEL) and with two public-domain datasets widely used in action recognition (Hollywood-1 and Hollywood-2). We also compare the performances of the proposed isolated and continuous recognition algorithms with several recently published methods.
Network Function Virtualization based on FPGAs:A Framework for all-Programmable network devices
Venue: arXiv cs.NI 2014
Year: 2014

Network Function Virtualization (NFV) refers to the use of commodity hardware resources as the basic platform to perform specialized network functions as opposed to specialized hardware devices. Currently, NFV is mainly implemented based on general purpose processors, or general purpose network processors. In this paper we propose the use of FPGAs as an ideal platform for NFV that can be used to provide both the flexibility of virtualizations and the high performance of the specialized hardware. We present the early attempts of using FPGAs dynamic reconfiguration in network processing applications to provide flexible network functions and we present the opportunities for an FPGA-based NFV platform.
Collection of abstracts of the Workshop on Triangulations in Geometry and Topology at CG Week 2014 in Kyoto
Venue: arXiv cs.CG 2014
Year: 2014

This workshop about triangulations of manifolds in computational geometry and topology was held at the 2014 CG-Week in Kyoto, Japan. It focussed on computational and combinatorial questions regarding triangulations, with the goal of bringing together researchers working on various aspects of triangulations and of fostering a closer collaboration within the computational geometry and topology community. Triangulations are highly suitable for computations due to their clear combinatorial structure. As a consequence, they have been successfully employed in discrete algorithms to solve purely theoretical problems in a broad variety of mathematical research areas (knot theory, polytope theory, 2- and 3-manifold topology, geometry, and others). However, due to the large variety of applications, requirements vary from field to field and thus different types of triangulations, different tools, and different frameworks are used in different areas of research. This is why today closely related research areas are sometimes largely disjoint leaving potential reciprocal benefits unused. To address these potentials a workshop on Triangulations was held at Oberwolfach Research Institute in 2012. Since then many new collaborations between researchers of different mathematical communities have been established. Regarding the computational geometry community, the theory of manifolds continues to contribute to advances in more applied areas of the field. Many researchers are interested in fundamental mathematical research about triangulations and thus will benefit from a broad set of knowledge about different research areas using different techniques. We hope that this workshop brought together researchers from many different fields of computational geometry to have fruitful discussions which will lead to new interdisciplinary collaborations and solutions.
Assessment Model for Opportunistic Routing
Venue: arXiv cs.NI 2014
Year: 2014

This paper proposes an assessment model, based on a new taxonomy, which comprises an evaluation guideline with performance metrics and experimental setup to aid designers in evaluating solutions through fair comparisons. Simulation results are provided based on the proposed model considering Epidemic, PROPHET, Bubble Rap, and Spray and Wait, and showing how they perform under the same set of metrics and scenario