OpenRaiser/Intern-Atlas huggingface dataset:
Semantic tracking: Single-target tracking with inter-supervised convolutional networks
Venue: arXiv cs.CV 2016
Year: 2016

This article presents a semantic tracker which simultaneously tracks a single target and recognises its category. In general, it is hard to design a tracking model suitable for all object categories, e.g., a rigid tracker for a car is not suitable for a deformable gymnast. Category-based trackers usually achieve superior tracking performance for the objects of that specific category, but have difficulties being generalised. Therefore, we propose a novel unified robust tracking framework which explicitly encodes both generic features and category-based features. The tracker consists of a shared convolutional network (NetS), which feeds into two parallel networks, NetC for classification and NetT for tracking. NetS is pre-trained on ImageNet to serve as a generic feature extractor across the different object categories for NetC and NetT. NetC utilises those features within fully connected layers to classify the object category. NetT has multiple branches, corresponding to multiple categories, to distinguish the tracked object from the background. Since each branch in NetT is trained by the videos of a specific category or groups of similar categories, NetT encodes category-based features for tracking. During online tracking, NetC and NetT jointly determine the target regions with the right category and foreground labels for target estimation. To improve the robustness and precision, NetC and NetT inter-supervise each other and trigger network adaptation when their outputs are ambiguous for the same image regions (i.e., when the category label contradicts the foreground/background classification). We have compared the performance of our tracker to other state-of-the-art trackers on a large-scale tracking benchmark (100 sequences)---the obtained results demonstrate the effectiveness of our proposed tracker as it outperformed other 38 state-of-the-art tracking algorithms.
Discover Aggregates Exceptions over Hidden Web Databases
Venue: arXiv cs.DB 2016
Year: 2016

Nowadays, many web databases "hidden" behind their restrictive search interfaces (e.g., Amazon, eBay) contain rich and valuable information that is of significant interests to various third parties. Recent studies have demonstrated the possibility of estimating/tracking certain aggregate queries over dynamic hidden web databases. Nonetheless, tracking all possible aggregate query answers to report interesting findings (i.e., exceptions), while still adhering to the stringent query-count limitations enforced by many hidden web databases providers, is very challenging. In this paper, we develop a novel technique for tracking and discovering exceptions (in terms of sudden changes of aggregates) over dynamic hidden web databases. Extensive real-world experiments demonstrate the superiority of our proposed algorithms over baseline solutions.
Visualizing Linguistic Shift
Venue: arXiv cs.CL 2016
Year: 2016

Neural network based models are a very powerful tool for creating word embeddings, the objective of these models is to group similar words together. These embeddings have been used as features to improve results in various applications such as document classification, named entity recognition, etc. Neural language models are able to learn word representations which have been used to capture semantic shifts across time and geography. The objective of this paper is to first identify and then visualize how words change meaning in different text corpus. We will train a neural language model on texts from a diverse set of disciplines philosophy, religion, fiction etc. Each text will alter the embeddings of the words to represent the meaning of the word inside that text. We will present a computational technique to detect words that exhibit significant linguistic shift in meaning and usage. We then use enhanced scatterplots and storyline visualization to visualize the linguistic shift.
Approximation and parameterized algorithms for geometric independent set with shrinking
Venue: arXiv cs.DS 2016
Year: 2016

Consider the Maximum Weight Independent Set problem for rectangles: given a family of weighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlapping rectangles. The problem is notoriously hard both in the approximation and in the parameterized setting. The best known polynomial-time approximation algorithms achieve super-constant approximation ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and Har-Peled, Discrete & Comp. Geometry 2012], even though there is a $(1+ε)$-approximation running in quasi-polynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and Ene, FOCS 2016]. When parameterized by the target size of the solution, the problem is $\mathsf{W}[1]$-hard even in the unweighted setting [Marx, FOCS 2007]. To achieve tractability, we study the following shrinking model: one is allowed to shrink each input rectangle by a multiplicative factor $1-δ$ for some fixed $δ>0$, but the performance is still compared against the optimal solution for the original, non-shrunk instance. We prove that in this regime, the problem admits an EPTAS with running time $f(ε,δ)\cdot n^{\mathcal{O}(1)}$, and an FPT algorithm with running time $f(k,δ)\cdot n^{\mathcal{O}(1)}$, in the setting where a maximum-weight solution of size at most $k$ is to be computed. This improves and significantly simplifies a PTAS given earlier for this problem [Adamaszek et al., APPROX 2015], and provides the first parameterized results for the shrinking model. Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelization procedures for several variants of the problem when the input rectangles are squares.
A critical comparative analysis of five world university rankings
Venue: arXiv cs.DL 2016
Year: 2016

To provide users insight into the value and limits of world university rankings, a comparative analysis is conducted of 5 ranking systems: ARWU, Leiden, THE, QS and U-Multirank. It links these systems with one another at the level of individual institutions, and analyses the overlap in institutional coverage, geographical coverage, how indicators are calculated from raw data, the skewness of indicator distributions, and statistical correlations between indicators. Four secondary analyses are presented investigating national academic systems and selected pairs of indicators. It is argued that current systems are still one-dimensional in the sense that they provide finalized, seemingly unrelated indicator values rather than offering a data set and tools to observe patterns in multi-faceted data. By systematically comparing different systems, more insight is provided into how their institutional coverage, rating methods, the selection of indicators and their normalizations influence the ranking positions of given institutions.
On the List-Decodability of Random Self-Orthogonal Codes
Venue: arXiv cs.IT 2016
Year: 2016

In 2011, Guruswami-Håstad-Kopparty \cite{Gru} showed that the list-decodability of random linear codes is as good as that of general random codes. In the present paper, we further strengthen the result by showing that the list-decodability of random {\it Euclidean self-orthogonal} codes is as good as that of general random codes as well, i.e., achieves the classical Gilbert-Varshamov bound. Specifically, we show that, for any fixed finite field $\F_q$, error fraction $δ\in (0,1-1/q)$ satisfying $1-H_q(δ)\le \frac12$ and small $ε>0$, with high probability a random Euclidean self-orthogonal code over $\F_q$ of rate $1-H_q(δ)-ε$ is $(δ, O(1/ε))$-list-decodable. This generalizes the result of linear codes to Euclidean self-orthogonal codes. In addition, we extend the result to list decoding {\it symplectic dual-containing} codes by showing that the list-decodability of random symplectic dual-containing codes achieves the quantum Gilbert-Varshamov bound as well. This implies that list-decodability of quantum stabilizer codes can achieve the quantum Gilbert-Varshamov bound. The counting argument on self-orthogonal codes is an important ingredient to prove our result.
A randomized polynomial kernelization for Vertex Cover with a smaller parameter
Venue: arXiv cs.DS 2016
Year: 2016

In the Vertex Cover problem we are given a graph $G=(V,E)$ and an integer $k$ and have to determine whether there is a set $X\subseteq V$ of size at most $k$ such that each edge in $E$ has at least one endpoint in $X$. The problem can be easily solved in time $O^*(2^k)$, making it fixed-parameter tractable (FPT) with respect to $k$. While the fastest known algorithm takes only time $O^*(1.2738^k)$, much stronger improvements have been obtained by studying parameters that are smaller than $k$. Apart from treewidth-related results, the arguably best algorithm for Vertex Cover runs in time $O^*(2.3146^p)$, where $p=k-LP(G)$ is only the excess of the solution size $k$ over the best fractional vertex cover (Lokshtanov et al.\ TALG 2014). Since $p\leq k$ but $k$ cannot be bounded in terms of $p$ alone, this strictly increases the range of tractable instances. Recently, Garg and Philip (SODA 2016) greatly contributed to understanding the parameterized complexity of the Vertex Cover problem. They prove that $2LP(G)-MM(G)$ is a lower bound for the vertex cover size of $G$, where $MM(G)$ is the size of a largest matching of $G$, and proceed to study parameter $\ell=k-(2LP(G)-MM(G))$. They give an algorithm of running time $O^*(3^\ell)$, proving that Vertex Cover is FPT in $\ell$. It can be easily observed that $\ell\leq p$ whereas $p$ cannot be bounded in terms of $\ell$ alone. We complement the work of Garg and Philip by proving that Vertex Cover admits a randomized polynomial kernelization in terms of $\ell$, i.e., an efficient preprocessing to size polynomial in $\ell$. This improves over parameter $p=k-LP(G)$ for which this was previously known (Kratsch and Wahlström FOCS 2012).
Communications and Signals Design for Wireless Power Transmission
Venue: arXiv cs.IT 2016
Year: 2016

Radiative wireless power transfer (WPT) is a promising technology to provide cost-effective and real-time power supplies to wireless devices. Although radiative WPT shares many similar characteristics with the extensively studied wireless information transfer or communication, they also differ significantly in terms of design objectives, transmitter/receiver architectures and hardware constraints, etc. In this article, we first give an overview on the various WPT technologies, the historical development of the radiative WPT technology and the main challenges in designing contemporary radiative WPT systems. Then, we focus on discussing the new communication and signal processing techniques that can be applied to tackle these challenges. Topics discussed include energy harvester modeling, energy beamforming for WPT, channel acquisition, power region characterization in multi-user WPT, waveform design with linear and non-linear energy receiver model, safety and health issues of WPT, massive MIMO (multiple-input multiple-output) and millimeter wave (mmWave) enabled WPT, wireless charging control, and wireless power and communication systems co-design. We also point out directions that are promising for future research.
Throughput analysis in networks of WLANs
Venue: arXiv cs.NI 2016
Year: 2016

This paper proposes a simple but accurate approximation to analytically model both the inter-WLANs (Wireless Local Area Networks) interactions and the negative effect of collisions in networks of IEEE 802.11 WLANs. Inter-WLANs interactions are characterized using a continuous time Markov chain (CTMC) model where states represent the set of active WLANs at a given time. Then, the effect of collisions is considered by analyzing the local dynamics between contending WLANs at every state using the well-known IEEE 802.11 Bianchi model. Results confirm the accuracy of the presented approach.
Associative Adversarial Networks
Venue: arXiv cs.LG 2016
Year: 2016

We propose a higher-level associative memory for learning adversarial networks. Generative adversarial network (GAN) framework has a discriminator and a generator network. The generator (G) maps white noise (z) to data samples while the discriminator (D) maps data samples to a single scalar. To do so, G learns how to map from high-level representation space to data space, and D learns to do the opposite. We argue that higher-level representation spaces need not necessarily follow a uniform probability distribution. In this work, we use Restricted Boltzmann Machines (RBMs) as a higher-level associative memory and learn the probability distribution for the high-level features generated by D. The associative memory samples its underlying probability distribution and G learns how to map these samples to data space. The proposed associative adversarial networks (AANs) are generative models in the higher-levels of the learning, and use adversarial non-stochastic models D and G for learning the mapping between data and higher-level representation spaces. Experiments show the potential of the proposed networks.
Sampled Image Tagging and Retrieval Methods on User Generated Content
Venue: arXiv cs.CV 2016
Year: 2016

Traditional image tagging and retrieval algorithms have limited value as a result of being trained with heavily curated datasets. These limitations are most evident when arbitrary search words are used that do not intersect with training set labels. Weak labels from user generated content (UGC) found in the wild (e.g., Google Photos, FlickR, etc.) have an almost unlimited number of unique words in the metadata tags. Prior work on word embeddings successfully leveraged unstructured text with large vocabularies, and our proposed method seeks to apply similar cost functions to open source imagery. Specifically, we train a deep learning image tagging and retrieval system on large scale, user generated content (UGC) using sampling methods and joint optimization of word embeddings. By using the Yahoo! FlickR Creative Commons (YFCC100M) dataset, such an approach builds robustness to common unstructured data issues that include but are not limited to irrelevant tags, misspellings, multiple languages, polysemy, and tag imbalance. As a result, the final proposed algorithm will not only yield comparable results to state of the art in conventional image tagging, but will enable new capability to train algorithms on large, scale unstructured text in the YFCC100M dataset and outperform cited work in zero-shot capability.
Kernel Cross-View Collaborative Representation based Classification for Person Re-Identification
Venue: arXiv cs.CV 2016
Year: 2016

Person re-identification aims at the maintenance of a global identity as a person moves among non-overlapping surveillance cameras. It is a hard task due to different illumination conditions, viewpoints and the small number of annotated individuals from each pair of cameras (small-sample-size problem). Collaborative Representation based Classification (CRC) has been employed successfully to address the small-sample-size problem in computer vision. However, the original CRC formulation is not well-suited for person re-identification since it does not consider that probe and gallery samples are from different cameras. Furthermore, it is a linear model, while appearance changes caused by different camera conditions indicate a strong nonlinear transition between cameras. To overcome such limitations, we propose the Kernel Cross-View Collaborative Representation based Classification (Kernel X-CRC) that represents probe and gallery images by balancing representativeness and similarity nonlinearly. It assumes that a probe and its corresponding gallery image are represented with similar coding vectors using individuals from the training set. Experimental results demonstrate that our assumption is true when using a high-dimensional feature vector and becomes more compelling when dealing with a low-dimensional and discriminative representation computed using a common subspace learning method. We achieve state-of-the-art for rank-1 matching rates in two person re-identification datasets (PRID450S and GRID) and the second best results on VIPeR and CUHK01 datasets.
SROS: Securing ROS over the wire, in the graph, and through the kernel
Venue: arXiv cs.RO 2016
Year: 2016

SROS is a proposed addition to the ROS API and ecosystem to support modern cryptography and security measures. An overview of current progress will be presented, rationalizing each major advancement, including: over-the-wire cryptography for all data transport, namespaced access control enforcing graph policies/restrictions, and finally process profiles using Linux Security Modules to harden a node's resource access. By making the community aware of the vulnerabilities in ROS, as well as the proposed solutions provided by SROS, we intend to improve the state of security for future robotics subsystems.
The Use of Application Scanners in Software Product Quality Assessment
Venue: arXiv cs.SE 2016
Year: 2016

Software development needs continuous quality control for a timely detection and removal of quality problems. This includes frequent quality assessments, which need to be automated as far as possible to be feasible. One way of automation in assessing the security of software are application scanners that test an executing software for vulnerabilities. At present, common quality assessments do not integrate such scanners for giving an overall quality statement. This paper presents an integration of application scanners into a general quality assessment method based on explicit quality models and Bayesian nets. Its applicability and the detection capabilities of common scanners are investigated in a case study with two open-source web shops.
pocl: A Performance-Portable OpenCL Implementation
Venue: arXiv cs.DC 2016
Year: 2016

OpenCL is a standard for parallel programming of heterogeneous systems. The benefits of a common programming standard are clear; multiple vendors can provide support for application descriptions written according to the standard, thus reducing the program porting effort. While the standard brings the obvious benefits of platform portability, the performance portability aspects are largely left to the programmer. The situation is made worse due to multiple proprietary vendor implementations with different characteristics, and, thus, required optimization strategies. In this paper, we propose an OpenCL implementation that is both portable and performance portable. At its core is a kernel compiler that can be used to exploit the data parallelism of OpenCL programs on multiple platforms with different parallel hardware styles. The kernel compiler is modularized to perform target-independent parallel region formation separately from the target-specific parallel mapping of the regions to enable support for various styles of fine-grained parallel resources such as subword SIMD extensions, SIMD datapaths and static multi-issue. Unlike previous similar techniques that work on the source level, the parallel region formation retains the information of the data parallelism using the LLVM IR and its metadata infrastructure. This data can be exploited by the later generic compiler passes for efficient parallelization. The proposed open source implementation of OpenCL is also platform portable, enabling OpenCL on a wide range of architectures, both already commercialized and on those that are still under research. The paper describes how the portability of the implementation is achieved. Our results show that most of the benchmarked applications when compiled using pocl were faster or close to as fast as the best proprietary OpenCL implementation for the platform at hand.
Identity Testing for +-Regular Noncommutative Arithmetic Circuits
Venue: arXiv cs.CC 2016
Year: 2016

An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can compute a polynomial of degree exponential in $s$ with a double-exponential number of nonzero monomials. In this paper, we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials): (1) We consider \emph{$+$-regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the $+$-gates are layered, and in each $+$-layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for $+$-regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider $ΣΠ^*Σ$ noncommutative circuits: these are noncommutative circuits with layered $+$-gates such that there are only two layers of $+$-gates. These $+$-layers are the output $+$-gate and linear forms at the bottom layer; between the $+$-layers the circuit could have any number of $\times$ gates. We given an efficient randomized \emph{black-box} identity testing problem for $ΣΠ^*Σ$ circuits. In particular, we show if $f\in F<Z>$ is a nonzero noncommutative polynomial computed by a $ΣΠ^*Σ$ circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(F)$, where the field $F$ is a sufficiently large extension of $F$ depending on the degree of $f$.
Asymptotic expansions for factorial moments of some distributions in the analysis of algorithms
Venue: arXiv cs.DS 2016
Year: 2016

We establish asymptotic expansions for factorial moments of following distributions: number of cycles in a random permutation, number of inversions in a random permutation, and number of comparisons used by the randomized quick sort algorithm.To achieve this we use singularity analysis of certain type of generating functions due to Flajolet and Odlyzko.
Lazy Local Search Meets Machine Scheduling
Venue: arXiv cs.DS 2016
Year: 2016

We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs $J$ with processing times $p_j$ and each job may be scheduled only on some subset of machines $S_j \subseteq M$. The goal is to find an assignment of jobs to machines to minimize the time by which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos designed an elegant $2$-approximation for the problem in 1987. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of Configuration LPs, it now appears an attainable goal to design such an algorithm. Our main contribution is to make progress towards this goal. When the processing times of jobs are either $1$ or $ε\in (0,1)$, we design an approximation algorithm whose guarantee tends to $1 + \sqrt{3}/2 \approx 1.8660254,$ for the interesting cases when $ε\to 0$. This improves on the $2-ε_0$ guarantee recently obtained by Chakrabarty, Khanna, and Li for some constant $ε_0 > 0$.