OpenRaiser/Intern-Atlas huggingface dataset:
Model-based Hardware Design for FPGAs using Folding Transformations based on Subcircuits
Venue: arXiv cs.AR 2015
Year: 2015

We present a tool flow and results for a model-based hardware design for FPGAs from Simulink descriptions which nicely integrates into existing environments. While current commercial tools do not exploit some high-level optimizations, we investigate the promising approach of using reusable subcircuits for folding transformations to control embedded multiplier usage and to optimize logic block usage. We show that resource improvements of up to 70% compared to the original model are possible, but it is also shown that subcircuit selection is a critical task. While our tool flow provides good results already, the investigation and optimization of subcircuit selection is clearly identified as an additional keypoint to extend high-level control on low-level FPGA mapping properties.
On Practical SMT-Based Type Error Localization
Venue: arXiv cs.PL 2015
Year: 2015

Compilers for statically typed functional programming languages are notorious for generating confusing type error messages. When the compiler detects a type error, it typically reports the program location where the type checking failed as the source of the error. Since other error sources are not even considered, the actual root cause is often missed. A more adequate approach is to consider all possible error sources and report the most useful one subject to some usefulness criterion. In our previous work, we showed that this approach can be formulated as an optimization problem related to satisfiability modulo theories (SMT). This formulation cleanly separates the heuristic nature of usefulness criteria from the underlying search problem. Unfortunately, algorithms that search for an optimal error source cannot directly use principal types which are crucial for dealing with the exponential-time complexity of the decision problem of polymorphic type checking. In this paper, we present a new algorithm that efficiently finds an optimal error source in a given ill-typed program. Our algorithm uses an improved SMT encoding to cope with the high complexity of polymorphic typing by iteratively expanding the typing constraints from which principal types are derived. The algorithm preserves the clean separation between the heuristics and the actual search. We have implemented our algorithm for OCaml. In our experimental evaluation, we found that the algorithm reduces the running times for optimal type error localization from minutes to seconds and scales better than previous localization algorithms.
Shopper Analytics: a customer activity recognition system using a distributed RGB-D camera network
Venue: arXiv cs.CV 2015
Year: 2015

The aim of this paper is to present an integrated system consisted of a RGB-D camera and a software able to monitor shoppers in intelligent retail environments. We propose an innovative low cost smart system that can understand the shoppers' behavior and, in particular, their interactions with the products in the shelves, with the aim to develop an automatic RGB-D technique for video analysis. The system of cameras detects the presence of people and univocally identifies them. Through the depth frames, the system detects the interactions of the shoppers with the products on the shelf and determines if a product is picked up or if the product is taken and then put back and finally, if there is not contact with the products. The system is low cost and easy to install, and experimental results demonstrated that its performances are satisfactory also in real environments.
A Simple Algorithm for Coloring m-Clique Holes
Venue: arXiv cs.DM 2015
Year: 2015

An m-clique hole is a sequence $ϕ=(Φ_1,Φ_2,\dots,Φ_m)$ of $m$ distinct cliques such that $|Φ_i| \leq m$ for all $i=1,2,\ldots,m$, and whose clique graph is a hole on $m$ vertices. That is, $ϕ$ is an m-clique hole if for all $i\neq j$, $i,j=1,2,\ldots,m$, $Φ_i \cap Φ_{j} \neq \emptyset$ if and only if $(j-1)~\mbox{mod}~m = (j+1)~\mbox{mod}~m = i~\mbox{mod}~m$. This paper derives a sufficient and necessary condition on m-colorability of m-clique holes, and proposes a coloring algorithm that colors m-clique holes with exactly m colors.
Proposal of ROS-compliant FPGA Component for Low-Power Robotic Systems
Venue: arXiv cs.AR 2015
Year: 2015

In recent years, robots are required to be autonomous and their robotic software are sophisticated. Robots have a problem of insufficient performance, since it cannot equip with a high-performance microprocessor due to battery-power operation. On the other hand, FPGA devices can accelerate specific functions in a robot system without increasing power consumption by implementing customized circuits. But it is difficult to introduce FPGA devices into a robot due to large development cost of an FPGA circuit compared to software. Therefore, in this study, we propose an FPGA component technology for an easy integration of an FPGA into robots, which is compliant with ROS (Robot Operating System). As a case study, we designed ROS-compliant FPGA component of image labeling using Xilinx Zynq platform. The developed ROS-component FPGA component performs 1.7 times faster compared to the ordinary ROS software component.
On homomorphism of oriented graphs with respect to push operation
Venue: arXiv cs.DM 2015
Year: 2015

An oriented graph is a directed graph without any cycle of length at most 2. To push a vertex of a directed graph is to reverse the orientation of the arcs incident to that vertex. Klostermeyer and MacGillivray defined push graphs which are equivalence class of oriented graphs with respect to vertex pushing operation. They studied the homomorphism of the equivalence classes of oriented graphs with respect to push operation. In this article, we further study the same topic and answer some of the questions asked in the above mentioned work. The anti-twinned graph of an oriented graph is obtained by adding and pushing a copy of each of its vertices. In particular, we show that two oriented graphs are in a push relation if and only if they have isomorphic anti-twinned graphs. Moreover, we study oriented homomorphisms of outerplanar graphs with girth at least five, planar graphs and planar graphs with girth at least eight with respect to the push operation.
On chromatic number of colored mixed graphs
Venue: arXiv cs.DM 2015
Year: 2015

An $(m,n)$-colored mixed graph $G$ is a graph with its arcs having one of the $m$ different colors and edges having one of the $n$ different colors. A homomorphism $f$ of an $(m,n)$-colored mixed graph $G$ to an $(m,n)$-colored mixed graph $H$ is a vertex mapping such that if $uv$ is an arc (edge) of color $c$ in $G$, then $f(u)f(v)$ is an arc (edge) of color $c$ in $H$. The \textit{$(m,n)$-colored mixed chromatic number} $χ_{(m,n)}(G)$ of an $(m,n)$-colored mixed graph $G$ is the order (number of vertices) of the smallest homomorphic image of $G$. This notion was introduced by Nešetřil and Raspaud (2000, J. Combin. Theory, Ser. B 80, 147--155). They showed that $χ_{(m,n)}(G) \leq k(2m+n)^{k-1}$ where $G$ is a $k$-acyclic colorable graph. We proved the tightness of this bound. We also showed that the acyclic chromatic number of a graph is bounded by $k^2 + k^{2 + \lceil log_{(2m+n)} log_{(2m+n)} k \rceil}$ if its $(m,n)$-colored mixed chromatic number is at most $k$. Furthermore, using probabilistic method, we showed that for graphs with maximum degree $Δ$ its $(m,n)$-colored mixed chromatic number is at most $2(Δ-1)^{2m+n} (2m+n)^{Δ-1}$. In particular, the last result directly improves the upper bound $2Δ^2 2^Δ$ of oriented chromatic number of graphs with maximum degree $Δ$, obtained by Kostochka, Sopena and Zhu (1997, J. Graph Theory 24, 331--340) to $2(Δ-1)^2 2^{Δ-1}$. We also show that there exists a graph with maximum degree $Δ$ and $(m,n)$-colored mixed chromatic number at least $(2m+n)^{Δ/ 2}$.
On the Privacy Properties of Variants on the Sparse Vector Technique
Venue: arXiv cs.DB 2015
Year: 2015

The sparse vector technique is a powerful differentially private primitive that allows an analyst to check whether queries in a stream are greater or lesser than a threshold. This technique has a unique property -- the algorithm works by adding noise with a finite variance to the queries and the threshold, and guarantees privacy that only degrades with (a) the maximum sensitivity of any one query in stream, and (b) the number of positive answers output by the algorithm. Recent work has developed variants of this algorithm, which we call {\em generalized private threshold testing}, and are claimed to have privacy guarantees that do not depend on the number of positive or negative answers output by the algorithm. These algorithms result in a significant improvement in utility over the sparse vector technique for a given privacy budget, and have found applications in frequent itemset mining, feature selection in machine learning and generating synthetic data. In this paper we critically analyze the privacy properties of generalized private threshold testing. We show that generalized private threshold testing does not satisfy ε-differential privacy for any finite ε. We identify a subtle error in the privacy analysis of this technique in prior work. Moreover, we show an adversary can use generalized private threshold testing to recover counts from the datasets (especially small counts) exactly with high accuracy, and thus can result in individuals being reidentified. We demonstrate our attacks empirically on real datasets.
Lifetime Maximization of Wireless Sensor Networks with a Mobile Source Node
Venue: arXiv cs.NI 2015
Year: 2015

We study the problem of routing in sensor networks where the goal is to maximize the network's lifetime. Previous work has considered this problem for fixed-topology networks. Here, we add mobility to the source node, which requires a new definition of the network lifetime. In particular, we redefine lifetime to be the time until the source node depletes its energy. When the mobile node's trajectory is unknown in advance, we formulate three versions of an optimal control problem aiming at this lifetime maximization. We show that in all cases, the solution can be reduced to a sequence of Non- Linear Programming (NLP) problems solved on line as the source node trajectory evolves.
Colored Bin Packing
Venue: arXiv cs.DS 2015
Year: 2015

We study the Colored Bin Packing Problem: we are given a set of items where each item has a weight and color. We must pack the items in bins of uniform capacity such that no two items of the same color may be adjacent within in a bin. The goal is to perform this packing using the fewest number of bins. We consider a version of the problem where reordering is allowed. We first consider the zero-weight and unit weight versions of this problem, i.e. where the items have weight zero and one, respectively. We present linear time optimal algorithms for both versions.
Mixed Gaussian-Impulse Noise Removal from Highly Corrupted Images via Adaptive Local and Nonlocal Statistical Priors
Venue: arXiv cs.CV 2015
Year: 2015

The motivation of this paper is to introduce a novel framework for the restoration of images corrupted by mixed Gaussian-impulse noise. To this aim, first, an adaptive curvelet thresholding criterion is proposed which tries to adaptively remove the perturbations appeared during denoising process. Then, a new statistical regularization term, called joint adaptive statistical prior (JASP), is established which enforces both the local and nonlocal statistical consistencies, simultaneously, in a unified manner. Furthermore, a novel technique for mixed Gaussian plus impulse noise removal using JASP in a variational scheme is developed--we refer to it as De-JASP. To efficiently solve the above variational scheme, an efficient alternating minimization algorithm based on split Bregman iterative framework is developed. Extensive experimental results manifest the effectiveness of the proposed method comparing with the current state-of-the-art methods in mixed Gaussian-impulse noise removal.
Bounds on the Capacity of ASK Molecular Communication Channels with ISI
Venue: arXiv cs.IT 2015
Year: 2015

There are now several works on the use of the additive inverse Gaussian noise (AIGN) model for the random transit time in molecular communication~(MC) channels. The randomness invariably causes inter-symbol interference (ISI) in MC, an issue largely ignored or simplified. In this paper we derive an upper bound and two lower bounds for MC based on amplitude shift keying (ASK) in presence of ISI. The Blahut-Arimoto algorithm~(BAA) is modified to find the input distribution of transmitted symbols to maximize the lower bounds. Our results show that over wide parameter values the bounds are close.
An Event Network for Exploring Open Information
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, an event network is presented for exploring open information, where linguistic units about an event are organized for analysing. The process is divided into three steps: document event detection, event network construction and event network analysis. First, by implementing event detection or tracking, documents are retrospectively (or on-line) organized into document events. Secondly, for each of the document event, linguistic units are extracted and combined into event networks. Thirdly, various analytic methods are proposed for event network analysis. In our application methodologies are presented for exploring open information.
The Average Sensitivity of Bounded-Depth Formulas
Venue: arXiv cs.CC 2015
Year: 2015

We show that unbounded fan-in boolean formulas of depth $d+1$ and size $s$ have average sensitivity $O(\frac{1}{d}\log s)^d$. In particular, this gives a tight $2^{Ω(d(n^{1/d}-1))}$ lower bound on the size of depth $d+1$ formulas computing the \textsc{parity} function. These results strengthen the corresponding $2^{Ω(n^{1/d})}$ and $O(\log s)^d$ bounds for circuits due to Håstad (1986) and Boppana (1997). Our proof technique studies a random process where the Switching Lemma is applied to formulas in an efficient manner.
A survey on unmanned aerial vehicle collision avoidance systems
Venue: arXiv cs.SY 2015
Year: 2015

Collision avoidance is a key factor in enabling the integration of unmanned aerial vehicle into real life use, whether it is in military or civil application. For a long time there have been a large number of works to address this problem; therefore a comparative summary of them would be desirable. This paper presents a survey on the major collision avoidance systems developed in up to date publications. Each collision avoidance system contains two main parts: sensing and detection, and collision avoidance. Based on their characteristics each part is divided into different categories; and those categories are explained, compared and discussed about advantages and disadvantages in this paper.
Parameter Sensitivity Analysis of the Energy/Frequency Convexity Rule for Nanometer-scale Application Processors
Venue: arXiv cs.DC 2015
Year: 2015

Both theoretical and experimental evidence are presented in this work in order to validate the existence of an Energy/Frequency Convexity Rule, which relates energy consumption and microprocessor frequency for nanometer-scale microprocessors. Data gathered during several month-long experimental acquisition campaigns, supported by several independent publications, suggest that energy consumed is indeed depending on the microprocessor's clock frequency, and, more interestingly, the curve exhibits a clear minimum over the processor's frequency range. An analytical model for this behavior is presented and motivated, which fits well with the experimental data. A parameter sensitivity analysis shows how parameters affect the energy minimum in the clock frequency space. The conditions are discussed under which this convexity rule can be exploited, and when other methods are more effective, with the aim of improving the computer system's energy management efficiency. We show that the power requirements of the computer system, besides the microprocessor, and the overhead affect the location of the energy minimum the most. The sensitivity analysis of the Energy/Frequency Convexity Rule puts forward a number of simple guidelines especially for by low-power systems, such as battery-powered and embedded systems, and less likely by high-performance computer systems.
Parallel Approximate Steady-state Analysis of Large Probabilistic Boolean Networks (Technical Report)
Venue: arXiv cs.DC 2015
Year: 2015

Probabilistic Boolean networks (PBNs) is a widely used computational framework for modelling biological systems. The steady-state dynamics of PBNs is of special interest in the analysis of biological systems. However, obtaining the steady-state distributions for such systems poses a significant challenge due to the state space explosion problem which often arises in the case of large PBNs. The only viable way is to use statistical methods. We have considered the two-state Markov chain approach and the Skart method for the analysis of large PBNs in our previous work. However, the sample size required in both methods is often huge in the case of large PBNs and generating them is expensive in terms of computation time. Parallelising the sample generation is an ideal way to solve this issue. In this paper, we consider combining the German & Rubin method with either the two-state Markov chain approach or the Skart method for parallelisation. The first method can be used to run multiple independent Markov chains in parallel and to control their convergence to the steady-state while the other two methods can be used to determine the sample size required for computing the steady-state probability of states of interest. Experimental results show that our proposed combinations can reduce time cost of computing stead-state probabilities of large PBNs significantly.
A Multilayer Approach to Multiplexity and Link Prediction in Online Geo-Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

Online social systems are multiplex in nature as multiple links may exist between the same two users across different social networks. In this work, we introduce a framework for studying links and interactions between users beyond the individual social network. Exploring the cross-section of two popular online platforms - Twitter and location-based social network Foursquare - we represent the two together as a composite multilayer online social network. Through this paradigm we study the interactions of pairs of users differentiating between those with links on one or both networks. We find that users with multiplex links, who are connected on both networks, interact more and have greater neighbourhood overlap on both platforms, in comparison with pairs who are connected on just one of the social networks. In particular, the most frequented locations of users are considerably closer, and similarity is considerably greater among multiplex links. We present a number of structural and interaction features, such as the multilayer Adamic/Adar coefficient, which are based on the extension of the concept of the node neighbourhood beyond the single network. Our evaluation, which aims to shed light on the implications of multiplexity for the link generation process, shows that multilayer features, constructed from properties across social networks, perform better than their single network counterparts in predicting links across networks. We propose that combining information from multiple networks in a multilayer configuration can provide new insights into user interactions on online social networks, and can significantly improve link prediction overall with valuable applications to social bootstrapping and friend recommendations.
Characterizing Phishing Threats with Natural Language Processing
Venue: arXiv cs.CR 2015
Year: 2015

Spear phishing is a widespread concern in the modern network security landscape, but there are few metrics that measure the extent to which reconnaissance is performed on phishing targets. Spear phishing emails closely match the expectations of the recipient, based on details of their experiences and interests, making them a popular propagation vector for harmful malware. In this work we use Natural Language Processing techniques to investigate a specific real-world phishing campaign and quantify attributes that indicate a targeted spear phishing attack. Our phishing campaign data sample comprises 596 emails - all containing a web bug and a Curriculum Vitae (CV) PDF attachment - sent to our institution by a foreign IP space. The campaign was found to exclusively target specific demographics within our institution. Performing a semantic similarity analysis between the senders' CV attachments and the recipients' LinkedIn profiles, we conclude with high statistical certainty (p $< 10^{-4}$) that the attachments contain targeted rather than randomly selected material. Latent Semantic Analysis further demonstrates that individuals who were a primary focus of the campaign received CVs that are highly topically clustered. These findings differentiate this campaign from one that leverages random spam.
Overlapping Coalition Formation Games for Emerging Communication Networks
Venue: arXiv cs.GT 2015
Year: 2015

Modern cellular networks are witnessing an unprecedented evolution from classical, centralized and homogenous architectures into a mix of various technologies, in which the network devices are densely and randomly deployed in a decentralized and heterogenous architecture. This shift in network architecture requires network devices to become more autonomous and, potentially, cooperate with one another. Such cooperation can, for example, take place between interfering small access points that seek to coordinate their radio resource allocation, nearby single-antenna users that can cooperatively perform virtual MIMO communications, or even unlicensed users that wish to cooperatively sense the spectrum of the licensed users. Such cooperative mechanisms involve the simultaneous sharing and distribution of resources among a number of overlapping cooperative groups or coalitions. In this paper, a novel mathematical framework from cooperative games, dubbed \emph{overlapping coalition formation games} (OCF games), is introduced to model and solve such cooperative scenarios. First, the concepts of OCF games are presented, and then, several algorithmic aspects are studied for two main classes of OCF games. Subsequently, two example applications, namely, interference management and cooperative spectrum sensing, are discussed in detail to show how the proposed models and algorithms can be used in the future scenarios of wireless systems. Finally, we conclude by providing an overview on future directions and applications of OCF games.