OpenRaiser/Intern-Atlas huggingface dataset:
Coding vs. Spreading for Narrow-Band Interference Suppression
Venue: arXiv cs.IT 2015
Year: 2015

The use of active narrow-band interference (NBI) suppression in direct-sequence spread-spectrum (DS-SS) communications has been extensively studied. In this paper, we address the problem of optimum coding-spreading tradeoff for NBI suppression. With maximum likelihood decoding, we first derive upper bounds on the error probability of coded systems in the presence of a special class of NBI, namely, multi-tone interference with orthogonal signatures. By employing the well-developed bounding techniques, we show there is no advantage in spreading, and hence a low-rate full coding approach is always preferred. Then, we propose a practical low-rate turbo-Hadamard coding approach, in which the NBI suppression is naturally achieved through iterative decoding. The proposed turbo-Hadamard coding approach employs a kind of coded spread-spectrum signalling with time-varying spreading sequences, which is sharply compared with the code-aided DS-SS approach. With a spreading sequence of length 32 and a fixed bandwidth allocated for both approaches, it is shown through extensive simulations that the proposed turbo-Hadamard coding approach outperforms the code-aided DS-SS approach for three types of NBI, even when its transmission information rate is about 5 times higher than that of the code-aided DS-SS approach. The use of the proposed turbo-Hadmard coding approach in multipath fading channels is also discussed.
Stochasticity in pandemic spread over the World Airline Network explained by local flight connections
Venue: arXiv cs.SI 2015
Year: 2015

Massive growth in human mobility has dramatically increased the risk and rate of pandemic spread. Macro-level descriptors of the topology of the World Airline Network (WAN) explains middle and late stage dynamics of pandemic spread mediated by this network, but necessarily regard early stage variation as stochastic. We propose that much of early stage variation can be explained by appropriately characterizing the local topology surrounding the debut location of an outbreak. We measure for each airport the expected force of infection (AEF) which a pandemic originating at that airport would generate. We observe, for a subset of world airports, the minimum transmission rate at which a disease becomes pandemically competent at each airport. We also observe, for a larger subset, the time until a pandemically competent outbreak achieves pandemic status given its debut location. Observations are generated using a highly sophisticated metapopulation reaction-diffusion simulator under a disease model known to well replicate the 2009 influenza pandemic. The robustness of the AEF measure to model misspecification is examined by degrading the network model. AEF powerfully explains pandemic risk, showing correlation of 0.90 to the transmission level needed to give a disease pandemic competence, and correlation of 0.85 to the delay until an outbreak becomes a pandemic. The AEF is robust to model misspecification. For 97% of airports, removing 15% of airports from the model changes their AEF metric by less than 1%. Appropriately summarizing the size, shape, and diversity of an airport's local neighborhood in the WAN accurately explains much of the macro-level stochasticity in pandemic outcomes.
Haptic Shared Control in Steering Operation Based on Cooperative Status Between a Driver and a Driver Assistance System
Venue: arXiv cs.RO 2015
Year: 2015

Haptic shared control is expected to achieve a smooth collaboration between humans and automated systems, because haptics facilitate mutual communication. A methodology for sharing a given task is important to achieve effective shared control. Therefore, the appropriate cooperative relationship between a human operator and automated system should be considered. This paper proposes a methodology to evaluate the cooperative status between the operator and the automated system in the haptic shared control of a steering operation using a pseudo-power pair of torque from each agent and the vehicle lateral velocity as each agent's contribution to vehicle motion. This method allows us to estimate cooperative status based on two axes: the initiative holder and the intent consistency between the two agents. A control method for a lane-keeping assist system (LKAS) that enables drivers to change lanes smoothly is proposed based on the estimated cooperative status. A gain-tuning control method based on the estimated cooperative status is proposed to decrease the assistance system's pseudo-power when intent inconsistency occurs. A method for switching the followed lane to match the driver's and assistance system's intentions is also proposed. A user study using a driving simulator is conducted to demonstrate the effectiveness of the proposed methods. The results demonstrate that the proposed methods facilitate smooth driver-initiated lane changes without significantly affecting the driver's torque or steering wheel angle while significantly improve lane-keeping performance.
Ensembles based on the Rich-Club and how to use them to build soft-communities
Venue: arXiv cs.SI 2015
Year: 2015

Ensembles of networks are used as null-models to discriminate network structures. We present an efficient algorithm, based on the maximal entropy method to generate network ensembles defined by the degree sequence and the rich-club coefficient. The method is applicable for unweighted, undirected networks. The ensembles are used to generate correlated and uncorrelated null--models of a real networks. These ensembles can be used to define the partition of a network into soft communities.
Maximum Pagenumber-k Subgraph is NP-Complete
Venue: arXiv cs.CC 2015
Year: 2015

Given a graph $G$ with a total order defined on its vertices, the Maximum Pagenumber-$k$ Subgraph Problem asks for a maximum subgraph $G'$ of $G$ such that $G'$ can be embedded into a $k$-book when the vertices are placed on the spine according to the specified total order. We show that this problem is NP-complete for $k \geq 2$.
State-space formulation of scalar Preisach hysteresis model for rapid computation in time domain
Venue: arXiv cs.SY 2015
Year: 2015

A state-space formulation of classical scalar Preisach model (CSPM) of hysteresis is proposed. The introduced state dynamics and memory interface allow to use the state equation, which is rapid in calculation, instead of the original Preisach equation. The main benefit of the proposed modeling approach is the reduced computational effort which requires only a single integration over the instantaneous line segment in the Preisach plane. Numerical evaluations of the computation time and model accuracy are provided in comparison to the CSPM which is taken as a reference model.
Transients of platoons with asymmetric and different Laplacians
Venue: arXiv cs.SY 2015
Year: 2015

We consider an asymmetric control of platoons of identical vehicles with nearest-neighbor interaction. Recent results show that if the vehicle uses different asymmetries for position and velocity errors, the platoon has a short transient and low overshoots. In this paper we investigate the properties of vehicles with friction. To achieve consensus, an integral part is added to the controller, making the vehicle a third-order system. We show that the parameters can be chosen so that the platoon behaves as a wave equation with different wave velocities. Simulations suggest that our system has a better performance than other nearest-neighbor scenarios. Moreover, an optimization-based procedure is used to find the controller properties.
Taming the Android AppStore: Lightweight Characterization of Android Applications
Venue: arXiv cs.NI 2015
Year: 2015

There are over 1.2 million applications on the Google Play store today with a large number of competing applications for any given use or function. This creates challenges for users in selecting the right application. Moreover, some of the applications being of dubious origin, there are no mechanisms for users to understand who the applications are talking to, and to what extent. In our work, we first develop a lightweight characterization methodology that can automatically extract descriptions of application network behavior, and apply this to a large selection of applications from the Google App Store. We find several instances of overly aggressive communication with tracking websites, of excessive communication with ad related sites, and of communication with sites previously associated with malware activity. Our results underscore the need for a tool to provide users more visibility into the communication of apps installed on their mobile devices. To this end, we develop an Android application to do just this; our application monitors outgoing traffic, associates it with particular applications, and then identifies destinations in particular categories that we believe suspicious or else important to reveal to the end-user.
Model Checking Constraint LTL over Trees
Venue: arXiv cs.LO 2015
Year: 2015

Constraint automata are an adaptation of Büchi-automata that process data words where the data comes from some relational structure S. Every transition of such an automaton comes with constraints in terms of the relations of S. A transition can only be fired if the current and the next data values satisfy all constraints of this transition. These automata have been used in the setting where S is a linear order for deciding constraint LTL with constraints over S. In this paper, S is the infinitely branching infinite order tree T. We provide a PSPACE algorithm for emptiness of T-constraint automata. This result implies PSPACE-completeness of the satisfiability and the model checking problem for constraint LTL with constraints over T.
Nested Weighted Automata
Venue: arXiv cs.FL 2015
Year: 2015

Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time. In nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
Venue: arXiv cs.CC 2015
Year: 2015

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables. We prove the following results. 1. Over fields of characteristic zero, for every constant $μ$ such that $0 \leq μ< 1$, we give an explicit family of polynomials $\{P_{N}\}$, where $P_{N}$ is of degree $n$ in $N = n^{O(1)}$ variables, such that any representation of the above type for $P_{N}$ with $s = N^μ$ requires $Td \geq n^{Ω(\sqrt{n})}$. This strengthens a recent result of Kayal and Saha [KS14a] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for $s = \sqrt{n}$) would separate VP and VNP[KS14a]. 2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when $T$ and the individual degree of each variable in $P$ are at most $\log^{O(1)} N$ and $s \leq N^μ$ for any constant $μ< 1/2$. We get quasipolynomial running time when $s < \log^{O(1)} N$. The PIT algorithm is obtained by combining our lower bounds with the hardness-randomness tradeoffs developed in [DSY09, KI04]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case $s=2$), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits.
Finding Any Nontrivial Coarse Correlated Equilibrium Is Hard
Venue: arXiv cs.GT 2015
Year: 2015

One of the most appealing aspects of the (coarse) correlated equilibrium concept is that natural dynamics quickly arrive at approximations of such equilibria, even in games with many players. In addition, there exist polynomial-time algorithms that compute exact (coarse) correlated equilibria. In light of these results, a natural question is how good are the (coarse) correlated equilibria that can arise from any efficient algorithm or dynamics. In this paper we address this question, and establish strong negative results. In particular, we show that in multiplayer games that have a succinct representation, it is NP-hard to compute any coarse correlated equilibrium (or approximate coarse correlated equilibrium) with welfare strictly better than the worst possible. The focus on succinct games ensures that the underlying complexity question is interesting; many multiplayer games of interest are in fact succinct. Our results imply that, while one can efficiently compute a coarse correlated equilibrium, one cannot provide any nontrivial welfare guarantee for the resulting equilibrium, unless P=NP. We show that analogous hardness results hold for correlated equilibria, and persist under the egalitarian objective or Pareto optimality. To complement the hardness results, we develop an algorithmic framework that identifies settings in which we can efficiently compute an approximate correlated equilibrium with near-optimal welfare. We use this framework to develop an efficient algorithm for computing an approximate correlated equilibrium with near-optimal welfare in aggregative games.
A Characterization of Visibility Graphs for Pseudo-Polygons
Venue: arXiv cs.CG 2015
Year: 2015

In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary conditions based off our identified properties. We then prove that these necessary conditions are also sufficient via a reduction to a characterization of vertex-edge visibility graphs given by O'Rourke and Streinu.
Preprint Touch-less Interactive Augmented Reality Game on Vision Based Wearable Device
Venue: arXiv cs.HC 2015
Year: 2015

This is the preprint version of our paper on Personal and Ubiquitous Computing. There is an increasing interest in creating pervasive games based on emerging interaction technologies. In order to develop touch-less, interactive and augmented reality games on vision-based wearable device, a touch-less motion interaction technology is designed and evaluated in this work. Users interact with the augmented reality games with dynamic hands/feet gestures in front of the camera, which triggers the interaction event to interact with the virtual object in the scene. Three primitive augmented reality games with eleven dynamic gestures are developed based on the proposed touch-less interaction technology as proof. At last, a comparing evaluation is proposed to demonstrate the social acceptability and usability of the touch-less approach, running on a hybrid wearable framework or with Google Glass, as well as workload assessment, user's emotions and satisfaction.
Social Trust Prediction via Max-norm Constrained 1-bit Matrix Completion
Venue: arXiv cs.SI 2015
Year: 2015

Social trust prediction addresses the significant problem of exploring interactions among users in social networks. Naturally, this problem can be formulated in the matrix completion framework, with each entry indicating the trustness or distrustness. However, there are two challenges for the social trust problem: 1) the observed data are with sign (1-bit) measurements; 2) they are typically sampled non-uniformly. Most of the previous matrix completion methods do not well handle the two issues. Motivated by the recent progress of max-norm, we propose to solve the problem with a 1-bit max-norm constrained formulation. Since max-norm is not easy to optimize, we utilize a reformulation of max-norm which facilitates an efficient projected gradient decent algorithm. We demonstrate the superiority of our formulation on two benchmark datasets.
Recent Advances in Real Geometric Reasoning
Venue: arXiv cs.SC 2015
Year: 2015

In the 1930s Tarski showed that real quantifier elimination was possible, and in 1975 Collins gave a remotely practicable method, albeit with doubly-exponential complexity, which was later shown to be inherent. We discuss some of the recent major advances in Collins method: such as an alternative approach based on passing via the complexes, and advances which come closer to "solving the question asked" rather than "solving all problems to do with these polynomials".
Straight-line Drawability of a Planar Graph Plus an Edge
Venue: arXiv cs.CG 2015
Year: 2015

We investigate straight-line drawings of topological graphs that consist of a planar graph plus one edge, also called almost-planar graphs. We present a characterization of such graphs that admit a straight-line drawing. The characterization enables a linear-time testing algorithm to determine whether an almost-planar graph admits a straight-line drawing, and a linear-time drawing algorithm that constructs such a drawing, if it exists. We also show that some almost-planar graphs require exponential area for a straight-line drawing.
Approximation Algorithms for Inventory Problems with Submodular or Routing Costs
Venue: arXiv cs.DS 2015
Year: 2015

We consider the following two deterministic inventory optimization problems over a finite planning horizon $T$ with non-stationary demands. (a) Submodular Joint Replenishment Problem: This involves multiple item types and a single retailer who faces demands. In each time step, any subset of item-types can be ordered incurring a joint ordering cost which is submodular. Moreover, items can be held in inventory while incurring a holding cost. The objective is find a sequence of orders that satisfies all demands and minimizes the total ordering and holding costs. (b) Inventory Routing Problem: This involves a single depot that stocks items, and multiple retailer locations facing demands. In each time step, any subset of locations can be visited using a vehicle originating from the depot. There is also cost incurred for holding items at any retailer. The objective here is to satisfy all demands while minimizing the sum of routing and holding costs. We present a unified approach that yields $\mathcal{O}\left(\frac{\log T}{\log\log T}\right)$-factor approximation algorithms for both problems when the holding costs are polynomial functions. A special case is the classic linear holding cost model, wherein this is the first sub-logarithmic approximation ratio for either problem.
Symmetric matrix inversion using modified Gaussian elimination
Venue: arXiv cs.MS 2015
Year: 2015

In this paper we present two different variants of method for symmetric matrix inversion, based on modified Gaussian elimination. Both methods avoid computation of square roots and have a reduced machine time's spending. Further, both of them can be used efficiently not only for positive (semi-) definite, but for any non-singular symmetric matrix inversion. We use simulation to verify results, which represented in this paper.
Quantitative Games under Failures
Venue: arXiv cs.GT 2015
Year: 2015

We study a generalisation of sabotage games, a model of dynamic network games introduced by van Benthem. The original definition of the game is inherently finite and therefore does not allow one to model infinite processes. We propose an extension of the sabotage games in which the first player (Runner) traverses an arena with dynamic weights determined by the second player (Saboteur). In our model of quantitative sabotage games, Saboteur is now given a budget that he can distribute amongst the edges of the graph, whilst Runner attempts to minimise the quantity of budget witnessed while completing his task. We show that, on the one hand, for most of the classical cost functions considered in the literature, the problem of determining if Runner has a strategy to ensure a cost below some threshold is EXPTIME-complete. On the other hand, if the budget of Saboteur is fixed a priori, then the problem is in PTIME for most cost functions. Finally, we show that restricting the dynamics of the game also leads to better complexity.
Constructive Interference through Symbol Level Precoding for Multi-level Modulation
Venue: arXiv cs.IT 2015
Year: 2015

The constructive interference concept in the downlink of multiple-antenna systems is addressed in this paper. The concept of the joint exploitation of the channel state information (CSI) and data information (DI) is discussed. Using symbol-level precoding, the interference between data streams is transformed Under certain conditions into useful signal that can improve the signal to interference noise ratio (SINR) of the downlink transmissions. In the previous work, different constructive interference precoding techniques have been proposed for the MPSK scenario. In this context, a novel constructive interference precoding technique that tackles the transmit power minimization (min-power) with individual SINR constraints at each user's receivers is proposed assuming MQAM modulation. Extensive simulations are performed to validate the proposed technique.
Overlapping Communities Detection via Measure Space Embedding
Venue: arXiv cs.LG 2015
Year: 2015

We present a new algorithm for community detection. The algorithm uses random walks to embed the graph in a space of measures, after which a modification of $k$-means in that space is applied. The algorithm is therefore fast and easily parallelizable. We evaluate the algorithm on standard random graph benchmarks, including some overlapping community benchmarks, and find its performance to be better or at least as good as previously known algorithms. We also prove a linear time (in number of edges) guarantee for the algorithm on a $p,q$-stochastic block model with $p \geq c\cdot N^{-\frac{1}{2} + ε}$ and $p-q \geq c' \sqrt{p N^{-\frac{1}{2} + ε} \log N}$.
Evaluating Dynamic File Striping For Lustre
Venue: arXiv cs.OS 2015
Year: 2015

We define dynamic striping as the ability to assign different Lustre striping characteristics to contiguous segments of a file as it grows. In this paper, we evaluate the effects of dynamic striping using a watermark-based strategy where the stripe count or width is increased once a file's size exceeds one of the chosen watermarks. To measure the performance of this strategy we used a modified version of the IOR benchmark, a netflow analysis workload, and the blastn algorithm from NCBI BLAST. The results indicate that dynamic striping is beneficial to tasks with unpredictable data file size and large sequential reads, but are less conclusive for workloads with significant random read phases.