OpenRaiser/Intern-Atlas huggingface dataset:
Graph isomorphism completeness for trapezoid graphs
Venue: arXiv cs.DM 2015
Year: 2015

The complexity of the graph isomorphism problem for trapezoid graphs has been open over a decade. This paper shows that the problem is GI-complete. More precisely, we show that the graph isomorphism problem is GI-complete for comparability graphs of partially ordered sets with interval dimension 2 and height 3. In contrast, the problem is known to be solvable in polynomial time for comparability graphs of partially ordered sets with interval dimension at most 2 and height at most 2.
Measuring Software Quality in Use: State-of-the-Art and Research Challenges
Venue: arXiv cs.SE 2015
Year: 2015

Software quality in use comprises quality from the user's perspective. It has gained its importance in e-government applications, mobile-based applications, embedded systems, and even business process development. User's decisions on software acquisitions are often ad hoc or based on preference due to difficulty in quantitatively measuring software quality in use. But, why is quality-in-use measurement difficult? Although there are many software quality models, to the authors' knowledge no works survey the challenges related to software quality-in-use measurement. This article has two main contributions: 1) it identifies and explains major issues and challenges in measuring software quality in use in the context of the ISO SQuaRE series and related software quality models and highlights open research areas; and 2) it sheds light on a research direction that can be used to predict software quality in use. In short, the quality-in-use measurement issues are related to the complexity of the current standard models and the limitations and incompleteness of the customized software quality models. A sentiment analysis of software reviews is proposed to deal with these issues.
Sample compression schemes for VC classes
Venue: arXiv cs.LG 2015
Year: 2015

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size $k$ means that given an arbitrary list of labeled examples, one can retain only $k$ of them in a way that allows to recover the labels of all other examples in the list. They showed that compression implies PAC learnability for binary-labeled classes, and asked whether the other direction holds. We answer their question and show that every concept class $C$ with VC dimension $d$ has a sample compression scheme of size exponential in $d$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.
Pragmatic Requirements for Adaptive Systems: a Goal-Driven Modelling and Analysis Approach
Venue: arXiv cs.SE 2015
Year: 2015

Goal-models (GM) have been used in adaptive systems engineering for their ability to capture the different ways to fulfill the requirements. Contextual GM (CGM) extend these models with the notion of context and context-dependent applicability of goals. In this paper, we observe that the interpretation of a goal achievement is itself context-dependent. Thus, we introduce the notion of Pragmatic Goals which have a dynamic satisfaction criteria. We also developed and evaluated an algorithm to decide the Pragmatic CGM's achievability. Finally, we performed several experiments to evaluate and to compare our algorithm against human judgment and concluded that the specification of context-dependent goals' applicability and interpretations make it hard for domain stakeholders to decide whether the model covers all possibilities, both in terms of time and accuracy, thus showing the importance and contribution of our algorithm.
A note on optimal experiment design for nonlinear systems using dynamic programming
Venue: arXiv cs.SY 2015
Year: 2015

We present a method of solving the T-optimal design problem for nonlinear dynamical systems using dynamic programming. In contrast with previous dynamic programming formulations, we avoid adding an equation for the dispersion to the system state, allowing for more efficient solutions.
Isotropically Random Orthogonal Matrices: Performance of LASSO and Minimum Conic Singular Values
Venue: arXiv cs.IT 2015
Year: 2015

Recently, the precise performance of the Generalized LASSO algorithm for recovering structured signals from compressed noisy measurements, obtained via i.i.d. Gaussian matrices, has been characterized. The analysis is based on a framework introduced by Stojnic and heavily relies on the use of Gordon's Gaussian min-max theorem (GMT), a comparison principle on Gaussian processes. As a result, corresponding characterizations for other ensembles of measurement matrices have not been developed. In this work, we analyze the corresponding performance of the ensemble of isotropically random orthogonal (i.r.o.) measurements. We consider the constrained version of the Generalized LASSO and derive a sharp characterization of its normalized squared error in the large-system limit. When compared to its Gaussian counterpart, our result analytically confirms the superiority in performance of the i.r.o. ensemble. Our second result, derives an asymptotic lower bound on the minimum conic singular values of i.r.o. matrices. This bound is larger than the corresponding bound on Gaussian matrices. To prove our results we express i.r.o. matrices in terms of Gaussians and show that, with some modifications, the GMT framework is still applicable.
The Social System Identification Problem
Venue: arXiv cs.SI 2015
Year: 2015

The focus of this paper is modeling what we call a Social Radar, i.e. a method to estimate the relative influence between social agents, by sampling their opinions and as they evolve, after injecting in the network stubborn agents. The stubborn agents opinion is not influenced by the peers they seek to sway, and their opinion bias is the known input to the social network system. The novelty is in the model presented to probe a social network and the solution of the associated regression problem. The model allows to map the observed opinion onto system equations that can be used to infer the social graph and the amount of trust that characterizes the links.
Fractional Pilot Reuse in Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Pilot contamination is known to be one of the main impairments for massive MIMO multi-cell communications. Inspired by the concept of fractional frequency reuse and by recent contributions on pilot reutilization among non-adjacent cells, we propose a new pilot allocation scheme to mitigate this effect. The key idea is to allow users in neighboring cells that are closest to their base stations to reuse the same pilot sequences. Focusing on the uplink, we obtain expressions for the overall spectral efficiency per cell for different linear combining techniques at the base station and use them to obtain both the optimal pilot reuse parameters and the optimal number of scheduled users. Numerical results show a remarkable improvement in terms of spectral efficiency with respect to the existing techniques.
A Survey on Approximation Mechanism Design without Money for Facility Games
Venue: arXiv cs.GT 2015
Year: 2015

In a facility game one or more facilities are placed in a metric space to serve a set of selfish agents whose addresses are their private information. In a classical facility game, each agent wants to be as close to a facility as possible, and the cost of an agent can be defined as the distance between her location and the closest facility. In an obnoxious facility game, each agent wants to be far away from all facilities, and her utility is the distance from her location to the facility set. The objective of each agent is to minimize her cost or maximize her utility. An agent may lie if, by doing so, more benefit can be obtained. We are interested in social choice mechanisms that do not utilize payments. The game designer aims at a mechanism that is strategy-proof, in the sense that any agent cannot benefit by misreporting her address, or, even better, group strategy-proof, in the sense that any coalition of agents cannot all benefit by lying. Meanwhile, it is desirable to have the mechanism to be approximately optimal with respect to a chosen objective function. Several models for such approximation mechanism design without money for facility games have been proposed. In this paper we briefly review these models and related results for both deterministic and randomized mechanisms, and meanwhile we present a general framework for approximation mechanism design without money for facility games.
User Profiling Trends, Techniques and Applications
Venue: arXiv cs.IR 2015
Year: 2015

The Personalization of information has taken recommender systems at a very high level. With personalization these systems can generate user specific recommendations accurately and efficiently. User profiling helps personalization, where information retrieval is done to personalize a scenario which maintains a separate user profile for individual user. The main objective of this paper is to explore this field of personalization in context of user profiling, to help researchers make aware of the user profiling. Various trends, techniques and Applications have been discussed in paper which will fulfill this motto.
P-score: A Publication-based Metric for Academic Productivity
Venue: arXiv cs.DL 2015
Year: 2015

In this work we propose a metric to assess academic productivity based on publication outputs. We are interested in knowing how well a research group in an area of knowledge is doing relatively to a pre-selected set of reference groups, where each group is composed by academics or researchers. To assess academic productivity we propose a new metric, which we call P-score. Our metric P-score assigns weights to venues using only the publication patterns of selected reference groups. This implies that P-score does not depend on citation data and thus, that it is simpler to compute particularly in contexts in which citation data is not easily available. Also, preliminary experiments suggest that P-score preserves strong correlation with citation-based metrics.
An Analytical Formulation of Power System Oscillation Frequency
Venue: arXiv cs.SY 2015
Year: 2015

This letter proposes an analytical approach to formulate the power system oscillation frequency under a large disturbance. A fact is revealed that the oscillation frequency is only the function of the oscillation amplitude when the system's model and operating condition are fixed. Case studies also show that this function is damping-insensitive and could be applied to an inter-area model of a multi-machine power system.
SIRS Epidemics on Complex Networks: Concurrence of Exact Markov Chain and Approximated Models
Venue: arXiv cs.SI 2015
Year: 2015

We study the SIRS (Susceptible-Infected-Recovered-Susceptible) spreading processes over complex networks, by considering its exact $3^n$-state Markov chain model. The Markov chain model exhibits an interesting connection with its $2n$-state nonlinear "mean-field" approximation and the latter's corresponding linear approximation. We show that under the specific threshold where the disease-free state is a globally stable fixed point of both the linear and nonlinear models, the exact underlying Markov chain has an $O(\log n)$ mixing time, which means the epidemic dies out quickly. In fact, the epidemic eradication condition coincides for all the three models. Furthermore, when the threshold condition is violated, which indicates that the linear model is not stable, we show that there exists a unique second fixed point for the nonlinear model, which corresponds to the endemic state. We also investigate the effect of adding immunization to the SIRS epidemics by introducing two different models, depending on the efficacy of the vaccine. Our results indicate that immunization improves the threshold of epidemic eradication. Furthermore, the common threshold for fast-mixing of the Markov chain and global stability of the disease-free fixed point improves by the same factor for the vaccination-dominant model.
A Closed-Loop UL Power Control Scheme for Interference Mitigation in Dynamic TD-LTE Systems
Venue: arXiv cs.NI 2015
Year: 2015

The TD-LTE system is envisaged to adopt dynamic time division duplexing (TDD) transmissions for small cells to adapt their communication service to the fast variation of downlink (DL) and uplink (UL) traffic demands. However, different DL/UL directions for the same subframe in adjacent cells will result in new destructive interference components, i.e., eNB-to-eNB and UE-to-UE, with levels that can significantly differ from one subframe to another. In this paper, a feasible UL power control mechanism is proposed to manage eNB-to-eNB interference, where different UL power control parameters are set based on different interference level. We consider the geometric location information and the subframe set selection process about adjacent eNBs when the interference level is estimated. The performance of the proposed scheme is evaluated through system level simulations and it is shown that the scheme can achieve preferable improvement in terms of UL average and 5%-ile packet throughputs compared with the original scheme without power control. Also, the UE-to-UE interference is not worse when the UE transmit power become higher.
Sampled-data $H^{\infty}$ Optimization for Self-interference Suppression in Baseband Signal Subspaces
Venue: arXiv cs.SY 2015
Year: 2015

In this article, we propose a design method of selfinterference cancelers for wireless relay stations taking account of the baseband signal subspace. The problem is first formulated as a sampled-data $H^{\infty}$ control problem with a generalized sampler and a generalized hold, which can be reduced to a discretetime $\ell^2$-induced norm minimization problem. Taking account of the implementation of the generalized sampler and hold, we adopt the filter-sampler structure for the generalized sampler, and the uspampler-filter-hold structure for the generalized hold. Under these implementation constraints, we reformulate the problem as a standard discrete-time $H^{\infty}$ control problem by using the discrete-time lifting technique. A simulation result is shown to illustrate the effectiveness of the proposed method.
Gibbs Sampling with Low-Power Spiking Digital Neurons
Venue: arXiv cs.NE 2015
Year: 2015

Restricted Boltzmann Machines and Deep Belief Networks have been successfully used in a wide variety of applications including image classification and speech recognition. Inference and learning in these algorithms uses a Markov Chain Monte Carlo procedure called Gibbs sampling. A sigmoidal function forms the kernel of this sampler which can be realized from the firing statistics of noisy integrate-and-fire neurons on a neuromorphic VLSI substrate. This paper demonstrates such an implementation on an array of digital spiking neurons with stochastic leak and threshold properties for inference tasks and presents some key performance metrics for such a hardware-based sampler in both the generative and discriminative contexts.
Averaged Hausdorff Approximations of Pareto Fronts based on Multiobjective Estimation of Distribution Algorithms
Venue: arXiv cs.AI 2015
Year: 2015

In the a posteriori approach of multiobjective optimization the Pareto front is approximated by a finite set of solutions in the objective space. The quality of the approximation can be measured by different indicators that take into account the approximation's closeness to the Pareto front and its distribution along the Pareto front. In particular, the averaged Hausdorff indicator prefers an almost uniform distribution. An observed drawback of multiobjective estimation of distribution algorithms (MEDAs) is that - as common for randomized metaheuristics - the final population usually is not uniformly distributed along the Pareto front. Therefore, we propose a postprocessing strategy which consists of applying the averaged Hausdorff indicator to the complete archive of generated solutions after optimization in order to select a uniformly distributed subset of nondominated solutions from the archive. In this paper, we put forward a strategy for extracting the above described subset. The effectiveness of the proposal is contrasted in a series of experiments that involve different MEDAs and filtering techniques.
Are Markov Models Effective for Storage Reliability Modelling?
Venue: arXiv cs.PF 2015
Year: 2015

Continuous Time Markov Chains (CTMC) have been used extensively to model reliability of storage systems. While the exponentially distributed sojourn time of Markov models is widely known to be unrealistic (and it is necessary to consider Weibull-type models for components such as disks), recent work has also highlighted some additional infirmities with the CTMC model, such as the ability to handle repair times. Due to the memoryless property of these models, any failure or repair of one component resets the "clock" to zero with any partial repair or aging in some other subsystem forgotten. It has therefore been argued that simulation is the only accurate technique available for modelling the reliability of a storage system with multiple components. We show how both the above problematic aspects can be handled when we consider a careful set of approximations in a detailed model of the system. A detailed model has many states, and the transitions between them and the current state captures the "memory" of the various components. We model a non-exponential distribution using a sum of exponential distributions, along with the use of a CTMC solver in a probabilistic model checking tool that has support for reducing large state spaces. Furthermore, it is possible to get results close to what is obtained through simulation and at much lower cost.
Formation of Robust Multi-Agent Networks Through Self-Organizing Random Regular Graphs
Venue: arXiv cs.MA 2015
Year: 2015

Multi-agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. One family of such graphs is the random regular graphs. In this paper, we present a decentralized scheme for transforming any connected interaction graph with a possibly non-integer average degree of k into a connected random m-regular graph for some m in [k, k + 2]. Accordingly, the agents improve the robustness of the network with a minimal change in the overall sparsity by optimizing the graph connectivity through the proposed local operations.
Learning Embedding Representations for Knowledge Inference on Imperfect and Incomplete Repositories
Venue: arXiv cs.AI 2015
Year: 2015

This paper considers the problem of knowledge inference on large-scale imperfect repositories with incomplete coverage by means of embedding entities and relations at the first attempt. We propose IIKE (Imperfect and Incomplete Knowledge Embedding), a probabilistic model which measures the probability of each belief, i.e. $\langle h,r,t\rangle$, in large-scale knowledge bases such as NELL and Freebase, and our objective is to learn a better low-dimensional vector representation for each entity ($h$ and $t$) and relation ($r$) in the process of minimizing the loss of fitting the corresponding confidence given by machine learning (NELL) or crowdsouring (Freebase), so that we can use $||{\bf h} + {\bf r} - {\bf t}||$ to assess the plausibility of a belief when conducting inference. We use subsets of those inexact knowledge bases to train our model and test the performances of link prediction and triplet classification on ground truth beliefs, respectively. The results of extensive experiments show that IIKE achieves significant improvement compared with the baseline and state-of-the-art approaches.
Harmonized Cellular and Distributed Massive MIMO: Load Balancing and Scheduling
Venue: arXiv cs.IT 2015
Year: 2015

Multi-tier networks with large-array base stations (BSs) that are able to operate in the "massive MIMO" regime are envisioned to play a key role in meeting the exploding wireless traffic demands. Operated over small cells with reciprocity-based training, massive MIMO promises large spectral efficiencies per unit area with low overheads. Also, near-optimal user-BS association and resource allocation are possible in cellular massive MIMO HetNets using simple admission control mechanisms and rudimentary BS schedulers, since scheduled user rates can be predicted a priori with massive MIMO. Reciprocity-based training naturally enables coordinated multi-point transmission (CoMP), as each uplink pilot inherently trains antenna arrays at all nearby BSs. In this paper we consider a distributed-MIMO form of CoMP, which improves cell-edge performance without requiring channel state information exchanges among cooperating BSs. We present methods for harmonized operation of distributed and cellular massive MIMO in the downlink that optimize resource allocation at a coarser time scale across the network. We also present scheduling policies at the resource block level which target approaching the optimal allocations. Simulations reveal that the proposed methods can significantly outperform the network-optimized cellular-only massive MIMO operation (i.e., operation without CoMP), especially at the cell edge.
The Problem of Peak-to-Average Power Ratio in OFDM Systems
Venue: arXiv cs.IT 2015
Year: 2015

Orthogonal Frequency Division Multiplexing (OFDM) is widely used in many digital communication systems due to its advantages such us high bit rate, strong immunity to multipath and high spectral efficiency but it suffers a high Peak-to-Average Power Ratio (PAPR) at the transmitted signal. It is very important to deal with PAPR reduction in OFDM systems to avoid signal degradation. Currently, the PAPR problem is an active area of research and in this paper we present several techniques and that mathematically analyzed. Moreover their advantages and disadvantages have been enumerated in order to provide the readers the actual situation of the PAPR problem.
Do current lattice Boltzmann methods for diffusion and diffusion-type equations respect maximum principles and the non-negative constraint?
Venue: arXiv cs.NA 2015
Year: 2015

The lattice Boltzmann method (LBM) has established itself as a valid numerical method in computational fluid dynamics. Recently, multiple-relaxation-time LBM has been proposed to simulate anisotropic advection-diffusion processes. The governing differential equations of advective-diffusive systems are known to satisfy maximum principles, comparison principles, the non-negative constraint, and the decay property. In this paper, it will be shown that current single- and multiple-relaxation-time lattice Boltzmann methods fail to preserve these mathematical properties for transient diffusion-type equations. It will also be shown that the discretization of Dirichlet boundary conditions will affect the performance of lattice Boltzmann methods in meeting these mathematical principles. A new way of discretizing the Dirichlet boundary conditions is also proposed. Several benchmark problems have been solved to illustrate the performance of lattice Boltzmann methods and the effect of discretization of boundary conditions with respect to the aforementioned mathematical properties for transient diffusion and advection-diffusion equations.