OpenRaiser/Intern-Atlas huggingface dataset:
The structure and topology of rooted weighted trees modeling layered cyber-security systems
Venue: arXiv cs.DM 2016
Year: 2016

In this paper we consider a layered-security model in which the containers and their nestings are given in the form of a rooted tree $T$. A {\em cyber-security model\/} is an ordered three-tuple $M = (T, C, P)$ where $C$ and $P$ are multisets of {\em penetration costs\/} for the containers and {\em target-acquisition values\/} for the prizes that are located within the containers, respectively, both of the same cardinality as the set of the non-root vertices of $T$. The problem that we study is to assign the penetration costs to the edges and the target-acquisition values to the vertices of the tree $T$ in such a way that minimizes the total prize that an attacker can acquire given a limited {\em budget}. For a given assignment of costs and target values we obtain a {\em security system}, and we discuss three types of them: {\em improved}, {\em good}, and {\em optimal}. We show that in general it is not possible to develop an optimal security system for a given cyber-security model $M$. We define P- and C-models where the penetration costs and prizes, respectively, all have unit value. We show that if $T$ is a rooted tree such that any P- or C-model $M = (T,C,P)$ has an optimal security system, then $T$ is one of the following types: (i) a rooted path, (ii) a rooted star, (iii) a rooted 3-caterpillar, or (iv) a rooted 4-spider. Conversely, if $T$ is one of these four types of trees, then we show that any P- or C-model $M = (T,C,P)$ does have an optimal security system\@. Finally, we study a duality between P- and C-models that allows us to translate results for P-models into corresponding results for C-models and vice versa. The results obtained give us some mathematical insights into how layered-security defenses should be organized.
Tighter Loop Bound Analysis (Technical report)
Venue: arXiv cs.PL 2016
Year: 2016

We present a new algorithm for computing upper bounds on the number of executions of each program instruction during any single program run. The upper bounds are expressed as functions of program input values. The algorithm is primarily designed to produce bounds that are relatively tight, i.e. not unnecessarily blown up. The upper bounds for instructions allow us to infer loop bounds, i.e.~upper bounds on the number of loop iterations. Experimental results show that the algorithm implemented in a prototype tool Looperman often produces tighter bounds than current tools for loop bound analysis.
Parallel Equivalence Class Sorting: Algorithms, Lower Bounds, and Distribution-Based Analysis
Venue: arXiv cs.DS 2016
Year: 2016

We study parallel comparison-based algorithms for finding all equivalence classes of a set of $n$ elements, where sorting according to some total order is not possible. Such scenarios arise, for example, in applications, such as in distributed computer security, where each of $n$ agents are working to identify the private group to which they belong, with the only operation available to them being a zero-knowledge pairwise-comparison (which is sometimes called a "secret handshake") that reveals only whether two agents are in the same group or in different groups. We provide new parallel algorithms for this problem, as well as new lower bounds and distribution-based analysis.
Item Popularity Prediction in E-commerce Using Image Quality Feature Vectors
Venue: arXiv cs.CV 2016
Year: 2016

Online retail is a visual experience- Shoppers often use images as first order information to decide if an item matches their personal style. Image characteristics such as color, simplicity, scene composition, texture, style, aesthetics and overall quality play a crucial role in making a purchase decision, clicking on or liking a product listing. In this paper we use a set of image features that indicate quality to predict product listing popularity on a major e-commerce website, Etsy. We first define listing popularity through search clicks, favoriting and purchase activity. Next, we infer listing quality from the pixel-level information of listed images as quality features. We then compare our findings to text-only models for popularity prediction. Our initial results indicate that a combined image and text modeling of product listings outperforms text-only models in popularity prediction.
Deformable Parts Correlation Filters for Robust Visual Tracking
Venue: arXiv cs.CV 2016
Year: 2016

Deformable parts models show a great potential in tracking by principally addressing non-rigid object deformations and self occlusions, but according to recent benchmarks, they often lag behind the holistic approaches. The reason is that potentially large number of degrees of freedom have to be estimated for object localization and simplifications of the constellation topology are often assumed to make the inference tractable. We present a new formulation of the constellation model with correlation filters that treats the geometric and visual constraints within a single convex cost function and derive a highly efficient optimization for MAP inference of a fully-connected constellation. We propose a tracker that models the object at two levels of detail. The coarse level corresponds a root correlation filter and a novel color model for approximate object localization, while the mid-level representation is composed of the new deformable constellation of correlation filters that refine the object location. The resulting tracker is rigorously analyzed on a highly challenging OTB, VOT2014 and VOT2015 benchmarks, exhibits a state-of-the-art performance and runs in real-time.
Pulse Shaped OFDM for 5G Systems
Venue: arXiv cs.IT 2016
Year: 2016

OFDM-based waveforms with filtering or windowing functionalities are considered key enablers for a flexible air-interface design for multi-service support in future 5G systems. One candidate from this category of waveforms is pulse shaped OFDM, which follows the idea of subcarrier filtering and aims at fully maintaining the advantages of standard OFDM systems while addressing their drawbacks. In this paper, we elaborate on several pulse shaping design methods, and show how pulse shapes can be exploited as an additional degree of freedom to provide better frequency localization and more efficient spectrum utilization under a pre-defined spectrum mask. The performance analysis and evaluation results show that, for a practical mobile communication systems, the application of pulse shaping is a simple and effective means to achieve a lower out-of-band leakage for OFDM systems at virtually no costs. In fact, the complexity increase amounts to 1-2% compared to CP-OFDM only. In addition, the system's robustness against both time and frequency distortions is shown to be substantially improved by a proper pulse shape design. By allowing for the flexible configuration of physical layer parameters per sub-band according to the diverse requirements of future 5G services, pulse shaped OFDM systems can efficiently facilitate asynchronous transmissions and fragmented spectrum access, rendering it beneficial for various mobile-broadband and Internet-of-Things applications.
Complete Interference Mitigation Through Receiver-Caching in Wyner's Networks
Venue: arXiv cs.IT 2016
Year: 2016

We present upper and lower bounds on the per-user multiplexing gain (MG) of Wyner's circular soft-handoff model and Wyner's circular full model with cognitive transmitters and receivers with cache memories. The bounds are tight for cache memories with prelog $μ\geq 2/3D$ in the soft-handoff model and for $μ\geq D$ in the full model, where $D$ denotes the number of possibly demanded files. In these cases the per-user MG of the two models is $1+μ/D$, the same as for non-interfering point-to-point links with caches at the receivers. Large receiver cache-memories thus allow to completely mitigate interference in these networks.
Coverage Analysis In Downlink Poisson Cellular Network With $κ$-$μ$ Shadowed Fading
Venue: arXiv cs.IT 2016
Year: 2016

The downlink coverage probability of a cellular network, when the base station locations are modelled by a Poisson point process (PPP), is known when the desired channel is Nakagami distributed with an integer shape parameter. However, for many interesting fading distributions such as Rician, Rician shadowing, $κ$-$μ$, $η$-$μ$, etc., the coverage probability is unknown. $κ$-$μ$ shadowed fading is a generic fading distribution whose special cases are many of these popular distributions known so far. In this letter, we derive the coverage probability when the desired channel experiences $κ$-$μ$ shadowed fading. Using numerical simulations, we verify our analytical expressions.
Adaptive Modulation with Impulsive Interference
Venue: arXiv cs.IT 2016
Year: 2016

In this letter, we analyze power and rate adaptation in a point-to-point link with Rayleigh fading and impulsive interference. We model the impulsive interference as a Bernoulli-Gaussian random process. Adaptation is used to maximize the average spectral efficiency by changing power and rate of the transmission subject to an average power and instantaneous probability of error constraints. Without impulsive interference, it is well known that water-filling is optimal for block fading. We provide two simple schemes that show that the conventional water-filling algorithm is not optimal in an impulsive interference channel.
Integrating User eXperience Practices into Software Development Processes: Implications of Subjectivity and Emergent Nature of UX
Venue: arXiv cs.SE 2016
Year: 2016

Many software companies face challenges in their work with User eXperience (UX) and how to integrate UX practices into existing development processes. A better understanding of these challenges can help researchers and practitioners better address them. Existing research does not analyse UX challenges in relation to other software quality characteristics including usability. In this empirical study, we have interviewed 17 practitioners from eight software development companies. Their responses are coded and analysed with thematic analysis. We report 11 challenges that practitioners face in their work with UX. Some of these challenges partly overlap with those reported in existing literature about usability or software quality characteristics. In contrast to these overlaps, the participants of our study either view many of the challenges unique to UX, or more severe than for usability or other quality characteristics. Although at a superficial level challenges with UX and other quality characteristics overlap, we differentiate these challenges at a deeper level through two main aspects of UX: subjectivity and emergent nature. In particular, we identify at least five issues that are essential to the very nature of UX, and add at least seven extra difficulties to the work of practitioners. These difficulties can explain why practitioners perceive the challenges to be more severe than for other quality characteristics. Our findings can be useful for researchers in identifying industrially relevant research areas and for practitioners to learn from empirically investigated challenges and base their improvement efforts on such knowledge. Investigating the overlaps can help finding research areas not only for enhancing practice of UX but also software quality in general. It also makes it easier for practitioners to spot, better understand as well as find mitigation strategies for UX challenges.
Asymptotic sequential Rademacher complexity of a finite function class
Venue: arXiv cs.LG 2016
Year: 2016

For a finite function class we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a $G$-heat equation. In the language of Peng's sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional $G$-normal random variable. We illustrate this result by deriving upper and lower bounds for the asymptotic sequential Rademacher complexity.
A New Manifold Distance Measure for Visual Object Categorization
Venue: arXiv cs.CV 2016
Year: 2016

Manifold distances are very effective tools for visual object recognition. However, most of the traditional manifold distances between images are based on the pixel-level comparison and thus easily affected by image rotations and translations. In this paper, we propose a new manifold distance to model the dissimilarities between visual objects based on the Complex Wavelet Structural Similarity (CW-SSIM) index. The proposed distance is more robust to rotations and translations of images than the traditional manifold distance and the CW-SSIM index based distance. In addition, the proposed distance is combined with the $k$-medoids clustering method to derive a new clustering method for visual object categorization. Experiments on Coil-20, Coil-100 and Olivetti Face Databases show that the proposed distance measure is better for visual object categorization than both the traditional manifold distances and the CW-SSIM index based distances.
Local Distributed Verification
Venue: arXiv cs.DC 2016
Year: 2016

In the framework of distributed network computing, it is known that, for every network predicate, each network configuration that satisfies this predicate can be proved using distributed certificates which can be verified locally. However, this requires to leak information about the identities of the nodes in the certificates, which might not be applicable in a context in which privacy is desirable. Unfortunately, it is known that if one insists on certificates independent of the node identities, then not all network predicates can be proved using distributed certificates that can be verified locally. In this paper, we prove that, for every network predicate, there is a distributed protocol satisfying the following two properties: (1) for every network configuration that is legal w.r.t. the predicate, and for any attempt by an adversary to prove the illegality of that configuration using distributed certificates, there is a locally verifiable proof that the adversary is wrong, also using distributed certificates; (2) for every network configuration that is illegal w.r.t. the predicate, there is a proof of that illegality, using distributed certificates, such that no matter the way an adversary assigns its own set of distributed certificates in an attempt to prove the legality of the configuration, the actual illegality of the configuration will be locally detected. In both cases, the certificates are independent of the identities of the nodes. These results are achieved by investigating the so-called local hierarchy of complexity classes in which the certificates do not exploit the node identities. Indeed, we give a characterization of such a hierarchy, which is of its own interest
A Rate-Splitting Strategy for Max-Min Fair Multigroup Multicasting
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of transmit beamforming to multiple cochannel multicast groups. The conventional approach is to beamform a designated data stream to each group, while treating potential inter-group interference as noise at the receivers. In overloaded systems where the number of transmit antennas is insufficient to perform interference nulling, we show that inter-group interference dominates at high SNRs, leading to a saturating max-min fair performance. We propose a rather unconventional approach to cope with this issue based on the concept of Rate-Splitting (RS). In particular, part of the interference is broadcasted to all groups such that it is decoded and canceled before the designated beams are decoded. We show that the RS strategy achieves significant performance gains over the conventional multigroup multicast beamforming strategy.
A Corpus-based Toy Model for DisCoCat
Venue: arXiv cs.CL 2016
Year: 2016

The categorical compositional distributional (DisCoCat) model of meaning rigorously connects distributional semantics and pregroup grammars, and has found a variety of applications in computational linguistics. From a more abstract standpoint, the DisCoCat paradigm predicates the construction of a mapping from syntax to categorical semantics. In this work we present a concrete construction of one such mapping, from a toy model of syntax for corpora annotated with constituent structure trees, to categorical semantics taking place in a category of free R-semimodules over an involutive commutative semiring R.
Sum Degrees of Freedom of the $K$-user Interference Channel with Blind CSI
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider the problem of the interference alignment for the $K$-user SISO interference channel (IC) with blind channel state information (CSI) at transmitters. Our achievement in contrast to the traditional $K-$user interference alignment (IA) scheme has more practical notions. In this case, every receiver is equipped with one reconfigurable antenna which tries to place its desired signal in a subspace which is linearly independent of interference signals. We show that if the channel values are known to the receivers only, the sum degrees-of-freedom (DoF) of the linear blind IA (BIA) with reconfigurable antenna is $\frac{Kr}{r^2-r+K}$, where $r = \left \lceil{\frac{\sqrt{1+4K}-1}{2}} \right \rceil$. The result indicates that the optimum sum DoF for the $K-$user IC is to achieve the sum DoF of $\lim_{K \rightarrow \infty} {\frac{Kr}{r^2-r+K}}=\frac{\sqrt{K}}{2}$ for an asymptotically large interference network. Thus, the DoF of the $K$-user IC using reconfigurable antenna grows sublinearly with the number of the users, whereas it grows linearly in the case where transmitters access to the CSI. In addition, we propose both achievability and converse proof so as to show that this is the sum DoF of linear BIA with the reconfigurable antenna.
Track Extraction with Hidden Reciprocal Chain Models
Venue: arXiv cs.CV 2016
Year: 2016

This paper develops Bayesian track extraction algorithms for targets modelled as hidden reciprocal chains (HRC). HRC are a class of finite-state random process models that generalise the familiar hidden Markov chains (HMC). HRC are able to model the "intention" of a target to proceed from a given origin to a destination, behaviour which cannot be properly captured by a HMC. While Bayesian estimation problems for HRC have previously been studied, this paper focusses principally on the problem of track extraction, of which the primary task is confirming target existence in a set of detections obtained from thresholding sensor measurements. Simulation examples are presented which show that the additional model information contained in a HRC improves detection performance when compared to HMC models.
Natural Language Semantics and Computability
Venue: arXiv cs.CL 2016
Year: 2016

This paper is a reflexion on the computability of natural language semantics. It does not contain a new model or new results in the formal semantics of natural language: it is rather a computational analysis of the logical models and algorithms currently used in natural language semantics, defined as the mapping of a statement to logical formulas - formulas, because a statement can be ambiguous. We argue that as long as possible world semantics is left out, one can compute the semantic representation(s) of a given statement, including aspects of lexical meaning. We also discuss the algorithmic complexity of this process.
Modeling and Analyzing Millimeter Wave Cellular Systems
Venue: arXiv cs.IT 2016
Year: 2016

We provide a comprehensive overview of mathematical models and analytical techniques for millimeter wave (mmWave) cellular systems. The two fundamental physical differences from conventional Sub-6GHz cellular systems are (i) vulnerability to blocking, and (ii) the need for significant directionality at the transmitter and/or receiver, which is achieved through the use of large antenna arrays of small individual elements. We overview and compare models for both of these factors, and present a baseline analytical approach based on stochastic geometry that allows the computation of the statistical distributions of the downlink signal-to-interference-plus-noise ratio (SINR) and also the per link data rate, which depends on the SINR as well as the average load. There are many implications of the models and analysis: (a) mmWave systems are significantly more noise-limited than at Sub-6GHz for most parameter configurations; (b) initial access is much more difficult in mmWave; (c) self-backhauling is more viable than in Sub-6GHz systems which makes ultra-dense deployments more viable, but this leads to increasingly interference-limited behavior; and (d) in sharp contrast to Sub-6GHz systems cellular operators can mutually benefit by sharing their spectrum licenses despite the uncontrolled interference that results from doing so. We conclude by outlining several important extensions of the baseline model, many of which are promising avenues for future research.
Variational Inference with Agent-Based Models
Venue: arXiv cs.MA 2016
Year: 2016

In this paper, we develop a variational method to track and make predictions about a real-world system from continuous imperfect observations about this system, using an agent-based model that describes the system dynamics. By combining the power of big data with the power of model-thinking in the stochastic process framework, we can make many valuable predictions. We show how to track the spread of an epidemic at the individual level and how to make short-term predictions about traffic congestion. This method points to a new way to bring together modelers and data miners by turning the real world into a living lab.
Online learning for Social Spammer Detection on Twitter
Venue: arXiv cs.SI 2016
Year: 2016

Social networking services like Twitter have been playing an import role in people's daily life since it supports new ways of communicating effectively and sharing information. The advantages of these social network services enable them rapidly growing. However, the rise of social network services is leading to the increase of unwanted, disruptive information from spammers, malware discriminators, and other content polluters. Negative effects of social spammers do not only annoy users, but also lead to financial loss and privacy issues. There are two main challenges of spammer detection on Twitter. Firstly, the data of social network scale with a huge volume of streaming social data. Secondly, spammers continually change their spamming strategy such as changing content patterns or trying to gain social influence, disguise themselves as far as possible. With those challenges, it is hard to directly apply traditional batch learning methods to quickly adapt newly spamming pattern in the high-volume and real-time social media data. We need an anti-spammer system to be able to adjust the learning model when getting a label feedback. Moreover, the data on social media may be unbounded. Then, the system must allow update efficiency model in both computation and memory requirements. Online learning is an ideal solution for this problem. These methods incrementally adapt the learning model with every single feedback and adjust to the changing patterns of spammers overtime. Our experiments demonstrate that an anti-spam system based on online learning approach is efficient in fast changing of spammers comparing with batch learning methods. We also attempt to find the optimal online learning method and study the effectiveness of various feature sets on these online learning methods.