OpenRaiser/Intern-Atlas huggingface dataset:
Approximation Ratio of LD Algorithm for Multi-Processor Scheduling and the Coffman-Sethi Conjecture
Venue: arXiv cs.DS 2015
Year: 2015

Coffman and Sethi proposed a heuristic algorithm, called LD, for multi-processor scheduling, to minimize makespan over flowtime-optimal schedules. LD algorithm is a natural extension of a very well-known list scheduling algorithm, Longest Processing Time (LPT) list scheduling, to our bicriteria scheduling problem. Moreover, in 1976, Coffman and Sethi conjectured that LD algorithm has precisely the following worst-case performance bound: $\frac{5}{4} - \frac{3}{4(4m-1)}$, where m is the number of machines. In this paper, utilizing some recent work by the authors and Huang, from 2013, which exposed some very strong combinatorial properties of various presumed minimal counterexamples to the conjecture, we provide a proof of this conjecture. The problem and the LD algorithm have connections to other fundamental problems (such as the assembly line-balancing problem) and to other algorithms.
Implementation of BT-trees
Venue: arXiv cs.DS 2015
Year: 2015

This document presents the full implementation details of BT-trees, a highly efficient ordered map, and an evaluation which compares BT-trees with unordered maps. BT- trees are often much faster than other ordered maps, and have comparable performance to unordered map implementations. However, in benchmarks which favor unordered maps, BT-trees are not faster than the fastest unordered map implementations we know of.
Amplitude-Aided 1-Bit Compressive Sensing Over Noisy Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

Abstract-One-bit compressive sensing (CS) is known to be particularly suited for resource-constrained wireless sensor networks (WSNs). In this paper, we consider 1-bit CS over noisy WSNs subject to channel-induced bit flipping errors, and propose an amplitude-aided signal reconstruction scheme, by which (i) the representation points of local binary quantizers are designed to minimize the loss of data fidelity caused by local sensing noise, quantization, and bit sign flipping, and (ii) the fusion center adopts the conventional minimization method for sparse signal recovery using the decoded and de-mapped binary data. The representation points of binary quantizers are designed by minimizing the mean square error (MSE) of the net data mismatch, taking into account the distributions of the nonzero signal entries, local sensing noise, quantization error, and bit flipping; a simple closed-form solution is then obtained. Numerical simulations show that our method improves the estimation accuracy when SNR is low or the number of sensors is small, as compared to state-of-the-art 1-bit CS algorithms relying solely on the sign message for signal recovery.
Controllability of networked MIMO systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we consider the state controllability of networked systems, where the network topology is directed and weighted and the nodes are higher-dimensional linear time-invariant (LTI) dynamical systems. We investigate how the network topology, the node-system dynamics, the external control inputs, and the inner interactions affect the controllability of a networked system, and show that for a general networked multi-input/multi-output (MIMO) system: 1) the controllability of the overall network is an integrated result of the aforementioned relevant factors, which cannot be decoupled into the controllability of individual node-systems and the properties solely determined by the network topology, quite different from the familiar notion of consensus or formation controllability; 2) if the network topology is uncontrollable by external inputs, then the networked system with identical nodes will be uncontrollable, even if it is structurally controllable; 3) with a controllable network topology, controllability and observability of the nodes together are necessary for the controllability of the networked systems under some mild conditions, but nevertheless they are not sufficient. For a networked system with single-input/single-output (SISO) LTI nodes, we present precise necessary and sufficient conditions for the controllability of a general network topology.
Understanding Graph Structure of Wikipedia for Query Expansion
Venue: arXiv cs.IR 2015
Year: 2015

Knowledge bases are very good sources for knowledge extraction, the ability to create knowledge from structured and unstructured sources and use it to improve automatic processes as query expansion. However, extracting knowledge from unstructured sources is still an open challenge. In this respect, understanding the structure of knowledge bases can provide significant benefits for the effectiveness of such purpose. In particular, Wikipedia has become a very popular knowledge base in the last years because it is a general encyclopedia that has a large amount of information and thus, covers a large amount of different topics. In this piece of work, we analyze how articles and categories of Wikipedia relate to each other and how these relationships can support a query expansion technique. In particular, we show that the structures in the form of dense cycles with a minimum amount of categories tend to identify the most relevant information.
On the Optimality of Secure Network Coding
Venue: arXiv cs.IT 2015
Year: 2015

In network communications, information transmission often encounters wiretapping attacks. Secure network coding is introduced to prevent information from being leaked to adversaries. The investigation of performance bounds on the numbers of source symbols and random symbols are two fundamental research problems. For an important case that each wiretap-set with cardinality not larger than $r$, Cai and Yeung proposed a coding scheme, which is optimal in the senses of maximizing the number of source symbols and at the same time minimizing the number of random symbols. In this letter, we further study achievable lower bound on the number of random key and show that it just depends on the security constraint, and particularly, is independent to the information amount for transmission. This implies that when the number of transmitted source message changes, we can't reduce the number of random key to keep the same security level. We further give an intuitive interpretation on our result. In addition, a similar construction of secure linear network codes is proposed, which achieves this lower bound on the number of random key no matter how much information is transmitted. At last, we also extend our result to imperfect security case.
Mining Scientific Papers for Bibliometrics: a (very) Brief Survey of Methods and Tools
Venue: arXiv cs.DL 2015
Year: 2015

The Open Access movement in scientific publishing and search engines like Google Scholar have made scientific articles more broadly accessible. During the last decade, the availability of scientific papers in full text has become more and more widespread thanks to the growing number of publications on online platforms such as ArXiv and CiteSeer. The efforts to provide articles in machine-readable formats and the rise of Open Access publishing have resulted in a number of standardized formats for scientific papers (such as NLM-JATS, TEI, DocBook). Our aim is to stimulate research at the intersection of Bibliometrics and Computational Linguistics in order to study the ways Bibliometrics can benefit from large-scale text analytics and sense mining of scientific papers, thus exploring the interdisciplinarity of Bibliometrics and Natural Language Processing.
Fast Differentially Private Matrix Factorization
Venue: arXiv cs.LG 2015
Year: 2015

Differentially private collaborative filtering is a challenging task, both in terms of accuracy and speed. We present a simple algorithm that is provably differentially private, while offering good performance, using a novel connection of differential privacy to Bayesian posterior sampling via Stochastic Gradient Langevin Dynamics. Due to its simplicity the algorithm lends itself to efficient implementation. By careful systems design and by exploiting the power law behavior of the data to maximize CPU cache bandwidth we are able to generate 1024 dimensional models at a rate of 8.5 million recommendations per second on a single PC.
Retaining Experience and Growing Solutions
Venue: arXiv cs.NE 2015
Year: 2015

Generally, when genetic programming (GP) is used for function synthesis any valuable experience gained by the system is lost from one problem to the next, even when the problems are closely related. With the aim of developing a system which retains beneficial experience from problem to problem, this paper introduces the novel Node-by-Node Growth Solver (NNGS) algorithm which features a component, called the controller, which can be adapted and improved for use across a set of related problems. NNGS grows a single solution tree from root to leaves. Using semantic backpropagation and acting locally on each node in turn, the algorithm employs the controller to assign subsequent child nodes until a fully formed solution is generated. The aim of this paper is to pave a path towards the use of a neural network as the controller component and also, separately, towards the use of meta-GP as a mechanism for improving the controller component. A proof-of-concept controller is discussed which demonstrates the success and potential of the NNGS algorithm. In this case, the controller constitutes a set of hand written rules which can be used to deterministically and greedily solve standard Boolean function synthesis benchmarks. Even before employing machine learning to improve the controller, the algorithm vastly outperforms other well known recent algorithms on run times, maintains comparable solution sizes, and has a 100% success rate on all Boolean function synthesis benchmarks tested so far.
Best-First and Depth-First Minimax Search in Practice
Venue: arXiv cs.AI 2015
Year: 2015

Most practitioners use a variant of the Alpha-Beta algorithm, a simple depth-first pro- cedure, for searching minimax trees. SSS*, with its best-first search strategy, reportedly offers the potential for more efficient search. However, the complex formulation of the al- gorithm and its alleged excessive memory requirements preclude its use in practice. For two decades, the search efficiency of "smart" best-first SSS* has cast doubt on the effectiveness of "dumb" depth-first Alpha-Beta. This paper presents a simple framework for calling Alpha-Beta that allows us to create a variety of algorithms, including SSS* and DUAL*. In effect, we formulate a best-first algorithm using depth-first search. Expressed in this framework SSS* is just a special case of Alpha-Beta, solving all of the perceived drawbacks of the algorithm. In practice, Alpha-Beta variants typically evaluate less nodes than SSS*. A new instance of this framework, MTD(f), out-performs SSS* and NegaScout, the Alpha-Beta variant of choice by practitioners.
Structure Formation in Large Theories
Venue: arXiv cs.LO 2015
Year: 2015

Structuring theories is one of the main approaches to reduce the combinatorial explosion associated with reasoning and exploring large theories. In the past we developed the notion of development graphs as a means to represent and maintain structured theories. In this paper we present a methodology and a resulting implementation to reveal the hidden structure of flat theories by transforming them into detailed development graphs. We review our approach using plain TSTP-representations of MIZAR articles obtaining more structured and also more concise theories.
Blind Compressive Sensing Framework for Collaborative Filtering
Venue: arXiv cs.IR 2015
Year: 2015

Existing works based on latent factor models have focused on representing the rating matrix as a product of user and item latent factor matrices, both being dense. Latent (factor) vectors define the degree to which a trait is possessed by an item or the affinity of user towards that trait. A dense user matrix is a reasonable assumption as each user will like/dislike a trait to certain extent. However, any item will possess only a few of the attributes and never all. Hence, the item matrix should ideally have a sparse structure rather than a dense one as formulated in earlier works. Therefore we propose to factor the ratings matrix into a dense user matrix and a sparse item matrix which leads us to the Blind Compressed Sensing (BCS) framework. We derive an efficient algorithm for solving the BCS problem based on Majorization Minimization (MM) technique. Our proposed approach is able to achieve significantly higher accuracy and shorter run times as compared to existing approaches.
A Survey of Predictive Modelling under Imbalanced Distributions
Venue: arXiv cs.LG 2015
Year: 2015

Many real world data mining applications involve obtaining predictive models using data sets with strongly imbalanced distributions of the target variable. Frequently, the least common values of this target variable are associated with events that are highly relevant for end users (e.g. fraud detection, unusual returns on stock markets, anticipation of catastrophes, etc.). Moreover, the events may have different costs and benefits, which when associated with the rarity of some of them on the available training data creates serious problems to predictive modelling techniques. This paper presents a survey of existing techniques for handling these important applications of predictive analytics. Although most of the existing work addresses classification tasks (nominal target variables), we also describe methods designed to handle similar problems within regression tasks (numeric target variables). In this survey we discuss the main challenges raised by imbalanced distributions, describe the main approaches to these problems, propose a taxonomy of these methods and refer to some related problems within predictive modelling.
Divisibility patterns of natural numbers on a complex network
Venue: arXiv cs.SI 2015
Year: 2015

Investigation of divisibility properties of natural numbers is one of the most important themes in the theory of numbers. Various tools have been developed over the centuries to discover and study the various patterns in the sequence of natural numbers in the context of divisibility. In the present paper, we study the divisibility of natural numbers using the framework of a growing complex network. In particular, using tools from the field of statistical inference, we show that the network is scale-free but has a non-stationary degree distribution. Along with this, we report a new kind of similarity pattern for the local clustering, which we call "stretching similarity", in this network. We also show that the various characteristics like average degree, global clustering coefficient and assortativity coefficient of the network vary smoothly with the size of the network. Using analytical arguments we estimate the asymptotic behavior of global clustering and average degree which is validated using numerical analysis.
Coordination protocol for inter-operator spectrum sharing in co-primary 5G small cell networks
Venue: arXiv cs.NI 2015
Year: 2015

We consider spectrum sharing between a limited set of operators having similar rights for accessing spectrum. A coordination protocol acting on the level of the Radio Access Network (RAN) is designed. The protocol is non-cooperative, but assumes an agreement to a set of negotiation rules. The signaling overhead is low, and knowledge of competitor's channel state information is not assumed. No monetary transactions are involved; instead, spectrum sharing is based on a RAN-internal virtual currency. The protocol is applicable in a scenario of mutual renting and when the operators form a spectrum pool. The protocol is reactive to variations in interference and load of the operators, and shows gains in a simulated small cell scenario compared to not using any coordination protocol.
Deep Learning for Medical Image Segmentation
Venue: arXiv cs.LG 2015
Year: 2015

This report provides an overview of the current state of the art deep learning architectures and optimisation techniques, and uses the ADNI hippocampus MRI dataset as an example to compare the effectiveness and efficiency of different convolutional architectures on the task of patch-based 3-dimensional hippocampal segmentation, which is important in the diagnosis of Alzheimer's Disease. We found that a slightly unconventional "stacked 2D" approach provides much better classification performance than simple 2D patches without requiring significantly more computational power. We also examined the popular "tri-planar" approach used in some recently published studies, and found that it provides much better results than the 2D approaches, but also with a moderate increase in computational power requirement. Finally, we evaluated a full 3D convolutional architecture, and found that it provides marginally better results than the tri-planar approach, but at the cost of a very significant increase in computational power requirement.
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
Venue: arXiv cs.DS 2015
Year: 2015

This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using $\tilde{O}(n^{4/5})$ space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a $\mathrm{polylog}(n)$ approximation for general graphs using $\mathrm{polylog}(n)$ space in random order streams, respectively. In addition, we give a space lower bound of $Ω(n^{1-\varepsilon})$ for any randomized algorithm estimating the size of a maximum matching up to a $1+O(\varepsilon)$ factor for adversarial streams.
Short Portfolio Training for CSP Solving
Venue: arXiv cs.AI 2015
Year: 2015

Many different approaches for solving Constraint Satisfaction Problems (CSPs) and related Constraint Optimization Problems (COPs) exist. However, there is no single solver (nor approach) that performs well on all classes of problems and many portfolio approaches for selecting a suitable solver based on simple syntactic features of the input CSP instance have been developed. In this paper we first present a simple portfolio method for CSP based on k-nearest neighbors method. Then, we propose a new way of using portfolio systems --- training them shortly in the exploitation time, specifically for the set of instances to be solved and using them on that set. Thorough evaluation has been performed and has shown that the approach yields good results. We evaluated several machine learning techniques for our portfolio. Due to its simplicity and efficiency, the selected k-nearest neighbors method is especially suited for our short training approach and it also yields the best results among the tested methods. We also confirm that our approach yields good results on SAT domain.
Web ontology representation and reasoning via fragments of set theory
Venue: arXiv cs.LO 2015
Year: 2015

In this paper we use results from Computable Set Theory as a means to represent and reason about description logics and rule languages for the semantic web. Specifically, we introduce the description logic $\mathcal{DL}\langle 4LQS^R\rangle(\D)$--admitting features such as min/max cardinality constructs on the left-hand/right-hand side of inclusion axioms, role chain axioms, and datatypes--which turns out to be quite expressive if compared with $\mathcal{SROIQ}(\D)$, the description logic underpinning the Web Ontology Language OWL. Then we show that the consistency problem for $\mathcal{DL}\langle 4LQS^R\rangle(\D)$-knowledge bases is decidable by reducing it, through a suitable translation process, to the satisfiability problem of the stratified fragment $4LQS^R$ of set theory, involving variables of four sorts and a restricted form of quantification. We prove also that, under suitable not very restrictive constraints, the consistency problem for $\mathcal{DL}\langle 4LQS^R\rangle(\D)$-knowledge bases is \textbf{NP}-complete. Finally, we provide a $4LQS^R$-translation of rules belonging to the Semantic Web Rule Language (SWRL).
Distributed Optimization of Multi-Cell Uplink Co-operation with Backhaul Constraints
Venue: arXiv cs.SY 2015
Year: 2015

We address the problem of uplink co-operative reception with constraints on both backhaul bandwidth and the receiver aperture, or number of antenna signals that can be processed. The problem is cast as a network utility (weighted sum rate) maximization subject to computational complexity and architectural bandwidth sharing constraints. We show that a relaxed version of the problem is convex, and can be solved via a dual-decomposition. The proposed solution is distributed in that each cell broadcasts a set of {\em demand prices} based on the data sharing requests they receive. Given the demand prices, the algorithm determines an antenna/cell ordering and antenna-selection for each scheduled user in a cell. This algorithm, referred to as {\em LiquidMAAS}, iterates between the preceding two steps. Simulations of realistic network scenarios show that the algorithm exhibits fast convergence even for systems with large number of cells.
MegaFace: A Million Faces for Recognition at Scale
Venue: arXiv cs.CV 2015
Year: 2015

Recent face recognition experiments on the LFW benchmark show that face recognition is performing stunningly well, surpassing human recognition rates. In this paper, we study face recognition at scale. Specifically, we have collected from Flickr a \textbf{Million} faces and evaluated state of the art face recognition algorithms on this dataset. We found that the performance of algorithms varies--while all perform great on LFW, once evaluated at scale recognition rates drop drastically for most algorithms. Interestingly, deep learning based approach by \cite{schroff2015facenet} performs much better, but still gets less robust at scale. We consider both verification and identification problems, and evaluate how pose affects recognition at scale. Moreover, we ran an extensive human study on Mechanical Turk to evaluate human recognition at scale, and report results. All the photos are creative commons photos and is released at \small{\url{http://megaface.cs.washington.edu/}} for research and further experiments.
Construction of Subspace Codes through Linkage
Venue: arXiv cs.IT 2015
Year: 2015

A construction is presented that allows to produce subspace codes of long length using subspace codes of shorter length in combination with a rank metric code. The subspace distance of the resulting code, called linkage code, is as good as the minimum subspace distance of the constituent codes. As a special application, the construction of the best known partial spreads is reproduced. Finally, for a special case of linkage, a decoding algorithm is presented which amounts to decoding with respect to the smaller constituent codes and which can be parallelized.