OpenRaiser/Intern-Atlas huggingface dataset:
A Fast Parameterized Algorithm for Co-Path Set
Venue: arXiv cs.DS 2016
Year: 2016

The k-CO-PATH SET problem asks, given a graph G and a positive integer k, whether one can delete k edges from G so that the remainder is a collection of disjoint paths. We give a linear-time fpt algorithm with complexity O^*(1.588^k) for deciding k-CO-PATH SET, significantly improving the previously best known O^*(2.17^k) of Feng, Zhou, and Wang (2015). Our main tool is a new O^*(4^{tw(G)}) algorithm for CO-PATH SET using the Cut&Count framework, where tw(G) denotes treewidth. In general graphs, we combine this with a branching algorithm which refines a 6k-kernel into reduced instances, which we prove have bounded treewidth.
Rapid building detection using machine learning
Venue: arXiv cs.CV 2016
Year: 2016

This work describes algorithms for performing discrete object detection, specifically in the case of buildings, where usually only low quality RGB-only geospatial reflective imagery is available. We utilize new candidate search and feature extraction techniques to reduce the problem to a machine learning (ML) classification task. Here we can harness the complex patterns of contrast features contained in training data to establish a model of buildings. We avoid costly sliding windows to generate candidates; instead we innovatively stitch together well known image processing techniques to produce candidates for building detection that cover 80-85% of buildings. Reducing the number of possible candidates is important due to the scale of the problem. Each candidate is subjected to classification which, although linear, costs time and prohibits large scale evaluation. We propose a candidate alignment algorithm to boost classification performance to 80-90% precision with a linear time algorithm and show it has negligible cost. Also, we propose a new concept called a Permutable Haar Mesh (PHM) which we use to form and traverse a search space to recover candidate buildings which were lost in the initial preprocessing phase.
Taxi Dispatch with Real-Time Sensing Data in Metropolitan Areas: A Receding Horizon Control Approach
Venue: arXiv cs.SY 2016
Year: 2016

Traditional taxi systems in metropolitan areas often suffer from inefficiencies due to uncoordinated actions as system capacity and customer demand change. With the pervasive deployment of networked sensors in modern vehicles, large amounts of information regarding customer demand and system status can be collected in real time. This information provides opportunities to perform various types of control and coordination for large-scale intelligent transportation systems. In this paper, we present a receding horizon control (RHC) framework to dispatch taxis, which incorporates highly spatiotemporally correlated demand/supply models and real-time GPS location and occupancy information. The objectives include matching spatiotemporal ratio between demand and supply for service quality with minimum current and anticipated future taxi idle driving distance. Extensive trace-driven analysis with a data set containing taxi operational records in San Francisco shows that our solution reduces the average total idle distance by 52%, and reduces the supply demand ratio error across the city during one experimental time slot by 45%. Moreover, our RHC framework is compatible with a wide variety of predictive models and optimization problem formulations. This compatibility property allows us to solve robust optimization problems with corresponding demand uncertainty models that provide disruptive event information.
Fast calculation of inverse square root with the use of magic constant $-$ analytical approach
Venue: arXiv cs.MS 2016
Year: 2016

We present a mathematical analysis of transformations used in fast calculation of inverse square root for single-precision floating-point numbers. Optimal values of the so called magic constants are derived in a systematic way, minimizing either absolute or relative errors at subsequent stages of the discussed algorithm.
Optimal Sensing via Multi-armed Bandit Relaxations in Mixed Observability Domains
Venue: arXiv cs.AI 2016
Year: 2016

Sequential decision making under uncertainty is studied in a mixed observability domain. The goal is to maximize the amount of information obtained on a partially observable stochastic process under constraints imposed by a fully observable internal state. An upper bound for the optimal value function is derived by relaxing constraints. We identify conditions under which the relaxed problem is a multi-armed bandit whose optimal policy is easily computable. The upper bound is applied to prune the search space in the original problem, and the effect on solution quality is assessed via simulation experiments. Empirical results show effective pruning of the search space in a target monitoring domain.
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory
Venue: arXiv cs.CC 2016
Year: 2016

We provide a list of new natural $\mathsf{VNP}$-intermediate polynomial families, based on basic (combinatorial) $\mathsf{NP}$-complete problems that are complete under parsimonious reductions. Over finite fields, these families are in $\mathsf{VNP}$, and under the plausible hypothesis $\mathsf{Mod}_p\mathsf{P} \not\subseteq \mathsf{P/poly}$, are neither $\mathsf{VNP}$-hard (even under oracle-circuit reductions) nor in $\mathsf{VP}$. Prior to this, only the Cut Enumerator polynomial was known to be $\mathsf{VNP}$-intermediate, as shown by Bürgisser in 2000. We next show that over rationals and reals, two of our intermediate polynomials, based on satisfiability and Hamiltonian cycle, are not monotone affine polynomial-size projections of the permanent. This augments recent results along this line due to Grochow. Finally, we describe a (somewhat natural) polynomial defined independent of a computation model, and show that it is $\mathsf{VP}$-complete under polynomial-size projections. This complements a recent result of Durand et al. (2014) which established $\mathsf{VP}$-completeness of a related polynomial but under constant-depth oracle circuit reductions. Both polynomials are based on graph homomorphisms. A simple restriction yields a family similarly complete for $\mathsf{VBP}$.
Scalable Image Retrieval by Sparse Product Quantization
Venue: arXiv cs.CV 2016
Year: 2016

Fast Approximate Nearest Neighbor (ANN) search technique for high-dimensional feature indexing and retrieval is the crux of large-scale image retrieval. A recent promising technique is Product Quantization, which attempts to index high-dimensional image features by decomposing the feature space into a Cartesian product of low dimensional subspaces and quantizing each of them separately. Despite the promising results reported, their quantization approach follows the typical hard assignment of traditional quantization methods, which may result in large quantization errors and thus inferior search performance. Unlike the existing approaches, in this paper, we propose a novel approach called Sparse Product Quantization (SPQ) to encoding the high-dimensional feature vectors into sparse representation. We optimize the sparse representations of the feature vectors by minimizing their quantization errors, making the resulting representation is essentially close to the original data in practice. Experiments show that the proposed SPQ technique is not only able to compress data, but also an effective encoding technique. We obtain state-of-the-art results for ANN search on four public image datasets and the promising results of content-based image retrieval further validate the efficacy of our proposed method.
Energy Costs for Traffic Offloading by Cache-enabled D2D Communications
Venue: arXiv cs.IT 2016
Year: 2016

Device-to-Device (D2D) communications can offload the traffic and boost the throughput of cellular networks. By caching files at users, content delivery traffic can be offloaded via D2D links, if a helper user are willing to send the cached file to the user who requests the file. Yet it is unclear how much energy needs to be consumed at a helper user to support the traffic offloading. In this paper, we strive to find the minimal energy consumption required at a helper user to maximize the amount of offloaded traffic. To this end, we introduce a user-centric proactive caching policy that can control the energy cost for a helper user to convey a file, and then optimize the caching policy to maximize the offloaded traffic. To reduce the energy during transmission, we optimize the transmit power to minimize the energy consumed by a helper to send a file. We analyze the relationship between traffic offloading and energy cost with the optimized caching policy and transmit power by numerical and simulation results, which demonstrate that a significant amount of traffic can be offloaded with affordable energy costs.
Evaluating the word-expert approach for Named-Entity Disambiguation
Venue: arXiv cs.CL 2016
Year: 2016

Named Entity Disambiguation (NED) is the task of linking a named-entity mention to an instance in a knowledge-base, typically Wikipedia. This task is closely related to word-sense disambiguation (WSD), where the supervised word-expert approach has prevailed. In this work we present the results of the word-expert approach to NED, where one classifier is built for each target entity mention string. The resources necessary to build the system, a dictionary and a set of training instances, have been automatically derived from Wikipedia. We provide empirical evidence of the value of this approach, as well as a study of the differences between WSD and NED, including ambiguity and synonymy statistics.
Ensemble of Deep Convolutional Neural Networks for Learning to Detect Retinal Vessels in Fundus Images
Venue: arXiv cs.LG 2016
Year: 2016

Vision impairment due to pathological damage of the retina can largely be prevented through periodic screening using fundus color imaging. However the challenge with large scale screening is the inability to exhaustively detect fine blood vessels crucial to disease diagnosis. In this work we present a computational imaging framework using deep and ensemble learning for reliable detection of blood vessels in fundus color images. An ensemble of deep convolutional neural networks is trained to segment vessel and non-vessel areas of a color fundus image. During inference, the responses of the individual ConvNets of the ensemble are averaged to form the final segmentation. In experimental evaluation with the DRIVE database, we achieve the objective of vessel detection with maximum average accuracy of 94.7\% and area under ROC curve of 0.9283.
Parallel Algorithms for Select and Partition with Noisy Comparisons
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of finding the $k^{th}$ highest element in a totally ordered set of $n$ elements (select), and partitioning a totally ordered set into the top $k$ and bottom $n-k$ elements (partition) using pairwise comparisons. Motivated by settings like peer grading or crowdsourcing, where multiple rounds of interaction are costly and queried comparisons may be inconsistent with the ground truth, we evaluate algorithms based both on their total runtime and the number of interactive rounds in three comparison models: noiseless (where the comparisons are correct), erasure (where comparisons are erased with probability $1-γ$), and noisy (where comparisons are correct with probability $1/2+γ/2$ and incorrect otherwise). We provide numerous matching upper and lower bounds in all three models. Even our results in the noiseless model, which is quite well-studied in the TCS literature on parallel algorithms, are novel.
On the effect of randomness on planted 3-coloring models
Venue: arXiv cs.CC 2016
Year: 2016

We present the hosted coloring framework for studying algorithmic and hardness results for the $k$-coloring problem. There is a class ${\cal H}$ of host graphs. One selects a graph $H\in{\cal H}$ and plants in it a balanced $k$-coloring (by partitioning the vertex set into $k$ roughly equal parts, and removing all edges within each part). The resulting graph $G$ is given as input to a polynomial time algorithm that needs to $k$-color $G$ (any legal $k$-coloring would do -- the algorithm is not required to recover the planted $k$-coloring). Earlier planted models correspond to the case that ${\cal H}$ is the class of all $n$-vertex $d$-regular graphs, a member $H\in{\cal H}$ is chosen at random, and then a balanced $k$-coloring is planted at random. Blum and Spencer [1995] designed algorithms for this model when $d=n^δ$ (for $0<δ\le1$), and Alon and Kahale [1997] managed to do so even when $d$ is a sufficiently large constant. The new aspect in our framework is that it need not involve randomness. In one model within the framework (with $k=3$) $H$ is a $d$ regular spectral expander (meaning that except for the largest eigenvalue of its adjacency matrix, every other eigenvalue has absolute value much smaller than $d$) chosen by an adversary, and the planted 3-coloring is random. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In another model $H$ is a random $d$-regular graph but the planted balanced $3$-coloring is chosen by an adversary, after seeing $H$. We show that for a certain range of average degrees somewhat below $\sqrt{n}$, finding a 3-coloring is NP-hard. Together these results (and other results that we have) help clarify which aspects of randomness in the planted coloring model are the key to successful 3-coloring algorithms.
Applying Artifical Neural Networks To Predict Nominal Vehicle Performance
Venue: arXiv cs.NE 2016
Year: 2016

This paper investigates the use of artificial neural networks (ANNs) to replace traditional algorithms and manual review for identifying anomalies in vehicle run data. The specific data used for this study is from undersea vehicle qualification tests. Such data is highly non-linear, therefore traditional algorithms are not adequate and manual review is time consuming. By using ANNs to predict nominal vehicle performance based solely on information available pre-run, vehicle deviation from expected performance can be automatically identified in the post-run data. Such capability is only now becoming available due to the rapid increase in understanding of ANN framework and available computing power in the past decade. The ANN trained for the purpose of this investigation is relatively simple, to keep the computing requirements within the parameters of a modern desktop PC. This ANN showed potential in predicting vehicle performance, particularly during transient events within the run data. However, there were also several performance cases, such as steady state operation and cases which did not have sufficient training data, where the ANN showed deficiencies. It is expected that as computational power becomes more readily available, ANN understanding matures, and more training data is acquired from real world tests, the performance predictions of the ANN will surpass traditional algorithms and manual human review.
Embedding by Normalisation
Venue: arXiv cs.PL 2016
Year: 2016

This paper presents the insight that practical embedding techniques, commonly used for implementing Domain-Specific Languages, correspond to theoretical Normalisation-By-Evaluation (NBE) techniques, commonly used for deriving canonical form of terms with respect to an equational theory. NBE constitutes of four components: a syntactic domain, a semantic domain, and a pair of translations between the two. Embedding also often constitutes of four components: an object language, a host language, encoding of object terms in the host, and extraction of object code from the host. The correspondence is deep in that all four components in embedding and NBE correspond to each other. Based on this correspondence, this paper introduces Embedding-By-Normalisation (EBN) as a principled approach to study and structure embedding. The correspondence is useful in that solutions from NBE can be borrowed to solve problems in embedding. In particular, based on NBE techniques, such as Type-Directed Partial Evaluation, this paper presents a solution to the problem of extracting object code from embedded programs involving sum types, such as conditional expressions, and primitives, such as literals and operations on them.
Optimal Quantile Approximation in Streams
Venue: arXiv cs.DS 2016
Year: 2016

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An $\varepsilon$ approximate quantile sketch receives a stream of items $x_1,\ldots,x_n$ and allows one to approximate the rank of any query up to additive error $\varepsilon n$ with probability at least $1-δ$. The rank of a query $x$ is the number of stream items such that $x_i \le x$. The minimal sketch size required for this task is trivially at least $1/\varepsilon$. Felber and Ostrovsky obtain a $O((1/\varepsilon)\log(1/\varepsilon))$ space sketch for a fixed $δ$. To date, no better upper or lower bounds were known even for randomly permuted streams or for approximating a specific quantile, e.g.,\ the median. This paper obtains an $O((1/\varepsilon)\log \log (1/δ))$ space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This subtle modification allows for an analysis which is both tight and extremely simple. Similar techniques should be useful for improving other sketching objectives and geometric coreset constructions.
Modeling self-organization of vocabularies under phonological similarity effects
Venue: arXiv cs.CL 2016
Year: 2016

This work develops a computational model (by Automata Networks) of phonological similarity effects involved in the formation of word-meaning associations on artificial populations of speakers. Classical studies show that in recalling experiments memory performance was impaired for phonologically similar words versus dissimilar ones. Here, the individuals confound phonologically similar words according to a predefined parameter. The main hypothesis is that there is a critical range of the parameter, and with this, of working-memory mechanisms, which implies drastic changes in the final consensus of the entire population. Theoretical results present proofs of convergence for a particular case of the model within a worst-case complexity framework. Computer simulations describe the evolution of an energy function that measures the amount of local agreement between individuals. The main finding is the appearance of sudden changes in the energy function at critical parameters.
Self-Interference Cancellation Using Time-Domain Phase Noise Estimation in OFDM Full-Duplex Systems
Venue: arXiv cs.IT 2016
Year: 2016

In full-duplex systems, oscillator phase noise (PN) problem is considered the bottleneck challenge that may face the self-interference cancellation (SIC) stage especially when orthogonal frequency division multiplexing (OFDM) transmission scheme is deployed. Phase noise degrades the SIC performance significantly, if not mitigated before or during the SIC technique. The presence of the oscillator phase noise has different impacts on the transmitted data symbol like common phase error (CPE) and inter-carrier interference (ICI). However, phase noise can be estimated and mitigated digitally in either time or frequency domain. Through this work, we propose a novel and simple time domain self-interference (SI) phase noise estimation and mitigation technique. The proposed algorithm is inspired from Wiener filtering in time domain. Simulation results show that the proposed algorithm has a superior performance than the already-existing time-domain or frequency domain PN mitigation solutions with a noticeable reduction in the computational complexity.
Adaptive Rejection of Periodic Disturbances Acting on Linear Systems with Unknown Dynamics
Venue: arXiv cs.SY 2016
Year: 2016

This paper proposes a novel direct adaptive control method for rejecting unknown deterministic disturbances and tracking unknown trajectories in systems with uncertain dynamics when the disturbances or trajectories are the summation of multiple sinusoids with known frequencies, such as periodic profiles or disturbances. The proposed algorithm does not require a model of the plant dynamics and does not use batches of measurements in the adaptation process. Moreover, it is applicable to both minimum and non-minimum phase plants. The algorithm is a "direct" adaptive method, in the sense that the identification of system parameters and the control design are performed simultaneously. In order to verify the effectiveness of the proposed method, an add-on controller is designed and implemented in the servo system of a hard disk drive to track unknown nano-scale periodic trajectories.
Variable-Length Hashing
Venue: arXiv cs.CV 2016
Year: 2016

Hashing has emerged as a popular technique for large-scale similarity search. Most learning-based hashing methods generate compact yet correlated hash codes. However, this redundancy is storage-inefficient. Hence we propose a lossless variable-length hashing (VLH) method that is both storage- and search-efficient. Storage efficiency is achieved by converting the fixed-length hash code into a variable-length code. Search efficiency is obtained by using a multiple hash table structure. With VLH, we are able to deliberately add redundancy into hash codes to improve retrieval performance with little sacrifice in storage efficiency or search complexity. In particular, we propose a block K-means hashing (B-KMH) method to obtain significantly improved retrieval performance with no increase in storage and marginal increase in computational cost.
Modified Group Delay Based MultiPitch Estimation in Co-Channel Speech
Venue: arXiv cs.SD 2016
Year: 2016

Phase processing has been replaced by group delay processing for the extraction of source and system parameters from speech. Group delay functions are ill-behaved when the transfer function has zeros that are close to unit circle in the z-domain. The modified group delay function addresses this problem and has been successfully used for formant and monopitch estimation. In this paper, modified group delay functions are used for multipitch estimation in concurrent speech. The power spectrum of the speech is first flattened in order to annihilate the system characteristics, while retaining the source characteristics. Group delay analysis on this flattened spectrum picks the predominant pitch in the first pass and a comb filter is used to filter out the estimated pitch along with its harmonics. The residual spectrum is again analyzed for the next candidate pitch estimate in the second pass. The final pitch trajectories of the constituent speech utterances are formed using pitch grouping and post processing techniques. The performance of the proposed algorithm was evaluated on standard datasets using two metrics; pitch accuracy and standard deviation of fine pitch error. Our results show that the proposed algorithm is a promising pitch detection method in multipitch environment for real speech recordings.