OpenRaiser/Intern-Atlas huggingface dataset:
The complexity of dominating set reconfiguration
Venue: arXiv cs.DM 2015
Year: 2015

Suppose that we are given two dominating sets $D_s$ and $D_t$ of a graph $G$ whose cardinalities are at most a given threshold $k$. Then, we are asked whether there exists a sequence of dominating sets of $G$ between $D_s$ and $D_t$ such that each dominating set in the sequence is of cardinality at most $k$ and can be obtained from the previous one by either adding or deleting exactly one vertex. This problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, trees, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence such that the number of additions and deletions is bounded by $O(n)$, where $n$ is the number of vertices in the input graph.
Modeling and Analysis of Wireless Channels via the Mixture of Gaussian Distribution
Venue: arXiv cs.IT 2015
Year: 2015

Considerable efforts have been devoted to statistical modeling and the characterization of channels in a range of statistical models for fading channels. In this paper, we consider a unified approach to model wireless channels by the mixture of Gaussian (MoG) distribution. Simulations provided have shown the new probability density function to accurately characterize multipath fading as well as composite fading channels. We utilize the well known expectation-maximization algorithm to estimate the parameters of the MoG model and further utilize the Kullback-Leibler divergence and the mean square error criteria to demonstrate that our model provides both high accuracy and low computational complexity, in comparison with existing results. Additionally, we provide closed form expressions for several performance metrics used in wireless communication systems, including the moment generating function, the raw moments, the amount of fading, the outage probability, the average channel capacity, and the probability of energy detection for cognitive radio. Numerical Analysis and Monte-Carlo simulations are presented to corroborate the analytical results and to provide detailed performance comparisons with the other models in the literature.
Anisotropic Diffusion in ITK
Venue: arXiv cs.CV 2015
Year: 2015

Anisotropic Non-Linear Diffusion is a powerful image processing technique, which allows to simultaneously remove the noise and enhance sharp features in two or three dimensional images. Anisotropic Diffusion is understood here in the sense of Weickert, meaning that diffusion tensors are anisotropic and reflect the local orientation of image features. This is in contrast with the non-linear diffusion filter of Perona and Malik, which only involves scalar diffusion coefficients, in other words isotropic diffusion tensors. In this paper, we present an anisotropic non-linear diffusion technique we implemented in ITK. This technique is based on a recent adaptive scheme making the diffusion stable and requiring limited numerical resources. (See supplementary data.)
Secrecy Transmit Beamforming for Heterogeneous Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we pioneer the study of physical-layer security in heterogeneous networks (HetNets). We investigate secure communications in a two-tier downlink HetNet, which comprises one macrocell and several femtocells. Each cell has multiple users and an eavesdropper attempts to wiretap the intended macrocell user. Firstly, we consider an orthogonal spectrum allocation strategy to eliminate co-channel interference, and propose the secrecy transmit beamforming only operating in the macrocell (STB-OM) as a partial solution for secure communication in HetNet. Next, we consider a secrecy-oriented non-orthogonal spectrum allocation strategy and propose two cooperative STBs which rely on the collaboration amongst the macrocell base station (MBS) and the adjacent femtocell base stations (FBSs). Our first cooperative STB is the STB sequentially operating in the macrocell and femtocells (STB-SMF), where the cooperative FBSs individually design their STB matrices and then feed their performance metrics to the MBS for guiding the STB in the macrocell. Aiming to improve the performance of STB-SMF, we further propose the STB jointly designed in the macrocell and femtocells (STB-JMF), where all cooperative FBSs feed channel state information to the MBS for designing the joint STB. Unlike conventional STBs conceived for broadcasting or interference channels, the three proposed STB schemes all entail relatively sophisticated optimizations due to QoS constraints of the legitimate users. In order to efficiently use these STB schemes, the original optimization problems are reformulated and convex optimization techniques, such as second-order cone programming and semidefinite programming, are invoked to obtain the optimal solutions. Numerical results demonstrate that the proposed STB schemes are highly effective in improving the secrecy rate performance of HetNet.
Collective achievement of making in cosplay culture
Venue: arXiv cs.CY 2015
Year: 2015

This paper analyzes peer-based learning and the concept of Scaffolding represented in ethnographic case studies of ten female informants aged 20-25 participating in the cosplay community. Cosplay is a female-dominated niche subculture of extreme fans and mavens, who are devoted to dressing up as characters from manga, games, and anime. Cosplayers are highly conscious of quality standards for costumes, makeup, and accessories. Cosplay events and dedicated SNSs for cosplayers are a valuable venue for exchanging information about costume making. First we frame this work as an effort to think about their learning environment using the concept of connected learning by Ito et al(2013). Then we share an overview of cosplay culture in Japan and our methodologies based on interviews and fieldwork. The interview transcripts were analyzed according to the Steps for coding and Theorization method, a qualitative data analysis technique by Otani (2008). In this study, We focus on their reciprocal learning and expanding the concept of Scaffolding.
Using Descriptive Video Services to Create a Large Data Source for Video Annotation Research
Venue: arXiv cs.CV 2015
Year: 2015

In this work, we introduce a dataset of video annotated with high quality natural language phrases describing the visual content in a given segment of time. Our dataset is based on the Descriptive Video Service (DVS) that is now encoded on many digital media products such as DVDs. DVS is an audio narration describing the visual elements and actions in a movie for the visually impaired. It is temporally aligned with the movie and mixed with the original movie soundtrack. We describe an automatic DVS segmentation and alignment method for movies, that enables us to scale up the collection of a DVS-derived dataset with minimal human intervention. Using this method, we have collected the largest DVS-derived dataset for video description of which we are aware. Our dataset currently includes over 84.6 hours of paired video/sentences from 92 DVDs and is growing.
Assessing a human mediated current awareness service
Venue: arXiv cs.DL 2015
Year: 2015

In this paper, we present an approach for analyzing the behavior of editors in the large current awareness service "NEP: New Economics Papers". We processed data from more than 38,000 issues derived from 90 different NEP reports over the past ten years. The aim of our analysis was to gain an inside to the editor behaviour when creating an issue and to look for factors that influence the success of a report. In our study we looked at the following features: average editing time, the average number of papers in an issue and the editor effort measured on presorted issues as relative search length (RSL). We found an average issue size of 12.4 documents per issue. The average editing time is rather low with 14.5 minute. We get to the point that the success of a report is mainly driven by its topic and the number of subscribers, as well as proactive action by the editor to promote the report in her community.
A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words
Venue: arXiv cs.DS 2015
Year: 2015

A quantile summary is a data structure that approximates to $\varepsilon$-relative error the order statistics of a much larger underlying dataset. In this paper we develop a randomized online quantile summary for the cash register data input model and comparison data domain model that uses $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words of memory. This improves upon the previous best upper bound of $O(\frac{1}{\varepsilon} \log^{3/2} \frac{1}{\varepsilon})$ by Agarwal et. al. (PODS 2012). Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic summary for the comparison model can outperform our randomized summary in terms of space complexity. Lastly, our summary has the nice property that $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words suffice to ensure that the success probability is $1 - e^{-\text{poly}(1/\varepsilon)}$.
Statistical modality tagging from rule-based annotations and crowdsourcing
Venue: arXiv cs.CL 2015
Year: 2015

We explore training an automatic modality tagger. Modality is the attitude that a speaker might have toward an event or state. One of the main hurdles for training a linguistic tagger is gathering training data. This is particularly problematic for training a tagger for modality because modality triggers are sparse for the overwhelming majority of sentences. We investigate an approach to automatically training a modality tagger where we first gathered sentences based on a high-recall simple rule-based modality tagger and then provided these sentences to Mechanical Turk annotators for further annotation. We used the resulting set of training data to train a precise modality tagger using a multi-class SVM that delivers good performance.
On the Number of Minimal Separators in Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We consider the largest number of minimal separators a graph on n vertices can have at most. We give a new proof that this number is in $O( ((1+\sqrt{5})/2)^n n )$. We prove that this number is in $ω( 1.4521^n )$, improving on the previous best lower bound of $Ω(3^{n/3}) \subseteq ω( 1.4422^n )$. This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.
Unified Analysis of Cooperative Spectrum Sensing over Composite and Generalized Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the performance of cooperative spectrum sensing (CSS) with multiple antenna nodes over composite and generalized fading channels. We model the probability density function (PDF) of the signal-to-noise ratio (SNR) using the mixture gamma (MG) distribution. We then derive a generalized closed-form expression for the probability of energy detection, which can be used efficiently for generalized multipath as well as composite (multipath and shadowing) fading channels. The composite effect of fading and shadowing scenarios in CSS is mitigated by applying an optimal fusion rule that minimizes the total error rate (TER), where the optimal number of nodes is derived under the Bayesian criterion, assuming erroneous feedback channels. For imperfect feedback channels, we demonstrate the existence of a TER floor as the number of antennas of the CR nodes increases. Accordingly, we derive the optimal rule for the number of antennas that minimizes the TER. Numerical and Monte-Carlo simulations are presented to corroborate the analytical results and to provide illustrative performance comparisons between different composite fading channels.
On Flattenability of Graphs
Venue: arXiv cs.CG 2015
Year: 2015

We consider a generalization of the concept of $d$-flattenability of graphs - introduced for the $l_2$ norm by Belk and Connelly - to general $l_p$ norms, with integer $P$, $1 \le p < \infty$, though many of our results work for $l_\infty$ as well. The following results are shown for graphs $G$, using notions of genericity, rigidity, and generic $d$-dimensional rigidity matroid introduced by Kitson for frameworks in general $l_p$ norms, as well as the cones of vectors of pairwise $l_p^p$ distances of a finite point configuration in $d$-dimensional, $l_p$ space: (i) $d$-flattenability of a graph $G$ is equivalent to the convexity of $d$-dimensional, inherent Cayley configurations spaces for $G$, a concept introduced by the first author; (ii) $d$-flattenability and convexity of Cayley configuration spaces over specified non-edges of a $d$-dimensional framework are not generic properties of frameworks (in arbitrary dimension); (iii) $d$-flattenability of $G$ is equivalent to all of $G$'s generic frameworks being $d$-flattenable; (iv) existence of one generic $d$-flattenable framework for $G$ is equivalent to the independence of the edges of $G$, a generic property of frameworks; (v) the rank of $G$ equals the dimension of the projection of the $d$-dimensional stratum of the $l_p^p$ distance cone. We give stronger results for specific norms for $d = 2$: we show that (vi) 2-flattenable graphs for the $l_1$-norm (and $l_\infty$-norm) are a larger class than 2-flattenable graphs for Euclidean $l_2$-norm case and finally (vii) prove further results towards characterizing 2-flattenability in the $l_1$-norm. A number of conjectures and open problems are posed.
Visualization of Clandestine Labs from Seizure Reports: Thematic Mapping and Data Mining Research Directions
Venue: arXiv cs.IR 2015
Year: 2015

The problem of spatiotemporal event visualization based on reports entails subtasks ranging from named entity recognition to relationship extraction and mapping of events. We present an approach to event extraction that is driven by data mining and visualization goals, particularly thematic mapping and trend analysis. This paper focuses on bridging the information extraction and visualization tasks and investigates topic modeling approaches. We develop a static, finite topic model and examine the potential benefits and feasibility of extending this to dynamic topic modeling with a large number of topics and continuous time. We describe an experimental test bed for event mapping that uses this end-to-end information retrieval system, and report preliminary results on a geoinformatics problem: tracking of methamphetamine lab seizure events across time and space.
What's Cookin'? Interpreting Cooking Videos using Text, Speech and Vision
Venue: arXiv cs.CL 2015
Year: 2015

We present a novel method for aligning a sequence of instructions to a video of someone carrying out a task. In particular, we focus on the cooking domain, where the instructions correspond to the recipe. Our technique relies on an HMM to align the recipe steps to the (automatically generated) speech transcript. We then refine this alignment using a state-of-the-art visual food detector, based on a deep convolutional neural network. We show that our technique outperforms simpler techniques based on keyword spotting. It also enables interesting applications, such as automatically illustrating recipes with keyframes, and searching within a video for events of interest.
Modelling the Semantic Web using a Type System
Venue: arXiv cs.LO 2015
Year: 2015

We present an approach for modeling the Semantic Web as a type system. By using a type system, we can use symbolic representation for representing linked data. Objects with only data properties and references to external resources are represented as terms in the type system. Triples are represented symbolically using type constructors as the predicates. In our type system, we allow users to add analytics that utilize machine learning or knowledge discovery to perform inductive reasoning over data. These analytics can be used by the inference engine when performing reasoning to answer a query. Furthermore, our type system defines a means to resolve semantic heterogeneity on-the-fly.
The Contemporary Understanding of User Experience in Practice
Venue: arXiv cs.HC 2015
Year: 2015

User Experience (UX) has been a buzzword in agile literature in recent years. However, often UX remains as a vague concept and it may be hard to understand the very nature of it in the context of agile software development. This paper explores the multifaceted UX literature, emphasizes the multi-dimensional nature of the concept and organizes the current state-of-the-art knowledge. As a starting point to better understand the contemporary meaning of UX assigned by practitioners, we selected four UX blogs and performed an analysis using a framework derived from the literature review. The preliminary results show that the practitioners more often focus on interaction between product and user and view UX from design perspective predominantly. While the economical perspective receives little attention in literature, it is evident in practitioners writings. Our study opens up a promising line of request of the contemporary meaning of UX in practice.
What is User Experience Really: towards a UX Conceptual Framework
Venue: arXiv cs.HC 2015
Year: 2015

For more then a decade the term User Experience (UX) has been highly debated and defined in many ways. However, often UX remains as a vague concept and it may be hard to understand the very nature of it. In this paper we aimed at providing a better understanding of this concept. We explored the multi-faceted UX literature, reviewing the current state-of- the-art knowledge and emphasizing the multi-dimensional nature of the concept. Based on the literature review we built a conceptual framework of UX using the elements that are linked to it and reported in different studies. To show the potential use of the framework, we examined the UX delivered by different phone applications on different mobile devices using the elements in the framework. Several interesting insights have been obtained in terms of how the phone applications deliver different UX. Our study opens up a promising line of investigating the contemporary meaning of UX.
Partial light field tomographic reconstruction from a fixed-camera focal stack
Venue: arXiv cs.CV 2015
Year: 2015

This paper describes a novel approach to partially reconstruct high-resolution 4D light fields from a stack of differently focused photographs taken with a fixed camera. First, a focus map is calculated from this stack using a simple approach combining gradient detection and region expansion with graph-cut. Then, this focus map is converted into a depth map thanks to the calibration of the camera. We proceed after this with the tomographic reconstruction of the epipolar images by back-projecting the focused regions of the scene only. We call it masked back-projection. The angles of back-projection are calculated from the depth map. Thanks to the high angular resolution we achieve by suitably exploiting the image content captured over a large interval of focus distances, we are able to render puzzling perspective shifts although the original photographs were taken from a single fixed camera at a fixed position.
Mechanism Design via Optimal Transport
Venue: arXiv cs.GT 2015
Year: 2015

Optimal mechanisms have been provided in quite general multi-item settings, as long as each bidder's type distribution is given explicitly by listing every type in the support along with its associated probability. In the implicit setting, e.g. when the bidders have additive valuations with independent and/or continuous values for the items, these results do not apply, and it was recently shown that exact revenue optimization is intractable, even when there is only one bidder. Even for item distributions with special structure, optimal mechanisms have been surprisingly rare and the problem is challenging even in the two-item case. In this paper, we provide a framework for designing optimal mechanisms using optimal transport theory and duality theory. We instantiate our framework to obtain conditions under which only pricing the grand bundle is optimal in multi-item settings (complementing the work of [Manelli and Vincent 2006], as well as to characterize optimal two-item mechanisms. We use our results to derive closed-form descriptions of the optimal mechanism in several two-item settings, exhibiting also a setting where a continuum of lotteries is necessary for revenue optimization but a closed-form representation of the mechanism can still be found efficiently using our framework.
Information entropy as an anthropomorphic concept
Venue: arXiv cs.IT 2015
Year: 2015

According to E.T. Jaynes and E.P. Wigner, entropy is an anthropomorphic concept in the sense that in a physical system correspond many thermodynamic systems. The physical system can be examined from many points of view each time examining different variables and calculating entropy differently. In this paper we discuss how this concept may be applied in information entropy; how Shannon's definition of entropy can fit in Jayne's and Wigner's statement. This is achieved by generalizing Shannon's notion of information entropy and this is the main contribution of the paper. Then we discuss how entropy under these considerations may be used for the comparison of password complexity and as a measure of diversity useful in the analysis of the behavior of genetic algorithms.
Towards an intelligent VNS heuristic for the k-labelled spanning forest problem
Venue: arXiv cs.OH 2015
Year: 2015

In a currently ongoing project, we investigate a new possibility for solving the k-labelled spanning forest (kLSF) problem by an intelligent Variable Neighbourhood Search (Int-VNS) metaheuristic. In the kLSF problem we are given an undirected input graph G and an integer positive value k, and the aim is to find a spanning forest of G having the minimum number of connected components and the upper bound k on the number of labels to use. The problem is related to the minimum labelling spanning tree (MLST) problem, whose goal is to get the spanning tree of the input graph with the minimum number of labels, and has several applications in the real world, where one aims to ensure connectivity by means of homogeneous connections. The Int-VNS metaheuristic that we propose for the kLSF problem is derived from the promising intelligent VNS strategy recently proposed for the MLST problem, and integrates the basic VNS for the kLSF problem with other complementary approaches from machine learning, statistics and experimental algorithmics, in order to produce high-quality performance and to completely automate the resulting strategy.