OpenRaiser/Intern-Atlas huggingface dataset:
Packing Cycles Faster Than Erdős-Pósa
Venue: arXiv cs.DS 2017
Year: 2017

The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since the publication of the classic Erdős-Pósa theorem in 1965, this problem received significant scientific attention in the fields of Graph Theory and Algorithm Design. In particular, this problem is one of the first problems studied in the framework of Parameterized Complexity. The non-uniform fixed-parameter tractability of Cycle Packing follows from the Robertson-Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time $2^{\mathcal{O}(k^2)}\cdot |V|$ using exponential space. In case a solution exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a $2^{\mathcal{O}(k\log^2k)}\cdot |V|$-time (deterministic) algorithm using exponential space, which is a consequence of the Erdős-Pósa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on Parameterized Complexity. Yet, no algorithm that runs in time $2^{o(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, has been found. In light of this, it seems natural to ask whether the $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer this question negatively by developing a $2^{\mathcal{O}(\frac{k\log^2k}{\log\log k})}\cdot |V|$-time (deterministic) algorithm for Cycle Packing. In case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound $2^{\mathcal{O}(k\log^2k)}\cdot |V|^{\mathcal{O}(1)}$, our algorithm runs in time linear in $|V|$, and its space complexity is polynomial in the input size.
LittleDarwin: a Feature-Rich and Extensible Mutation Testing Framework for Large and Complex Java Systems
Venue: arXiv cs.SE 2017
Year: 2017

Mutation testing is a well-studied method for increasing the quality of a test suite. We designed LittleDarwin as a mutation testing framework able to cope with large and complex Java software systems, while still being easily extensible with new experimental components. LittleDarwin addresses two existing problems in the domain of mutation testing: having a tool able to work within an industrial setting, and yet, be open to extension for cutting edge techniques provided by academia. LittleDarwin already offers higher-order mutation, null type mutants, mutant sampling, manual mutation, and mutant subsumption analysis. There is no tool today available with all these features that is able to work with typical industrial software systems.
Publish or impoverish: An investigation of the monetary reward system of science in China (1999-2016)
Venue: arXiv cs.DL 2017
Year: 2017

Purpose: The purpose of this study is to present the landscape of the cash-per-publication reward policy in China and reveal its trend since the late 1990s. Design/methodology/approach: This study is based on the analysis of 168 university documents regarding the cash-per-publication reward policy at 100 Chinese universities. Findings: Chinese universities offer cash rewards from 30 to 165,000 USD for papers published in journals indexed by Web of Science (WoS), and the average reward amount has been increasing for the past 10 years. Originality/value: The cash-per-publication reward policy in China has never been systematically studied and investigated before except for in some case studies. This is the first paper that reveals the landscape of the cash-per-publication reward policy in China.
Biased Predecessor Search
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of performing predecessor searches in a bounded universe while achieving query times that depend on the distribution of queries. We obtain several data structures with various properties: in particular, we give data structures that achieve expected query times logarithmic in the entropy of the distribution of queries but with space bounded in terms of universe size, as well as data structures that use only linear space but with query times that are higher (but still sublinear) functions of the entropy. For these structures, the distribution is assumed to be known. We also consider individual query times on universe elements with general weights, as well as the case when the distribution is not known in advance.
A Survey of Recent Advances in CNN-based Single Image Crowd Counting and Density Estimation
Venue: arXiv cs.CV 2017
Year: 2017

Estimating count and density maps from crowd images has a wide range of applications such as video surveillance, traffic monitoring, public safety and urban planning. In addition, techniques developed for crowd counting can be applied to related tasks in other fields of study such as cell microscopy, vehicle counting and environmental survey. The task of crowd counting and density map estimation is riddled with many challenges such as occlusions, non-uniform density, intra-scene and inter-scene variations in scale and perspective. Nevertheless, over the last few years, crowd count analysis has evolved from earlier methods that are often limited to small variations in crowd density and scales to the current state-of-the-art methods that have developed the ability to perform successfully on a wide range of scenarios. The success of crowd counting methods in the recent years can be largely attributed to deep learning and publications of challenging datasets. In this paper, we provide a comprehensive survey of recent Convolutional Neural Network (CNN) based approaches that have demonstrated significant improvements over earlier methods that rely largely on hand-crafted representations. First, we briefly review the pioneering methods that use hand-crafted representations and then we delve in detail into the deep learning-based approaches and recently published datasets. Furthermore, we discuss the merits and drawbacks of existing CNN-based approaches and identify promising avenues of research in this rapidly evolving field.
The Complexity of Human Computation: A Concrete Model with an Application to Passwords
Venue: arXiv cs.HC 2017
Year: 2017

What can humans compute in their heads? We are thinking of a variety of Crypto Protocols, games like Sudoku, Crossword Puzzles, Speed Chess, and so on. The intent of this paper is to apply the ideas and methods of theoretical computer science to better understand what humans can compute in their heads. For example, can a person compute a function in their head so that an eavesdropper with a powerful computer --- who sees the responses to random input --- still cannot infer responses to new inputs? To address such questions, we propose a rigorous model of human computation and associated measures of complexity. We apply the model and measures first and foremost to the problem of (1) humanly computable password generation, and then consider related problems of (2) humanly computable "one-way functions" and (3) humanly computable "pseudorandom generators". The theory of Human Computability developed here plays by different rules than standard computability, and this takes some getting used to. For reasons to be made clear, the polynomial versus exponential time divide of modern computability theory is irrelevant to human computation. In human computability, the step-counts for both humans and computers must be more concrete. Specifically, we restrict the adversary to at most 10^24 (Avogadro number of) steps. An alternate view of this work is that it deals with the analysis of algorithms and counting steps for the case that inputs are small as opposed to the usual case of inputs large-in-the-limit.
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Venue: arXiv cs.DS 2017
Year: 2017

We study the maximum induced matching problem on a graph g. Induced matchings correspond to independent sets in L2(g), the square of the line graph of g. The problem is NP-complete on bipartite graphs. In this work, we show that for a number of graph families with forbidden vertex orderings, almost all forbidden patterns on three vertices are preserved when taking the square of the line graph. These orderings can be computed in linear time in the size of the input graph. In particular, given a graph class G characterized by a vertex ordering, and a graph g = (V, E) in G with a corresponding vertex ordering σof V , one can produce (in linear time in the size of g) an ordering on the vertices of L2(g), that shows that L2(g) in G - for a number of graph classes G - without computing the line graph or the square of the line graph of g. These results generalize and unify previous ones on showing closure under L2(.) for various graph families. Furthermore, these orderings on L2(g) can be exploited algorithmically to compute a maximum induced matching on G faster. We illustrate this latter fact in the second half of the paper where we focus on cocomparability graphs, a large graph class that includes interval, permutation, trapezoid graphs, and co-graphs, and we present the first O(mn) time algorithm to compute a maximum weighted induced matching on cocomparability graphs; an improvement from the best known O(n4) time algorithm for the unweighted case.
SADA: A General Framework to Support Robust Causation Discovery with Theoretical Guarantee
Venue: arXiv cs.AI 2017
Year: 2017

Causation discovery without manipulation is considered a crucial problem to a variety of applications. The state-of-the-art solutions are applicable only when large numbers of samples are available or the problem domain is sufficiently small. Motivated by the observations of the local sparsity properties on causal structures, we propose a general Split-and-Merge framework, named SADA, to enhance the scalability of a wide class of causation discovery algorithms. In SADA, the variables are partitioned into subsets, by finding causal cut on the sparse causal structure over the variables. By running mainstream causation discovery algorithms as basic causal solvers on the subproblems, complete causal structure can be reconstructed by combining the partial results. SADA benefits from the recursive division technique, since each small subproblem generates more accurate result under the same number of samples. We theoretically prove that SADA always reduces the scales of problems without sacrifice on accuracy, under the condition of local causal sparsity and reliable conditional independence tests. We also present sufficient condition to accuracy enhancement by SADA, even when the conditional independence tests are vulnerable. Extensive experiments on both simulated and real-world datasets verify the improvements on scalability and accuracy by applying SADA together with existing causation discovery algorithms.
Robust Multi-Image HDR Reconstruction for the Modulo Camera
Venue: arXiv cs.CV 2017
Year: 2017

Photographing scenes with high dynamic range (HDR) poses great challenges to consumer cameras with their limited sensor bit depth. To address this, Zhao et al. recently proposed a novel sensor concept - the modulo camera - which captures the least significant bits of the recorded scene instead of going into saturation. Similar to conventional pipelines, HDR images can be reconstructed from multiple exposures, but significantly fewer images are needed than with a typical saturating sensor. While the concept is appealing, we show that the original reconstruction approach assumes noise-free measurements and quickly breaks down otherwise. To address this, we propose a novel reconstruction algorithm that is robust to image noise and produces significantly fewer artifacts. We theoretically analyze correctness as well as limitations, and show that our approach significantly outperforms the baseline on real data.
The Influence of Feature Representation of Text on the Performance of Document Classification
Venue: arXiv cs.CL 2017
Year: 2017

In this paper we perform a comparative analysis of three models for feature representation of text documents in the context of document classification. In particular, we consider the most often used family of models bag-of-words, recently proposed continuous space models word2vec and doc2vec, and the model based on the representation of text documents as language networks. While the bag-of-word models have been extensively used for the document classification task, the performance of the other two models for the same task have not been well understood. This is especially true for the network-based model that have been rarely considered for representation of text documents for classification. In this study, we measure the performance of the document classifiers trained using the method of random forests for features generated the three models and their variants. The results of the empirical comparison show that the commonly used bag-of-words model has performance comparable to the one obtained by the emerging continuous-space model of doc2vec. In particular, the low-dimensional variants of doc2vec generating up to 75 features are among the top-performing document representation models. The results finally point out that doc2vec shows a superior performance in the tasks of classifying large documents.
A dataset for Computer-Aided Detection of Pulmonary Embolism in CTA images
Venue: arXiv cs.CV 2017
Year: 2017

Todays, researchers in the field of Pulmonary Embolism (PE) analysis need to use a publicly available dataset to assess and compare their methods. Different systems have been designed for the detection of pulmonary embolism (PE), but none of them have used any public datasets. All papers have used their own private dataset. In order to fill this gap, we have collected 5160 slices of computed tomography angiography (CTA) images acquired from 20 patients, and after labeling the image by experts in this field, we provided a reliable dataset which is now publicly available. In some situation, PE detection can be difficult, for example when it occurs in the peripheral branches or when patients have pulmonary diseases (such as parenchymal disease). Therefore, the efficiency of CAD systems highly depends on the dataset. In the given dataset, 66% of PE are located in peripheral branches, and different pulmonary diseases are also included.
Web Video in Numbers - An Analysis of Web-Video Metadata
Venue: arXiv cs.MM 2017
Year: 2017

Web video is often used as a source of data in various fields of study. While specialized subsets of web video, mainly earmarked for dedicated purposes, are often analyzed in detail, there is little information available about the properties of web video as a whole. In this paper we present insights gained from the analysis of the metadata associated with more than 120 million videos harvested from two popular web video platforms, vimeo and YouTube, in 2016 and compare their properties with the ones found in commonly used video collections. This comparison has revealed that existing collections do not (or no longer) properly reflect the properties of web video "in the wild".
A Modern Approach to Integrate Database Queries for Searching E-Commerce Product
Venue: arXiv cs.DB 2017
Year: 2017

E commerce refers to the utilization of electronic data transmission for enhancing business processes and implementing business strategies. Explicit components of e commerce include providing after sales services, promoting services or products to services, processing payment, engaging in transaction processes, identifying customer needs, processing payment and creating services or products. In recent times, the use of e commerce has become too common among the people. However, the growing demand of e commerce sites have made essential for the databases to support direct querying of the Web page. This research aims to explore and evaluate the integration of database queries and their uses in searching of electronic commerce products. It has been analyzed that e commerce is one of the most outstanding trends, which have been emerged in the commerce world, for the last decades. Therefore, this study was undertaken to examine the benefits of integrating database queries with e commerce product searches. The findings of this study suggested that database queries are extremely valuable for e commerce sites as they make product searches simpler and accurate. In this context, the approach of integrating database queries is found to be the most suitable and satisfactory, as it simplifies the searching of e commerce products.
Bounding the number of common zeros of multivariate polynomials and their consecutive derivatives
Venue: arXiv cs.IT 2017
Year: 2017

We upper bound the number of common zeros over a finite grid of multivariate polynomials and an arbitrary finite collection of their consecutive Hasse derivatives (in a coordinate-wise sense). To that end, we make use of the tool from Gröbner basis theory known as footprint. Then we establish and prove extensions in this context of a family of well-known results in algebra and combinatorics. These include Alon's combinatorial Nullstellensatz, existence and uniqueness of Hermite interpolating polynomials over a grid, estimations on the parameters of evaluation codes with consecutive derivatives, and bounds on the number of zeros of a polynomial by DeMillo and Lipton, Schwartz, Zippel, and Alon and Füredi. As an alternative, we also extend the Schwartz-Zippel bound to weighted multiplicities and discuss its connection with our extension of the footprint bound.
Align and Copy: UZH at SIGMORPHON 2017 Shared Task for Morphological Reinflection
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents the submissions by the University of Zurich to the SIGMORPHON 2017 shared task on morphological reinflection. The task is to predict the inflected form given a lemma and a set of morpho-syntactic features. We focus on neural network approaches that can tackle the task in a limited-resource setting. As the transduction of the lemma into the inflected form is dominated by copying over lemma characters, we propose two recurrent neural network architectures with hard monotonic attention that are strong at copying and, yet, substantially different in how they achieve this. The first approach is an encoder-decoder model with a copy mechanism. The second approach is a neural state-transition system over a set of explicit edit actions, including a designated COPY action. We experiment with character alignment and find that naive, greedy alignment consistently produces strong results for some languages. Our best system combination is the overall winner of the SIGMORPHON 2017 Shared Task 1 without external resources. At a setting with 100 training samples, both our approaches, as ensembles of models, outperform the next best competitor.
Improving Content-Invariance in Gated Autoencoders for 2D and 3D Object Rotation
Venue: arXiv cs.CV 2017
Year: 2017

Content-invariance in mapping codes learned by GAEs is a useful feature for various relation learning tasks. In this paper we show that the content-invariance of mapping codes for images of 2D and 3D rotated objects can be substantially improved by extending the standard GAE loss (symmetric reconstruction error) with a regularization term that penalizes the symmetric cross-reconstruction error. This error term involves reconstruction of pairs with mapping codes obtained from other pairs exhibiting similar transformations. Although this would principally require knowledge of the transformations exhibited by training pairs, our experiments show that a bootstrapping approach can sidestep this issue, and that the regularization term can effectively be used in an unsupervised setting.
Analyzing Guarded Protocols: Better Cutoffs, More Systems, More Expressivity
Venue: arXiv cs.LO 2017
Year: 2017

We study cutoff results for parameterized verification and synthesis of guarded protocols, as introduced by Emerson and Kahlon (2000). Guarded protocols describe systems of processes whose transitions are enabled or disabled depending on the existence of other processes in certain local states. Cutoff results reduce reasoning about systems with an arbitrary number of processes to systems of a determined, fixed size. Our work is based on the observation that existing cutoff results for guarded protocols are often impractical, since they scale linearly in the number of local states of processes in the system. We provide new cutoffs that scale not with the number of local states, but with the number of guards in the system, which is in many cases much smaller. Furthermore, we consider natural extensions of the classes of systems and specifications under consideration, and present results for problems that have not been known to admit cutoffs before.
Towards Recommender Systems for Police Photo Lineup
Venue: arXiv cs.IR 2017
Year: 2017

Photo lineups play a significant role in the eyewitness identification process. This method is used to provide evidence in the prosecution and subsequent conviction of suspects. Unfortunately, there are many cases where lineups have led to the conviction of an innocent suspect. One of the key factors affecting the incorrect identification of a suspect is the lack of lineup fairness, i.e. that the suspect differs significantly from all other candidates. Although the process of assembling fair lineup is both highly important and time-consuming, only a handful of tools are available to simplify the task. In this paper, we describe our work towards using recommender systems for the photo lineup assembling task. We propose and evaluate two complementary methods for item-based recommendation: one based on the visual descriptors of the deep neural network, the other based on the content-based attributes of persons. The initial evaluation made by forensic technicians shows that although results favored visual descriptors over attribute-based similarity, both approaches are functional and highly diverse in terms of recommended objects. Thus, future work should involve incorporating both approaches in a single prediction method, preference learning based on the feedback from forensic technicians and recommendation of assembled lineups instead of single candidates.
Determining sentiment in citation text and analyzing its impact on the proposed ranking index
Venue: arXiv cs.IR 2017
Year: 2017

Whenever human beings interact with each other, they exchange or express opinions, emotions, and sentiments. These opinions can be expressed in text, speech or images. Analysis of these sentiments is one of the popular research areas of present day researchers. Sentiment analysis, also known as opinion mining tries to identify or classify these sentiments or opinions into two broad categories - positive and negative. In recent years, the scientific community has taken a lot of interest in analyzing sentiment in textual data available in various social media platforms. Much work has been done on social media conversations, blog posts, newspaper articles and various narrative texts. However, when it comes to identifying emotions from scientific papers, researchers have faced some difficulties due to the implicit and hidden nature of opinion. By default, citation instances are considered inherently positive in emotion. Popular ranking and indexing paradigms often neglect the opinion present while citing. In this paper, we have tried to achieve three objectives. First, we try to identify the major sentiment in the citation text and assign a score to the instance. We have used a statistical classifier for this purpose. Secondly, we have proposed a new index (we shall refer to it hereafter as M-index) which takes into account both the quantitative and qualitative factors while scoring a paper. Thirdly, we developed a ranking of research papers based on the M-index. We also try to explain how the M-index impacts the ranking of scientific papers.