OpenRaiser/Intern-Atlas huggingface dataset:
Parameterized and approximation complexity of the detection pair problem in graphs
Venue: arXiv cs.DS 2018
Year: 2018

We study the complexity of the problem DETECTION PAIR. A detection pair of a graph $G$ is a pair $(W,L)$ of sets of detectors with $W\subseteq V(G)$, the watchers, and $L\subseteq V(G)$, the listeners, such that for every pair $u,v$ of vertices that are not dominated by a watcher of $W$, there is a listener of $L$ whose distances to $u$ and to $v$ are different. The goal is to minimize $|W|+|L|$. This problem generalizes the two classic problems DOMINATING SET and METRIC DIMENSION, that correspond to the restrictions $L=\emptyset$ and $W=\emptyset$, respectively. DETECTION PAIR was recently introduced by Finbow, Hartnell and Young [A. S. Finbow, B. L. Hartnell and J. R. Young. The complexity of monitoring a network with both watchers and listeners. Manuscript, 2015], who proved it to be NP-complete on trees, a surprising result given that both DOMINATING SET and METRIC DIMENSION are known to be linear-time solvable on trees. It follows from an existing reduction by Hartung and Nichterlein for METRIC DIMENSION that even on bipartite subcubic graphs of arbitrarily large girth, DETECTION PAIR is NP-hard to approximate within a sub-logarithmic factor and W[2]-hard (when parameterized by solution size). We show, using a reduction to SET COVER, that DETECTION PAIR is approximable within a factor logarithmic in the number of vertices of the input graph. Our two main results are a linear-time $2$-approximation algorithm and an FPT algorithm for DETECTION PAIR on trees.
Incremental Maintenance of Maximal Cliques in a Dynamic Graph
Venue: arXiv cs.DS 2018
Year: 2018

We consider the maintenance of the set of all maximal cliques in a dynamic graph that is changing through the addition or deletion of edges. We present nearly tight bounds on the magnitude of change in the set of maximal cliques, as well as the first change-sensitive algorithms for clique maintenance, whose runtime is proportional to the magnitude of the change in the set of maximal cliques. We present experimental results showing these algorithms are efficient in practice and are faster than prior work by two to three orders of magnitude.
Fundamental Distortion Limits of Analog-to-Digital Compression
Venue: arXiv cs.IT 2018
Year: 2018

Representing a continuous-time signal by a set of samples is a classical problem in signal processing. We study this problem under the additional constraint that the samples are quantized or compressed in a lossy manner under a limited bitrate budget. To this end, we consider a combined sampling and source coding problem in which an analog stationary Gaussian signal is reconstructed from its encoded samples. These samples are obtained by a set of bounded linear functionals of the continuous-time path, with a limitation on the average number of samples obtained per unit time available in this setting. We provide a full characterization of the minimal distortion in terms of the sampling frequency, the bitrate, and the signal's spectrum. Assuming that the signal's energy is not uniformly distributed over its spectral support, we show that for each compression bitrate there exists a critical sampling frequency smaller than the Nyquist rate, such that the distortion in signal reconstruction when sampling at this frequency is minimal. Our results can be seen as an extension of the classical sampling theorem for bandlimited random processes in the sense that it describes the minimal amount of excess distortion in the reconstruction due to lossy compression of the samples, and provides the minimal sampling frequency required in order to achieve this distortion. Finally, we compare the fundamental limits in the combined source coding and sampling problem to the performance of pulse code modulation (PCM), where each sample is quantized by a scalar quantizer using a fixed number of bits.
Privacy, Secrecy, and Storage with Multiple Noisy Measurements of Identifiers
Venue: arXiv cs.IT 2018
Year: 2018

The key-leakage-storage region is derived for a generalization of a classic two-terminal key agreement model. The additions to the model are that the encoder observes a hidden, or noisy, version of the identifier, and that the encoder and decoder can perform multiple measurements. To illustrate the behavior of the region, the theory is applied to binary identifiers and noise modeled via binary symmetric channels. In particular, the key-leakage-storage region is simplified by applying Mrs. Gerber's lemma twice in different directions to a Markov chain. The growth in the region as the number of measurements increases is quantified. The amount by which the privacy-leakage rate reduces for a hidden identifier as compared to a noise-free (visible) identifier at the encoder is also given. If the encoder incorrectly models the source as visible, it is shown that substantial secrecy leakage may occur and the reliability of the reconstructed key might decrease.
Distributed Estimation of State and Parameters in Multi-Agent Cooperative Load Manipulation
Venue: arXiv cs.RO 2018
Year: 2018

We present two distributed methods for the estimation of the kinematic parameters, the dynamic parameters, and the kinematic state of an unknown planar body manipulated by a decentralized multi-agent system. The proposed approaches rely on the rigid body kinematics and dynamics, on nonlinear observation theory, and on consensus algorithms. The only three requirements are that each agent can exert a 2D wrench on the load, it can measure the velocity of its contact point, and that the communication graph is connected. Both theoretical nonlinear observability analysis and convergence proofs are provided. The first method assumes constant parameters while the second one can deal with time-varying parameters and can be applied in parallel to any task-oriented control law. For the cases in which a control law is not provided, we propose a distributed and safe control strategy satisfying the observability condition. The effectiveness and robustness of the estimation strategy is showcased by means of realistic MonteCarlo simulations.
Binarization Trees and Random Number Generation
Venue: arXiv cs.DS 2018
Year: 2018

An m-extracting procedure produces unbiased random bits from a loaded dice with m faces. A binarization takes inputs from an m-faced dice and produce bit sequences to be fed into a (binary) extracting procedure to obtain random bits. Thus, binary extracting procedures give rise to an m-extracting procedure via a binarization. An entropy- preserving binarization is to be called complete, and such a procedure has been proposed by Zhou and Bruck. We show that there exist complete binarizations in abundance as naturally arising from binary trees with m leaves. The well-known leaf entropy theorem and a closely related structure lemma play important roles in the arguments.
Distributed Constraint Optimization Problems and Applications: A Survey
Venue: arXiv cs.AI 2018
Year: 2018

The field of Multi-Agent System (MAS) is an active area of research within Artificial Intelligence, with an increasingly important impact in industrial and other real-world applications. Within a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as one of the prominent agent architectures to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have enabled them to support MAS in complex, real-time, and uncertain environments. This survey aims at providing an overview of the DCOP model, giving a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions, and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.
Implicit LOD using points ordering for processing and visualisation in Point Cloud Servers
Venue: arXiv cs.CG 2018
Year: 2018

Lidar datasets now commonly reach Billions of points and are very dense. Using these point cloud becomes challenging, as the high number of points is intractable for most applications and for visualisation.In this work we propose a new paradigm to easily get a portable geometric Level Of Details (LOD) inside a Point Cloud Server.The main idea is to not store the LOD information in an external additional file, but instead to store it implicitly by exploiting the order of the points.The point cloud is divided into groups (patches). These patches are ordered so that their order gradually provides more and more details on the patch. We demonstrate the interest of our method with several classical uses of LOD, such as visualisation of massive point cloud, algorithm acceleration, fast density peak detection and correction.
Equity forecast: Predicting long term stock price movement using machine learning
Venue: arXiv cs.LG 2018
Year: 2018

Long term investment is one of the major investment strategies. However, calculating intrinsic value of some company and evaluating shares for long term investment is not easy, since analyst have to care about a large number of financial indicators and evaluate them in a right manner. So far, little help in predicting the direction of the company value over the longer period of time has been provided from the machines. In this paper we present a machine learning aided approach to evaluate the equity's future price over the long time. Our method is able to correctly predict whether some company's value will be 10% higher or not over the period of one year in 76.5% of cases.
Hand Segmentation for Hand-Object Interaction from Depth map
Venue: arXiv cs.CV 2018
Year: 2018

Hand segmentation for hand-object interaction is a necessary preprocessing step in many applications such as augmented reality, medical application, and human-robot interaction. However, typical methods are based on color information which is not robust to objects with skin color, skin pigment difference, and light condition variations. Thus, we propose hand segmentation method for hand-object interaction using only a depth map. It is challenging because of the small depth difference between a hand and objects during an interaction. To overcome this challenge, we propose the two-stage random decision forest (RDF) method consisting of detecting hands and segmenting hands. To validate the proposed method, we demonstrate results on the publicly available dataset of hand segmentation for hand-object interaction. The proposed method achieves high accuracy in short processing time comparing to the other state-of-the-art methods.
Microprocessor Optimizations for the Internet of Things: A Survey
Venue: arXiv cs.OH 2018
Year: 2018

The Internet of Things (IoT) refers to a pervasive presence of interconnected and uniquely identifiable physical devices. These devices' goal is to gather data and drive actions in order to improve productivity, and ultimately reduce or eliminate reliance on human intervention for data acquisition, interpretation, and use. The proliferation of these connected low-power devices will result in a data explosion that will significantly increase data transmission costs with respect to energy consumption and latency. Edge computing reduces these costs by performing computations at the edge nodes, prior to data transmission, to interpret and/or utilize the data. While much research has focused on the IoT's connected nature and communication challenges, the challenges of IoT embedded computing with respect to device microprocessors has received much less attention. This paper explores IoT applications' execution characteristics from a microarchitectural perspective and the microarchitectural characteristics that will enable efficient and effective edge computing. To tractably represent a wide variety of next-generation IoT applications, we present a broad IoT application classification methodology based on application functions, to enable quicker workload characterizations for IoT microprocessors. We then survey and discuss potential microarchitectural optimizations and computing paradigms that will enable the design of right-provisioned microprocessors that are efficient, configurable, extensible, and scalable. This paper provides a foundation for the analysis and design of a diverse set of microprocessor architectures for next-generation IoT devices.
Online but Accurate Inference for Latent Variable Models with Local Gibbs Sampling
Venue: arXiv cs.LG 2018
Year: 2018

We study parameter inference in large-scale latent variable models. We first propose an unified treatment of online inference for latent variable models from a non-canonical exponential family, and draw explicit links between several previously proposed frequentist or Bayesian methods. We then propose a novel inference method for the frequentist estimation of parameters, that adapts MCMC methods to online inference of latent variable models with the proper use of local Gibbs sampling. Then, for latent Dirich-let allocation,we provide an extensive set of experiments and comparisons with existing work, where our new approach outperforms all previously proposed methods. In particular, using Gibbs sampling for latent variable inference is superior to variational inference in terms of test log-likelihoods. Moreover, Bayesian inference through variational methods perform poorly, sometimes leading to worse fits with latent variables of higher dimensionality.
A Signaling Game Approach to Databases Querying and Interaction
Venue: arXiv cs.DB 2018
Year: 2018

As most users do not precisely know the structure and/or the content of databases, their queries do not exactly reflect their information needs. The database management systems (DBMS) may interact with users and use their feedback on the returned results to learn the information needs behind their queries. Current query interfaces assume that users do not learn and modify the way way they express their information needs in form of queries during their interaction with the DBMS. Using a real-world interaction workload, we show that users learn and modify how to express their information needs during their interactions with the DBMS and their learning is accurately modeled by a well-known reinforcement learning mechanism. As current data interaction systems assume that users do not modify their strategies, they cannot discover the information needs behind users' queries effectively. We model the interaction between users and DBMS as a game with identical interest between two rational agents whose goal is to establish a common language for representing information needs in form of queries. We propose a reinforcement learning method that learns and answers the information needs behind queries and adapts to the changes in users' strategies and prove that it improves the effectiveness of answering queries stochastically speaking. We propose two efficient implementation of this method over large relational databases. Our extensive empirical studies over real-world query workloads indicate that our algorithms are efficient and effective.
A Novel Method for the Extrinsic Calibration of a 2D Laser Rangefinder and a Camera
Venue: arXiv cs.CV 2018
Year: 2018

We present a novel method for extrinsically calibrating a camera and a 2D Laser Rangefinder (LRF) whose beams are invisible from the camera image. We show that point-to-plane constraints from a single observation of a V-shaped calibration pattern composed of two non-coplanar triangles suffice to uniquely constrain the relative pose between two sensors. Next, we present an approach to obtain analytical solutions using point-to-plane constraints from single or multiple observations. Along the way, we also show that previous solutions, in contrast to our method, have inherent ambiguities and therefore must rely on a good initial estimate. Real and synthetic experiments validate our method and show that it achieves better accuracy than previous methods.
Safety Control of Monotone Systems with Bounded Uncertainties
Venue: arXiv cs.SY 2018
Year: 2018

Monotone systems, also known as order-preserving or cooperative systems, are prevalent in models of engineering applications such as transportation and biological networks. In this paper, we investigate the problem of finding a control strategy for a discrete time monotone system with bounded uncertainties such that the evolution of the system is guaranteed to be confined to a safe set in the state space for all times. By exploiting monotonicity, we propose an approach to this problem which is based on constraint programming. We find control strategies that are based on repetitions of finite sequences of control actions. We show that, under assumptions made in the paper, safety control of monotone systems does not require state measurement. We demonstrate the results on a signalized urban traffic network, where the safety objective is to keep the traffic flow free of congestion.
Moving horizon estimation for discrete-time linear systems with binary sensors: algorithms and stability results
Venue: arXiv cs.SY 2018
Year: 2018

The paper addresses state estimation for linear discrete-time systems with binary (threshold) measurements. A Moving Horizon Estimation (MHE) approach is followed and different estimators, characterized by two different choices of the cost function to be minimized and/or by the possible inclusion of constraints, are proposed. Specifically, the cost function is either quadratic, when only the information pertaining to the threshold-crossing instants is exploited, or piece-wise quadratic, when all the available binary measurements are taken into account. Stability results are provided for the proposed MHE algorithms in the presence of unknown but bounded disturbances and measurement noises. Performance of the proposed techniques is also assessed by means of a simulation example.
Enhanced Approximation of Labeled Multi-object Density based on Correlation Analysis
Venue: arXiv cs.SY 2018
Year: 2018

Multi-object density is a fundamental descriptor of a point process and has ability to describe the randomness of number and values of objects, as well as the statistical correlation between objects. Due to its comprehensive nature, it usually has a complicate mathematical structure making the set integral suffering from the curse of dimension and the combinatorial nature of the problem. Hence, the approximation of multi-object density is a key research theme in point process theory or finite set statistics (FISST). Conventional approaches usually discard part or all of statistical correlation mechanically in return for computational efficiency, without considering the real situation of correlation between objects. In this paper, we propose an enhanced approximation of labeled multi-object (LMO) density which evaluates the correlation between objects adaptively and factorizes the LMO density into densities of several independent subsets according to the correlation analysis. Besides, to get a tractable factorization of LMO density, we derive the set marginal density of any subset of the universal labeled RFS, the generalized labeled multi-Bernoulli (GLMB) RFS family and its subclasses. The proposed method takes into account the simplification of the complicate structure of LMO density and the reservation of necessary correlation at the same time.
A Unified Theory of Multiple-Access and Interference Channels via Approximate Capacity Regions for the MAC-IC-MAC
Venue: arXiv cs.IT 2018
Year: 2018

Approximate capacity regions are established for a class of interfering multiple access channels consisting of two multiple-access channels (MACs), each with an arbitrary number of transmitters, with one transmitter in each MAC causing interference to the receiver of the other MAC, a channel we refer to henceforth as the MAC-IC-MAC. For the discrete memoryless (DM) MAC-IC-MAC, two inner bounds are obtained that are generalizations of prior inner bounds for the two-user DM interference channel (IC) due to Chong {\em et al}. For the semi-deterministic MAC-IC-MAC, it is shown that single-user coding at the non-interfering transmitters and superposition coding at the interfering transmitter of each MAC achieves a rate region that is within a quantifiable gap of the capacity region, thereby extending such a result for the two-user semi-deterministic IC by Telatar and Tse. For the Gaussian MAC-IC-MAC, an approximate capacity region that is within a constant gap of the capacity region is obtained, generalizing such a result for the two-user Gaussian IC by Etkin {\em et al}. Contrary to the aforementioned approximate capacity results for the two-user IC whose achievability requires the union of all admissible input distributions, our gap results on the semi-deterministic and the Gaussian MAC-IC-MAC are achievable by only a subset and one of all admissible coding distributions, respectively. The symmetric generalized degrees of freedom (GDoF) of the symmetric Gaussian MAC-IC-MAC with more than one user per cell, which is a function of the interference strength (the ratio of INR to SNR at high SNR, both expressed in dB) and the numbers of users in each cell, is V-shaped with flat shoulders. ...
DS-MLR: Exploiting Double Separability for Scaling up Distributed Multinomial Logistic Regression
Venue: arXiv cs.LG 2018
Year: 2018

Scaling multinomial logistic regression to datasets with very large number of data points and classes is challenging. This is primarily because one needs to compute the log-partition function on every data point. This makes distributing the computation hard. In this paper, we present a distributed stochastic gradient descent based optimization method (DS-MLR) for scaling up multinomial logistic regression problems to massive scale datasets without hitting any storage constraints on the data and model parameters. Our algorithm exploits double-separability, an attractive property that allows us to achieve both data as well as model parallelism simultaneously. In addition, we introduce a non-blocking and asynchronous variant of our algorithm that avoids bulk-synchronization. We demonstrate the versatility of DS-MLR to various scenarios in data and model parallelism, through an extensive empirical study using several real-world datasets. In particular, we demonstrate the scalability of DS-MLR by solving an extreme multi-class classification problem on the Reddit dataset (159 GB data, 358 GB parameters) where, to the best of our knowledge, no other existing methods apply.
(Almost) Efficient Mechanisms for Bilateral Trading
Venue: arXiv cs.GT 2018
Year: 2018

We study the bilateral trade problem: one seller, one buyer and a single, indivisible item for sale. It is well known that there is no fully-efficient and incentive compatible mechanism for this problem that maintains a balanced budget. We design simple and robust mechanisms that obtain approximate efficiency with these properties. We show that even minimal use of statistical data can yield good approximation results. Finally, we demonstrate how a mechanism for this simple bilateral-trade problem can be used as a "black-box" for constructing mechanisms in more general environments.