OpenRaiser/Intern-Atlas huggingface dataset:
Obtaining a Proportional Allocation by Deleting Items
Venue: arXiv cs.MA 2017
Year: 2017

We consider the following control problem on fair allocation of indivisible goods. Given a set $I$ of items and a set of agents, each having strict linear preference over the items, we ask for a minimum subset of the items whose deletion guarantees the existence of a proportional allocation in the remaining instance; we call this problem Proportionality by Item Deletion (PID). Our main result is a polynomial-time algorithm that solves PID for three agents. By contrast, we prove that PID is computationally intractable when the number of agents is unbounded, even if the number $k$ of item deletions allowed is small, since the problem turns out to be W[3]-hard with respect to the parameter $k$. Additionally, we provide some tight lower and upper bounds on the complexity of PID when regarded as a function of $|I|$ and $k$.
EvaluationNet: Can Human Skill be Evaluated by Deep Networks?
Venue: arXiv cs.CV 2017
Year: 2017

With the recent substantial growth of media such as YouTube, a considerable number of instructional videos covering a wide variety of tasks are available online. Therefore, online instructional videos have become a rich resource for humans to learn everyday skills. In order to improve the effectiveness of the learning with instructional video, observation and evaluation of the activity are required. However, it is difficult to observe and evaluate every activity steps by expert. In this study, a novel deep learning framework which targets human activity evaluation for learning from instructional video has been proposed. In order to deal with the inherent variability of activities, we propose to model activity as a structured process. First, action units are encoded from dense trajectories with LSTM network. The variable-length action unit features are then evaluated by a Siamese LSTM network. By the comparative experiments on public dataset, the effectiveness of the proposed method has been demonstrated.
What to Fix? Distinguishing between design and non-design rules in automated tools
Venue: arXiv cs.SE 2017
Year: 2017

Technical debt---design shortcuts taken to optimize for delivery speed---is a critical part of long-term software costs. Consequently, automatically detecting technical debt is a high priority for software practitioners. Software quality tool vendors have responded to this need by positioning their tools to detect and manage technical debt. While these tools bundle a number of rules, it is hard for users to understand which rules identify design issues, as opposed to syntactic quality. This is important, since previous studies have revealed the most significant technical debt is related to design issues. Other research has focused on comparing these tools on open source projects, but these comparisons have not looked at whether the rules were relevant to design. We conducted an empirical study using a structured categorization approach, and manually classify 466 software quality rules from three industry tools---CAST, SonarQube, and NDepend. We found that most of these rules were easily labeled as either not design (55%) or design (19%). The remainder (26%) resulted in disagreements among the labelers. Our results are a first step in formalizing a definition of a design rule, in order to support automatic detection.
Extreme-Scale De Novo Genome Assembly
Venue: arXiv cs.DC 2017
Year: 2017

De novo whole genome assembly reconstructs genomic sequence from short, overlapping, and potentially erroneous DNA segments and is one of the most important computations in modern genomics. This work presents HipMER, a high-quality end-to-end de novo assembler designed for extreme scale analysis, via efficient parallelization of the Meraculous code. Genome assembly software has many components, each of which stresses different components of a computer system. This chapter explains the computational challenges involved in each step of the HipMer pipeline, the key distributed data structures, and communication costs in detail. We present performance results of assembling the human genome and the large hexaploid wheat genome on large supercomputers up to tens of thousands of cores.
Lights, Camera, Action! Exploring Effects of Visual Distractions on Completion of Security Tasks
Venue: arXiv cs.HC 2017
Year: 2017

Human errors in performing security-critical tasks are typically blamed on the complexity of those tasks. However, such errors can also occur because of (possibly unexpected) sensory distractions. A sensory distraction that produces negative effects can be abused by the adversary that controls the environment. Meanwhile, a distraction with positive effects can be artificially introduced to improve user performance. The goal of this work is to explore the effects of visual stimuli on the performance of security-critical tasks. To this end, we experimented with a large number of subjects who were exposed to a range of unexpected visual stimuli while attempting to perform Bluetooth Pairing. Our results clearly demonstrate substantially increased task completion times and markedly lower task success rates. These negative effects are noteworthy, especially, when contrasted with prior results on audio distractions which had positive effects on performance of similar tasks. Experiments were conducted in a novel (fully automated and completely unattended) experimental environment. This yielded more uniform experiments, better scalability and significantly lower financial and logistical burdens. We discuss this experience, including benefits and limitations of the unattended automated experiment paradigm.
Constraint Solving for Finite Model Finding in SMT Solvers
Venue: arXiv cs.LO 2017
Year: 2017

SMT solvers have been used successfully as reasoning engines for automated verification and other applications based on automated reasoning. Current techniques for dealing with quantified formulas in SMT are generally incomplete, forcing SMT solvers to report "unknown" when they fail to prove the unsatisfiability of a formula with quantifiers. This inability to return counter-models limits their usefulness in applications that produce queries involving quantified formulas. In this paper, we reduce these limitations by integrating finite model finding techniques based on constraint solving into the architecture used by modern SMT solvers. This approach is made possible by a novel solver for cardinality constraints, as well as techniques for on-demand instantiation of quantified formulas. Experiments show that our approach is competitive with the state of the art in SMT, and orthogonal to approaches in automated theorem proving.
Asymptotic Outage Analysis of HARQ-IR over Time-Correlated Nakagami-$m$ Fading Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, outage performance of hybrid automatic repeat request with incremental redundancy (HARQ-IR) is analyzed. Unlike prior analyses, time-correlated Nakagami-$m$ fading channel is considered. The outage analysis thus involves the probability distribution analysis of a product of multiple correlated shifted Gamma random variables and is more challenging than prior analyses. Based on the finding of the conditional independence of the received signal-to-noise ratios (SNRs), the outage probability is exactly derived by using conditional Mellin transform. Specifically, the outage probability of HARQ-IR under time-correlated Nakagami-$m$ fading channels can be written as a weighted sum of outage probabilities of HARQ-IR over independent Nakagami fading channels, where the weightings are determined by a negative multinomial distribution. This result enables not only an efficient truncation approximation of the outage probability with uniform convergence but also asymptotic outage analysis to further extract clear insights which have never been discovered for HARQ-IR even under fast fading channels. The asymptotic outage probability is then derived in a simple form which clearly quantifies the impacts of transmit powers, channel time correlation and information transmission rate. It is proved that the asymptotic outage probability is an inverse power function of the product of transmission powers in all HARQ rounds, an increasing function of the channel time correlation coefficients, and a monotonically increasing and convex function of information transmission rate. The simple expression of the asymptotic result enables optimal power allocation and optimal rate selection of HARQ-IR with low complexity. Finally, numerical results are provided to verify our analytical results and justify the application of the asymptotic result for optimal system design.
Analysis of Full-Duplex Downlink Using Diversity Gain
Venue: arXiv cs.NI 2017
Year: 2017

The paper carries out performance analysis of a multiuser full-duplex (FD) communication system. Multiple FD UEs share the same spectrum resources, simultaneously, at both the uplink and downlink. This results in co-channel interference (CCI) at the downlink of a UE from uplink signals of other UEs. This work proposes the use of diversity gain at the receiver to mitigate the effects of the CCI. For this an architecture for the FD eNB and FD UE is proposed and corresponding downlink operation is described. Finally, the performance of the system is studied in terms of downlink capacity of a UE. It is shown that through the deployment of sufficient number of transmit and receive antennas at the eNB and UEs, respectively, significant improvement in performance can be achieved in the presence of CCI.
Shape and Positional Geometry of Multi-Object Configurations
Venue: arXiv cs.CV 2017
Year: 2017

In previous work, we introduced a method for modeling a configuration of objects in 2D and 3D images using a mathematical "medial/skeletal linking structure." In this paper, we show how these structures allow us to capture positional properties of a multi-object configuration in addition to the shape properties of the individual objects. In particular, we introduce numerical invariants for positional properties which measure the closeness of neighboring objects, including identifying the parts of the objects which are close, and the "relative significance" of objects compared with the other objects in the configuration. Using these numerical measures, we introduce a hierarchical ordering and relations between the individual objects, and quantitative criteria for identifying subconfigurations. In addition, the invariants provide a "proximity matrix" which yields a unique set of weightings measuring overall proximity of objects in the configuration. Furthermore, we show that these invariants, which are volumetrically defined and involve external regions, may be computed via integral formulas in terms of "skeletal linking integrals" defined on the internal skeletal structures of the objects.
Static Exploration of Taint-Style Vulnerabilities Found by Fuzzing
Venue: arXiv cs.CR 2017
Year: 2017

Taint-style vulnerabilities comprise a majority of fuzzer discovered program faults. These vulnerabilities usually manifest as memory access violations caused by tainted program input. Although fuzzers have helped uncover a majority of taint-style vulnerabilities in software to date, they are limited by (i) extent of test coverage; and (ii) the availability of fuzzable test cases. Therefore, fuzzing alone cannot provide a high assurance that all taint-style vulnerabilities have been uncovered. In this paper, we use static template matching to find recurrences of fuzzer-discovered vulnerabilities. To compensate for the inherent incompleteness of template matching, we implement a simple yet effective match-ranking algorithm that uses test coverage data to focus attention on those matches that comprise untested code. We prototype our approach using the Clang/LLVM compiler toolchain and use it in conjunction with afl-fuzz, a modern coverage-guided fuzzer. Using a case study carried out on the Open vSwitch codebase, we show that our prototype uncovers corner cases in modules that lack a fuzzable test harness. Our work demonstrates that static analysis can effectively complement fuzz testing, and is a useful addition to the security assessment tool-set. Furthermore, our techniques hold promise for increasing the effectiveness of program analysis and testing, and serve as a building block for a hybrid vulnerability discovery framework.
On the Design and Invariants of a Ruled Surface
Venue: arXiv cs.GR 2017
Year: 2017

This paper deals with a kind of design of a ruled surface. It combines concepts from the fields of computer aided geometric design and kinematics. A dual unit spherical Bézier-like curve on the dual unit sphere (DUS) is obtained with respect the control points by a new method. So, with the aid of Study [1] transference principle, a dual unit spherical Bézier-like curve corresponds to a ruled surface. Furthermore, closed ruled surfaces are determined via control points and integral invariants of these surfaces are investigated. The results are illustrated by examples.
A new method of verification of security protocols
Venue: arXiv cs.LO 2017
Year: 2017

In the paper we introduce a process model of security protocols, where processes are graphs with edges labelled by actions, and present a new method of specification and verification of security protocols based on this model.
Data Analysis in Multimedia Quality Assessment: Revisiting the Statistical Tests
Venue: arXiv cs.MM 2017
Year: 2017

Assessment of multimedia quality relies heavily on subjective assessment, and is typically done by human subjects in the form of preferences or continuous ratings. Such data is crucial for analysis of different multimedia processing algorithms as well as validation of objective (computational) methods for the said purpose. To that end, statistical testing provides a theoretical framework towards drawing meaningful inferences, and making well grounded conclusions and recommendations. While parametric tests (such as t test, ANOVA, and error estimates like confidence intervals) are popular and widely used in the community, there appears to be a certain degree of confusion in the application of such tests. Specifically, the assumption of normality and homogeneity of variance is often not well understood. Therefore, the main goal of this paper is to revisit them from a theoretical perspective and in the process provide useful insights into their practical implications. Experimental results on both simulated and real data are presented to support the arguments made. A software implementing the said recommendations is also made publicly available, in order to achieve the goal of reproducible research.
Modeling and Design of Millimeter-Wave Networks for Highway Vehicular Communication
Venue: arXiv cs.IT 2017
Year: 2017

Connected and autonomous vehicles will play a pivotal role in future Intelligent Transportation Systems (ITSs) and smart cities, in general. High-speed and low-latency wireless communication links will allow municipalities to warn vehicles against safety hazards, as well as support cloud-driving solutions to drastically reduce traffic jams and air pollution. To achieve these goals, vehicles need to be equipped with a wide range of sensors generating and exchanging high rate data streams. Recently, millimeter wave (mmWave) techniques have been introduced as a means of fulfilling such high data rate requirements. In this paper, we model a highway communication network and characterize its fundamental link budget metrics. In particular, we specifically consider a network where vehicles are served by mmWave Base Stations (BSs) deployed alongside the road. To evaluate our highway network, we develop a new theoretical model that accounts for a typical scenario where heavy vehicles (such as buses and lorries) in slow lanes obstruct Line-of-Sight (LOS) paths of vehicles in fast lanes and, hence, act as blockages. Using tools from stochastic geometry, we derive approximations for the Signal-to-Interference-plus-Noise Ratio (SINR) outage probability, as well as the probability that a user achieves a target communication rate (rate coverage probability). Our analysis provides new design insights for mmWave highway communication networks. In considered highway scenarios, we show that reducing the horizontal beamwidth from $90^\circ$ to $30^\circ$ determines a minimal reduction in the SINR outage probability (namely, $4 \cdot 10^{-2}$ at maximum). Also, unlike bi-dimensional mmWave cellular networks, for small BS densities (namely, one BS every $500$ m) it is still possible to achieve an SINR outage probability smaller than $0.2$.
A Composition Theorem for Randomized Query Complexity
Venue: arXiv cs.CC 2017
Year: 2017

Let the randomized query complexity of a relation for error probability $ε$ be denoted by $R_ε(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $R_{1/3}(f\circ g^n) = Ω(R_{4/9}(f)\cdot R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. We also show that $R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=Ω(\log n \cdot R_{4/9}(f) \cdot R_{1/3}(g))$, where $g^\oplus_{O(\log n)}$ is the function obtained by composing the xor function on $O(\log n)$ bits and $g^t$.
Semantic Specialisation of Distributional Word Vector Spaces using Monolingual and Cross-Lingual Constraints
Venue: arXiv cs.CL 2017
Year: 2017

We present Attract-Repel, an algorithm for improving the semantic quality of word vectors by injecting constraints extracted from lexical resources. Attract-Repel facilitates the use of constraints from mono- and cross-lingual resources, yielding semantically specialised cross-lingual vector spaces. Our evaluation shows that the method can make use of existing cross-lingual lexicons to construct high-quality vector spaces for a plethora of different languages, facilitating semantic transfer from high- to lower-resource ones. The effectiveness of our approach is demonstrated with state-of-the-art results on semantic similarity datasets in six languages. We next show that Attract-Repel-specialised vectors boost performance in the downstream task of dialogue state tracking (DST) across multiple languages. Finally, we show that cross-lingual vector spaces produced by our algorithm facilitate the training of multilingual DST models, which brings further performance improvements.
Tensor Contraction Layers for Parsimonious Deep Nets
Venue: arXiv cs.LG 2017
Year: 2017

Tensors offer a natural representation for many kinds of data frequently encountered in machine learning. Images, for example, are naturally represented as third order tensors, where the modes correspond to height, width, and channels. Tensor methods are noted for their ability to discover multi-dimensional dependencies, and tensor decompositions in particular, have been used to produce compact low-rank approximations of data. In this paper, we explore the use of tensor contractions as neural network layers and investigate several ways to apply them to activation tensors. Specifically, we propose the Tensor Contraction Layer (TCL), the first attempt to incorporate tensor contractions as end-to-end trainable neural network layers. Applied to existing networks, TCLs reduce the dimensionality of the activation tensors and thus the number of model parameters. We evaluate the TCL on the task of image recognition, augmenting two popular networks (AlexNet, VGG). The resulting models are trainable end-to-end. Applying the TCL to the task of image recognition, using the CIFAR100 and ImageNet datasets, we evaluate the effect of parameter reduction via tensor contraction on performance. We demonstrate significant model compression without significant impact on the accuracy and, in some cases, improved performance.
A Vision System for Multi-View Face Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Multimodal biometric identification has been grown a great attention in the most interests in the security fields. In the real world there exist modern system devices that are able to detect, recognize, and classify the human identities with reliable and fast recognition rates. Unfortunately most of these systems rely on one modality, and the reliability for two or more modalities are further decreased. The variations of face images with respect to different poses are considered as one of the important challenges in face recognition systems. In this paper, we propose a multimodal biometric system that able to detect the human face images that are not only one view face image, but also multi-view face images. Each subject entered to the system adjusted their face at front of the three cameras, and then the features of the face images are extracted based on Speeded Up Robust Features (SURF) algorithm. We utilize Multi-Layer Perceptron (MLP) and combined classifiers based on both Learning Vector Quantization (LVQ), and Radial Basis Function (RBF) for classification purposes. The proposed system has been tested using SDUMLA-HMT, and CASIA datasets. Furthermore, we collected a database of multi-view face images by which we take the additive white Gaussian noise into considerations. The results indicated the reliability, robustness of the proposed system with different poses and variations including noise images.
Combinatorial Problems on $H$-graphs
Venue: arXiv cs.DM 2017
Year: 2017

Biró, Hujter, and Tuza introduced the concept of $H$-graphs (1992), intersection graphs of connected subgraphs of a subdivision of a graph $H$. They naturally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. We continue the study of these graph classes by considering coloring, clique, and isomorphism problems on $H$-graphs. We show that for any fixed $H$ containing a certain 3-node, 6-edge multigraph as a minor that the clique problem is APX-hard on $H$-graphs and the isomorphism problem is isomorphism-complete. We also provide positive results on $H$-graphs. Namely, when $H$ is a cactus the clique problem can be solved in polynomial time. Also, when a graph $G$ has a Helly $H$-representation, the clique problem can be solved in polynomial time. Finally, we observe that one can use treewidth techniques to show that both the $k$-clique and list $k$-coloring problems are FPT on $H$-graphs. These FPT results apply more generally to treewidth-bounded graph classes where treewidth is bounded by a function of the clique number.
Urban Dreams of Migrants: A Case Study of Migrant Integration in Shanghai
Venue: arXiv cs.CY 2017
Year: 2017

Unprecedented human mobility has driven the rapid urbanization around the world. In China, the fraction of population dwelling in cities increased from 17.9% to 52.6% between 1978 and 2012. Such large-scale migration poses challenges for policymakers and important questions for researchers. To investigate the process of migrant integration, we employ a one-month complete dataset of telecommunication metadata in Shanghai with 54 million users and 698 million call logs. We find systematic differences between locals and migrants in their mobile communication networks and geographical locations. For instance, migrants have more diverse contacts and move around the city with a larger radius than locals after they settle down. By distinguishing new migrants (who recently moved to Shanghai) from settled migrants (who have been in Shanghai for a while), we demonstrate the integration process of new migrants in their first three weeks. Moreover, we formulate classification problems to predict whether a person is a migrant. Our classifier is able to achieve an F1-score of 0.82 when distinguishing settled migrants from locals, but it remains challenging to identify new migrants because of class imbalance. This classification setup holds promise for identifying new migrants who will successfully integrate into locals (new migrants that misclassified as locals).