OpenRaiser/Intern-Atlas huggingface dataset:
Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion
Venue: arXiv cs.DS 2016
Year: 2016

In this paper, we consider the problem of scheduling jobs on parallel identical machines, where the processing times of jobs are uncertain: only interval bounds of processing times are known. The optimality criterion of a schedule is the total completion time. In order to cope with the uncertainty, we consider the maximum regret objective and we seek a schedule that performs well under all possible instantiations of processing times. Although the deterministic version of the considered problem is solvable in polynomial time, the minmax regret version is known to be weakly NP-hard even for a single machine, and strongly NP-hard for parallel unrelated machines. In this paper, we show that the problem is strongly NP-hard also in the case of parallel identical machines.
Densities in large permutations and parameter testing
Venue: arXiv cs.DM 2016
Year: 2016

A classical theorem of Erdos, Lovasz and Spencer asserts that the densities of connected subgraphs in large graphs are independent. We prove an analogue of this theorem for permutations and we then apply the methods used in the proof to give an example of a finitely approximable permutation parameter that is not finitely forcible. The latter answers a question posed by two of the authors and Moreira and Sampaio.
Safe Sequential Path Planning of Multi-Vehicle Systems via Double-Obstacle Hamilton-Jacobi-Isaacs Variational Inequality
Venue: arXiv cs.MA 2016
Year: 2016

We consider the problem of planning trajectories for a group of $N$ vehicles, each aiming to reach its own target set while avoiding danger zones of other vehicles. The analysis of problems like this is extremely important practically, especially given the growing interest in utilizing unmanned aircraft systems for civil purposes. The direct solution of this problem by solving a single-obstacle Hamilton-Jacobi-Isaacs (HJI) variational inequality (VI) is numerically intractable due to the exponential scaling of computation complexity with problem dimensionality. Furthermore, the single-obstacle HJI VI cannot directly handle situations in which vehicles do not have a common scheduled arrival time. Instead, we perform sequential path planning by considering vehicles in order of priority, modeling higher-priority vehicles as time-varying obstacles for lower-priority vehicles. To do this, we solve a double-obstacle HJI VI which allows us to obtain the reach-avoid set, defined as the set of states from which a vehicle can reach its target while staying within a time-varying state constraint set. From the solution of the double-obstacle HJI VI, we can also extract the latest start time and the optimal control for each vehicle. This is a first application of the double-obstacle HJI VI which can handle systems with time-varying dynamics, target sets, and state constraint sets, and results in computation complexity that scales linearly, as opposed to exponentially, with the number of vehicles in consideration.
On Discovering Co-Location Patterns in Datasets: A Case Study of Pollutants and Child Cancers
Venue: arXiv cs.DB 2016
Year: 2016

We intend to identify relationships between cancer cases and pollutant emissions and attempt to understand whether cancer in children is typically located together with some specific chemical combinations or is independent. Co-location pattern analysis seems to be the appropriate investigation to perform. Co-location mining is one of the tasks of spatial data mining which focuses on the detection of co-location patterns, the sets of spatial features frequently located in close proximity of each other. Most previous works are based on transaction-free apriori-like algorithms which are dependent on user-defined thresholds and are designed for boolean data points. Due to the absence of a clear notion of transactions, it is nontrivial to use association rule mining techniques to tackle the co-location mining problem. The approach we propose is based on a grid "transactionization" of the geographic space and is designed to mine datasets with extended spatial objects. Uncertainty of the feature presence in transactions is taken into account in our model. The statistical test is used instead of global thresholds to detect significant co-location patterns and rules. We evaluate our approach on synthetic and real datasets. This approach can be used by researchers looking for spatial associations between environmental and health factors. In addition, we explain the data modelling framework which is used on real datasets of pollutants (PRTR/NPRI) and childhood cancer cases.
Systemization of Pluggable Transports for Censorship Resistance
Venue: arXiv cs.CR 2016
Year: 2016

An increasing number of countries implement Internet censorship at different scales and for a variety of reasons. In particular, the link between the censored client and entry point to the uncensored network is a frequent target of censorship due to the ease with which a nation-state censor can control it. A number of censorship resistance systems have been developed thus far to help circumvent blocking on this link, which we refer to as link circumvention systems (LCs). The variety and profusion of attack vectors available to a censor has led to an arms race, leading to a dramatic speed of evolution of LCs. Despite their inherent complexity and the breadth of work in this area, there is no systematic way to evaluate link circumvention systems and compare them against each other. In this paper, we (i) sketch an attack model to comprehensively explore a censor's capabilities, (ii) present an abstract model of a LC, a system that helps a censored client communicate with a server over the Internet while resisting censorship, (iii) describe an evaluation stack that underscores a layered approach to evaluate LCs, and (iv) systemize and evaluate existing censorship resistance systems that provide link circumvention. We highlight open challenges in the evaluation and development of LCs and discuss possible mitigations.
Mobile Instant Video Clip Sharing: Modeling and Enhancing View Experience
Venue: arXiv cs.MM 2016
Year: 2016

With the rapid development of wireless networking and mobile devices, anytime and anywhere data access becomes readily available nowadays. Given the crowdsourced content capturing and sharing, the preferred content length becomes shorter and shorter, even for such multimedia data as video. A representative is Twitter's Vine service, which, mainly targeting mobile users, enables them to create ultra-short video clips and instantly post and share with their followers. In this paper, we present an initial study on this new generation of instant video clip sharing service enabled by mobile platforms and explore the potentials towards its further enhancement. We closely investigate its unique mobile interface, revealing the key differences between Vine-enabled anytime anywhere data access patterns and that of traditional counterparts. We then examine the scheduling policy to maximize the user watching experience as well as the efficiency on the monetary and energy costs. We show that the generic scheduling problem involves two subproblems, namely, pre-fetching scheduling and watch-time download scheduling, and develop effective solutions towards both of them. The superiority of our solution is demonstrated by extensive trace-driven simulations. To the best of our knowledge, this is the first work on modeling and optimizing the instant video clip sharing on mobile devices.
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
Venue: arXiv cs.CG 2016
Year: 2016

We study the family of intersection graphs of low density objects in low dimensional Euclidean space. This family is quite general, and includes planar graphs. We prove that such graphs have small separators. Next, we present efficient $(1+\varepsilon)$-approximation algorithms for these graphs, for Independent Set, Set Cover, and Dominating Set problems, among others. We also prove corresponding hardness of approximation for some of these optimization problems, providing a characterization of their intractability in terms of density.
HMOG: New Behavioral Biometric Features for Continuous Authentication of Smartphone Users
Venue: arXiv cs.CR 2016
Year: 2016

We introduce Hand Movement, Orientation, and Grasp (HMOG), a set of behavioral features to continuously authenticate smartphone users. HMOG features unobtrusively capture subtle micro-movement and orientation dynamics resulting from how a user grasps, holds, and taps on the smartphone. We evaluated authentication and biometric key generation (BKG) performance of HMOG features on data collected from 100 subjects typing on a virtual keyboard. Data was collected under two conditions: sitting and walking. We achieved authentication EERs as low as 7.16% (walking) and 10.05% (sitting) when we combined HMOG, tap, and keystroke features. We performed experiments to investigate why HMOG features perform well during walking. Our results suggest that this is due to the ability of HMOG features to capture distinctive body movements caused by walking, in addition to the hand-movement dynamics from taps. With BKG, we achieved EERs of 15.1% using HMOG combined with taps. In comparison, BKG using tap, key hold, and swipe features had EERs between 25.7% and 34.2%. We also analyzed the energy consumption of HMOG feature extraction and computation. Our analysis shows that HMOG features extracted at 16Hz sensor sampling rate incurred a minor overhead of 7.9% without sacrificing authentication accuracy. Two points distinguish our work from current literature: 1) we present the results of a comprehensive evaluation of three types of features (HMOG, keystroke, and tap) and their combinations under the same experimental conditions, and 2) we analyze the features from three perspectives (authentication, BKG, and energy consumption on smartphones).
Inference for Generalized Linear Models via Alternating Directions and Bethe Free Energy Minimization
Venue: arXiv cs.IT 2016
Year: 2016

Generalized Linear Models (GLMs), where a random vector $\mathbf{x}$ is observed through a noisy, possibly nonlinear, function of a linear transform $\mathbf{z}=\mathbf{Ax}$ arise in a range of applications in nonlinear filtering and regression. Approximate Message Passing (AMP) methods, based on loopy belief propagation, are a promising class of approaches for approximate inference in these models. AMP methods are computationally simple, general, and admit precise analyses with testable conditions for optimality for large i.i.d. transforms $\mathbf{A}$. However, the algorithms can easily diverge for general $\mathbf{A}$. This paper presents a convergent approach to the generalized AMP (GAMP) algorithm based on direct minimization of a large-system limit approximation of the Bethe Free Energy (LSL-BFE). The proposed method uses a double-loop procedure, where the outer loop successively linearizes the LSL-BFE and the inner loop minimizes the linearized LSL-BFE using the Alternating Direction Method of Multipliers (ADMM). The proposed method, called ADMM-GAMP, is similar in structure to the original GAMP method, but with an additional least-squares minimization. It is shown that for strictly convex, smooth penalties, ADMM-GAMP is guaranteed to converge to a local minima of the LSL-BFE, thus providing a convergent alternative to GAMP that is stable under arbitrary transforms. Simulations are also presented that demonstrate the robustness of the method for non-convex penalties as well.
Firedrake: automating the finite element method by composing abstractions
Venue: arXiv cs.MS 2016
Year: 2016

Firedrake is a new tool for automating the numerical solution of partial differential equations. Firedrake adopts the domain-specific language for the finite element method of the FEniCS project, but with a pure Python runtime-only implementation centred on the composition of several existing and new abstractions for particular aspects of scientific computing. The result is a more complete separation of concerns which eases the incorporation of separate contributions from computer scientists, numerical analysts and application specialists. These contributions may add functionality, or improve performance. Firedrake benefits from automatically applying new optimisations. This includes factorising mixed function spaces, transforming and vectorising inner loops, and intrinsically supporting block matrix operations. Importantly, Firedrake presents a simple public API for escaping the UFL abstraction. This allows users to implement common operations that fall outside pure variational formulations, such as flux-limiters.
Unit Vector Games
Venue: arXiv cs.GT 2016
Year: 2016

McLennan and Tourky (2010) showed that "imitation games" provide a new view of the computation of Nash equilibria of bimatrix games with the Lemke-Howson algorithm. In an imitation game, the payoff matrix of one of the players is the identity matrix. We study the more general "unit vector games", which are already known, where the payoff matrix of one player is composed of unit vectors. Our main application is a simplification of the construction by Savani and von Stengel (2006) of bimatrix games where two basic equilibrium-finding algorithms take exponentially many steps: the Lemke-Howson algorithm, and support enumeration.
Term satisfiability in FL$_\mathrm{ew}$-algebras
Venue: arXiv cs.LO 2016
Year: 2016

FL$_\mathrm{ew}$-algebras form the algebraic semantics of the full Lambek calculus with exchange and weakening. We investigate two relations, called satisfiability and positive satisfiability, between FL$_\mathrm{ew}$-terms and FL$_\mathrm{ew}$-algebras. For each FL$_\mathrm{ew}$-algebra, the sets of its satisfiable and positively satisfiable terms can be viewed as fragments of its existential theory; we identify and investigate the complements as fragments of its universal theory. We offer characterizations of those algebras that (positively) satisfy just those terms that are satisfiable in the two-element Boolean algebra providing its semantics to classical propositional logic. In case of positive satisfiability, these algebras are just the nontrivial weakly contractive FL$_\mathrm{ew}$-algebras. In case of satisfiability, we give a characterization by means of another property of the algebra, the existence of a two-element congruence. Further, we argue that (positive) satisfiability problems in FL$_\mathrm{ew}$-algebras are computationally hard. Some previous results in the area of term satisfiability in MV-algebras or BL-algebras are thus brought to a common footing with known facts on satisfiability in Heyting algebras.
Neural Implementation of Probabilistic Models of Cognition
Venue: arXiv cs.NE 2016
Year: 2016

Bayesian models of cognition hypothesize that human brains make sense of data by representing probability distributions and applying Bayes' rule to find the best explanation for available data. Understanding the neural mechanisms underlying probabilistic models remains important because Bayesian models provide a computational framework, rather than specifying mechanistic processes. Here, we propose a deterministic neural-network model which estimates and represents probability distributions from observable events --- a phenomenon related to the concept of probability matching. Our model learns to represent probabilities without receiving any representation of them from the external world, but rather by experiencing the occurrence patterns of individual events. Our neural implementation of probability matching is paired with a neural module applying Bayes' rule, forming a comprehensive neural scheme to simulate human Bayesian learning and inference. Our model also provides novel explanations of base-rate neglect, a notable deviation from Bayes.
Size-optimal Steiner points for Delaunay-refinement on curved surfaces
Venue: arXiv cs.CG 2016
Year: 2016

An extension of the restricted Delaunay-refinement algorithm for surface mesh generation is described, where a new point-placement scheme is introduced to improve element quality in the presence of mesh size constraints. Specifically, it is shown that the use of off-centre Steiner points, positioned on the faces of the associated Voronoi diagram, typically leads to significant improvements in the shape- and size-quality of the resulting surface tessellations. The new algorithm can be viewed as a Frontal-Delaunay approach -- a hybridisation of conventional Delaunay-refinement and advancing-front techniques in which new vertices are positioned to satisfy both element size and shape constraints. The performance of the new scheme is investigated experimentally via a series of comparative studies that contrast its performance with that of a typical Delaunay-refinement technique. It is shown that the new method inherits many of the best features of classical Delaunay-refinement and advancing-front type methods, leading to the construction of smooth, high quality surface triangulations with bounded radius-edge ratios and convergence guarantees. Experiments are conducted using a range of complex benchmarks, verifying the robustness and practical performance of the proposed scheme.
A High-Gain Nonlinear Observer with Limited Gain Power
Venue: arXiv cs.SY 2016
Year: 2016

In this note we deal with a new observer for nonlinear systems of dimension n in canonical observability form. We follow the standard high-gain paradigm, but instead of having an observer of dimension n with a gain that grows up to power n, we design an observer of dimension 2n-2 with a gain that grows up only to power 2.
Self-Stabilizing Repeated Balls-into-Bins
Venue: arXiv cs.DC 2016
Year: 2016

We study the following synchronous process that we call "repeated balls-into-bins". The process is started by assigning $n$ balls to $n$ bins in an arbitrary way. In every subsequent round, from each non-empty bin one ball is chosen according to some fixed strategy (random, FIFO, etc), and re-assigned to one of the $n$ bins uniformly at random. We define a configuration "legitimate" if its maximum load is $\mathcal{O}(\log n)$. We prove that, starting from any configuration, the process will converge to a legitimate configuration in linear time and then it will only take on legitimate configurations over a period of length bounded by any polynomial in $n$, with high probability (w.h.p.). This implies that the process is self-stabilizing and that every ball traverses all bins in $\mathcal{O}(n \log^2 n)$ rounds, w.h.p.
FASTA: A Generalized Implementation of Forward-Backward Splitting
Venue: arXiv cs.MS 2016
Year: 2016

This is a user manual for the software package FASTA.
Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial
Venue: arXiv cs.SC 2016
Year: 2016

The algorithms of Pan (1995) and(2002) approximate the roots of a complex univariate polynomial in nearly optimal arithmetic and Boolean time but require precision of computing that exceeds the degree of the polynomial. This causes numerical stability problems when the degree is large. We observe, however, that such a difficulty disappears at the initial stage of the algorithms, and in our present paper we extend this stage to root-finding within a nearly optimal arithmetic and Boolean complexity bounds provided that some mild initial isolation of the roots of the input polynomial has been ensured. Furthermore our algorithm is nearly optimal for the approximation of the roots isolated in a fixed disc, square or another region on the complex plane rather than all complex roots of a polynomial. Moreover the algorithm can be applied to a polynomial given by a black box for its evaluation (even if its coefficients are not known); it promises to be of practical value for polynomial root-finding and factorization, the latter task being of interest on its own right. We also provide a new support for a winding number algorithm, which enables extension of our progress to obtaining mild initial approximations to the roots. We conclude with summarizing our algorithms and their extension to the approximation of isolated multiple roots and root clusters.
Globally Optimal Cell Tracking using Integer Programming
Venue: arXiv cs.CV 2016
Year: 2016

We propose a novel approach to automatically tracking cell populations in time-lapse images. To account for cell occlusions and overlaps, we introduce a robust method that generates an over-complete set of competing detection hypotheses. We then perform detection and tracking simultaneously on these hypotheses by solving to optimality an integer program with only one type of flow variables. This eliminates the need for heuristics to handle missed detections due to occlusions and complex morphology. We demonstrate the effectiveness of our approach on a range of challenging sequences consisting of clumped cells and show that it outperforms state-of-the-art techniques.
First- and Second-Order Coding Theorems for Mixed Memoryless Channels with General Mixture
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the first- and second-order maximum achievable rates of codes with/without cost constraints for mixed {channels} whose channel law is characterized by a general mixture of (at most) uncountably many stationary and memoryless discrete channels. These channels are referred to as {mixed memoryless channels with general mixture} and include the class of mixed memoryless channels of finitely or countably memoryless channels as a special case. For mixed memoryless channels with general mixture, the first-order coding theorem which gives a formula for the $\varepsilon$-capacity is established, and then a direct part of the second-order coding theorem is provided. A subclass of mixed memoryless channels whose component channels can be ordered according to their capacity is introduced, and the first- and second-order coding theorems are established. It is shown that the established formulas reduce to several known formulas for restricted scenarios.
Improved Lower Bounds for Coded Caching
Venue: arXiv cs.IT 2016
Year: 2016

Content delivery networks often employ caching to reduce transmission rates from the central server to the end users. Recently, the technique of coded caching was introduced whereby coding in the caches and coded transmission signals from the central server are considered. Prior results in this area demonstrate that carefully designing the placement of content in the caches and designing appropriate coded delivery signals from the server allow for a system where the delivery rates can be significantly smaller than conventional schemes. However, matching upper and lower bounds on the transmission rate have not yet been obtained. In this work, we derive tighter lower bounds on the coded caching rate than were known previously. We demonstrate that this problem can equivalently be posed as a combinatorial problem of optimally labeling the leaves of a directed tree. Our proposed labeling algorithm allows for significantly improved lower bounds on the coded caching rate. Furthermore, we study certain structural properties of our algorithm that allow us to analytically quantify improvements on the rate lower bound for general values of the problem parameters. This allows us to obtain a multiplicative gap of at most four between the achievable rate and our lower bound.