OpenRaiser/Intern-Atlas huggingface dataset:
Topological Drawings of Complete Bipartite Graphs
Venue: arXiv cs.CG 2017
Year: 2017

Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. Topological drawings of complete graphs and of complete bipartite graphs have been studied extensively in the context of crossing number problems. We consider a natural class of simple topological drawings of complete bipartite graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary of the drawing. We investigate the combinatorics of such drawings. For this purpose, we define combinatorial encodings of the drawings by enumerating the distinct drawings of subgraphs isomorphic to $K_{2,2}$ and $K_{3,2}$, and investigate the constraints they must satisfy. We prove that a drawing of $K_{k,n}$ exists if and only if some simple local conditions are satisfied by the encodings. This directly yields a polynomial-time algorithm for deciding the existence of such a drawing given the encoding. We show the encoding is equivalent to specifying which pairs of edges cross, yielding a similar polynomial-time algorithm for the realizability of abstract topological graphs. We also completely characterize and enumerate such drawings of $K_{k,n}$ in which the order of the edges around each vertex is the same for vertices on the same side of the bipartition. Finally, we investigate drawings of $K_{k,n}$ using straight lines and pseudolines, and consider the complexity of the corresponding realizability problems.
Delay Performance of Wireless Communications with Imperfect CSI and Finite Length Coding
Venue: arXiv cs.IT 2017
Year: 2017

With the rise of critical machine-to-machine applications, next generation wireless communication systems must be designed with strict constraints on the latency and reliability. A key question in this context relates to channel state estimation, which allows the transmitter to adapt the code rate to the channel. In this work, we characterize the trade-off between the estimation sequence length and data codeword length: shorter channel estimation leaves more time for the actual payload transmission but reduces the estimation accuracy and causes more decoding errors. Using lower coding rates can mitigate this effect, but may result in a higher backlog of data at the transmitter. We analyze this trade-off using queueing analysis on top of accurate models of the physical layer, which also account for the finite blocklength of the channel code. Based on a novel closed-form approximation for the error probability given the rate, we show that finding the optimal rate adaptation strategy becomes a convex problem. The optimal rate adaptation strategy and the optimal training sequence length, which both depend on the latency and reliability constraints of the application, can improve the delay performance by an order of magnitude, compared to suboptimal strategies that do not consider those constraints.
Spatio-Colour Asplünd 's Metric and Logarithmic Image Processing for Colour Images (LIPC)
Venue: arXiv cs.CV 2017
Year: 2017

Asplünd 's metric, which is useful for pattern matching, consists in a double-sided probing, i.e. the over-graph and the sub-graph of a function are probed jointly. This paper extends the Asplünd 's metric we previously defined for colour and multivariate images using a marginal approach (i.e. component by component) to the first spatio-colour Asplünd 's metric based on the vectorial colour LIP model (LIPC). LIPC is a non-linear model with operations between colour images which are consistent with the human visual system. The defined colour metric is insensitive to lighting variations and a variant which is robust to noise is used for colour pattern matching.
Detectability thresholds of general modular graphs
Venue: arXiv cs.SI 2017
Year: 2017

We investigate the detectability thresholds of various modular structures in the stochastic block model. Our analysis reveals how the detectability threshold is related to the details of the modular pattern, including the hierarchy of the clusters. We show that certain planted structures are impossible to infer regardless of their fuzziness.
Subcomputable Schnorr Randomness
Venue: arXiv cs.LO 2017
Year: 2017

The notion of Schnorr randomness refers to computable reals or computable functions. We propose a version of Schnorr randomness for subcomputable classes and characterize it in different ways: by Martin Löf tests, martingales or measure computable machines.
Spatially Correlated Content Caching for Device-to-Device Communications
Venue: arXiv cs.IT 2017
Year: 2017

We study optimal geographic content placement for device-to-device (D2D) networks in which each file's popularity follows the Zipf distribution. The locations of the D2D users (caches) are modeled by a Poisson point process (PPP) and have limited communication range and finite storage. Inspired by the Matérn hard-core (type II) point process that captures pairwise interactions between nodes, we devise a novel spatially correlated caching strategy called {\em hard-core placement} (HCP) such that the D2D nodes caching the same file are never closer to each other than the {\em exclusion radius}. The exclusion radius plays the role of a substitute for caching probability. We derive and optimize the exclusion radii to maximize the {\em hit probability}, which is the probability that a given D2D node can find a desired file at another node's cache within its communication range. Contrasting it with independent content placement, which is used in most prior work, our HCP strategy often yields a significantly higher cache hit probability. We further demonstrate that the HCP strategy is effective for small cache sizes and a small communication radius, which are likely conditions for D2D.
Brazilian Congress structural balance analysis
Venue: arXiv cs.SI 2017
Year: 2017

In this work, we study the behavior of Brazilian politicians and political parties with the help of clustering algorithms for signed social networks. For this purpose, we extract and analyze a collection of signed networks representing voting sessions of the lower house of Brazilian National Congress. We process all available voting data for the period between 2011 and 2016, by considering voting similarities between members of the Congress to define weighted signed links. The solutions obtained by solving Correlation Clustering (CC) problems are the basis for investigating deputies voting networks as well as questions about loyalty, leadership, coalitions, political crisis, and social phenomena such as mediation and polarization.
Identifiability of linear dynamic networks
Venue: arXiv cs.SY 2017
Year: 2017

Dynamic networks are structured interconnections of dynamical systems (modules) driven by external excitation and disturbance signals. In order to identify their dynamical properties and/or their topology consistently from measured data, we need to make sure that the network model set is identifiable. We introduce the notion of network identifiability, as a property of a parameterized model set, that ensures that different network models can be distinguished from each other when performing identification on the basis of measured data. Different from the classical notion of (parameter) identifiability, we focus on the distinction between network models in terms of their transfer functions. For a given structured model set with a pre-chosen topology, identifiability typically requires conditions on the presence and location of excitation signals, and on presence, location and correlation of disturbance signals. Because in a dynamic network, disturbances cannot always be considered to be of full-rank, the reduced-rank situation is also covered, meaning that the number of driving white noise processes can be strictly less than the number of disturbance variables. This includes the situation of having noise-free nodes.
Spectral learning of dynamic systems from nonequilibrium data
Venue: arXiv cs.LG 2017
Year: 2017

Observable operator models (OOMs) and related models are one of the most important and powerful tools for modeling and analyzing stochastic systems. They exactly describe dynamics of finite-rank systems and can be efficiently and consistently estimated through spectral learning under the assumption of identically distributed data. In this paper, we investigate the properties of spectral learning without this assumption due to the requirements of analyzing large-time scale systems, and show that the equilibrium dynamics of a system can be extracted from nonequilibrium observation data by imposing an equilibrium constraint. In addition, we propose a binless extension of spectral learning for continuous data. In comparison with the other continuous-valued spectral algorithms, the binless algorithm can achieve consistent estimation of equilibrium dynamics with only linear complexity.
Live Orchestral Piano, a system for real-time orchestral music generation
Venue: arXiv cs.LG 2017
Year: 2017

This paper introduces the first system for performing automatic orchestration based on a real-time piano input. We believe that it is possible to learn the underlying regularities existing between piano scores and their orchestrations by notorious composers, in order to automatically perform this task on novel piano inputs. To that end, we investigate a class of statistical inference models called conditional Restricted Boltzmann Machine (cRBM). We introduce a specific evaluation framework for orchestral generation based on a prediction task in order to assess the quality of different models. As prediction and creation are two widely different endeavours, we discuss the potential biases in evaluating temporal generative models through prediction tasks and their impact on a creative system. Finally, we introduce an implementation of the proposed model called Live Orchestral Piano (LOP), which allows to perform real-time projective orchestration of a MIDI keyboard input.
cf4ocl: a C framework for OpenCL
Venue: arXiv cs.DC 2017
Year: 2017

OpenCL is an open standard for parallel programming of heterogeneous compute devices, such as GPUs, CPUs, DSPs or FPGAs. However, the verbosity of its C host API can hinder application development. In this paper we present cf4ocl, a software library for rapid development of OpenCL programs in pure C. It aims to reduce the verbosity of the OpenCL API, offering straightforward memory management, integrated profiling of events (e.g., kernel execution and data transfers), simple but extensible device selection mechanism and user-friendly error management. We compare two versions of a conceptual application example, one based on cf4ocl, the other developed directly with the OpenCL host API. Results show that the former is simpler to implement and offers more features, at the cost of an effectively negligible computational overhead. Additionally, the tools provided with cf4ocl allowed for a quick analysis on how to optimize the application.
Joint Alignment of Multiple Point Sets with Batch and Incremental Expectation-Maximization
Venue: arXiv cs.CV 2017
Year: 2017

This paper addresses the problem of registering multiple point sets. Solutions to this problem are often approximated by repeatedly solving for pairwise registration, which results in an uneven treatment of the sets forming a pair: a model set and a data set. The main drawback of this strategy is that the model set may contain noise and outliers, which negatively affects the estimation of the registration parameters. In contrast, the proposed formulation treats all the point sets on an equal footing. Indeed, all the points are drawn from a central Gaussian mixture, hence the registration is cast into a clustering problem. We formally derive batch and incremental EM algorithms that robustly estimate both the GMM parameters and the rotations and translations that optimally align the sets. Moreover, the mixture's means play the role of the registered set of points while the variances provide rich information about the contribution of each component to the alignment. We thoroughly test the proposed algorithms on simulated data and on challenging real data collected with range sensors. We compare them with several state-of-the-art algorithms, and we show their potential for surface reconstruction from depth data.
Quantum one-way permutation over the finite field of two elements
Venue: arXiv cs.CC 2017
Year: 2017

In quantum cryptography, a one-way permutation is a bounded unitary operator $U:\mathcal{H} \to \mathcal{H}$ on a Hilbert space $\mathcal{H}$ that is easy to compute on every input, but hard to invert given the image of a random input. Levin [Probl. Inf. Transm., vol. 39 (1): 92-103 (2003)] has conjectured that the unitary transformation $g(a,x)=(a,f(x)+ax)$, where $f$ is any length-preserving function and $a,x \in GF_{{2}^{\|x\|}}$, is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin's one-way permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial $poly(x)$ over the Boolean ring of all subsets of $x$. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst ca
From Physical to Cyber: Escalating Protection for Personalized Auto Insurance
Venue: arXiv cs.CR 2017
Year: 2017

Nowadays, auto insurance companies set personalized insurance rate based on data gathered directly from their customers' cars. In this paper, we show such a personalized insurance mechanism -- wildly adopted by many auto insurance companies -- is vulnerable to exploit. In particular, we demonstrate that an adversary can leverage off-the-shelf hardware to manipulate the data to the device that collects drivers' habits for insurance rate customization and obtain a fraudulent insurance discount. In response to this type of attack, we also propose a defense mechanism that escalates the protection for insurers' data collection. The main idea of this mechanism is to augment the insurer's data collection device with the ability to gather unforgeable data acquired from the physical world, and then leverage these data to identify manipulated data points. Our defense mechanism leveraged a statistical model built on unmanipulated data and is robust to manipulation methods that are not foreseen previously. We have implemented this defense mechanism as a proof-of-concept prototype and tested its effectiveness in the real world. Our evaluation shows that our defense mechanism exhibits a false positive rate of 0.032 and a false negative rate of 0.013.
Physical Layer Security-Aware Routing and Performance Tradeoffs in Ad Hoc Networks
Venue: arXiv cs.IT 2017
Year: 2017

The application of physical layer security in ad hoc networks has attracted considerable academic attention recently. However, the available studies mainly focus on the single-hop and two-hop network scenarios, and the price in terms of degradation of communication quality of service (QoS) caused by improving security is largely uninvestigated. As a step to address these issues, this paper explores the physical layer security-aware routing and performance tradeoffs in a multi-hop ad hoc network. Specifically, for any given end-to-end path we first derive its connection outage probability (COP) and secrecy outage probability (SOP) in closed-form, which serve as the performance metrics of communication QoS and transmission security, respectively. Based on the closed-form expressions, we then study the security-QoS tradeoffs to minimize COP (resp. SOP) conditioned on that SOP (resp. COP) is guaranteed. With the help of analysis of a given path, we further propose the routing algorithms which can achieve the optimal performance tradeoffs for any pair of source and destination nodes in a distributed manner. Finally, simulation and numerical results are presented to validate the efficiency of our theoretical analysis, as well as to illustrate the security-QoS tradeoffs and the routing performance.
Adaptive Regularization in Convex Composite Optimization for Variational Imaging Problems
Venue: arXiv cs.CV 2017
Year: 2017

We propose an adaptive regularization scheme in a variational framework where a convex composite energy functional is optimized. We consider a number of imaging problems including denoising, segmentation and motion estimation, which are considered as optimal solutions of the energy functionals that mainly consist of data fidelity, regularization and a control parameter for their trade-off. We presents an algorithm to determine the relative weight between data fidelity and regularization based on the residual that measures how well the observation fits the model. Our adaptive regularization scheme is designed to locally control the regularization at each pixel based on the assumption that the diversity of the residual of a given imaging model spatially varies. The energy optimization is presented in the alternating direction method of multipliers (ADMM) framework where the adaptive regularization is iteratively applied along with mathematical analysis of the proposed algorithm. We demonstrate the robustness and effectiveness of our adaptive regularization through experimental results presenting that the qualitative and quantitative evaluation results of each imaging task are superior to the results with a constant regularization scheme. The desired properties, robustness and effectiveness, of the regularization parameter selection in a variational framework for imaging problems are achieved by merely replacing the static regularization parameter with our adaptive one.
Request Patterns and Caching for VoD Services with Recommendation Systems
Venue: arXiv cs.NI 2017
Year: 2017

Video on Demand (VoD) services like Netflix and YouTube account for ever increasing fractions of Internet traffic. It is estimated that this fraction will cross 80% in the next three years. Most popular VoD services have recommendation engines which recommend videos to users based on their viewing history, thus introducing time-correlation in user requests. Understanding and modeling this time-correlation in user requests is critical for network traffic engineering. The primary goal of this work is to use empirically observed properties of user requests to model the effect of recommendation engines on the request patterns in VoD services. We propose a Markovian request model to capture the time-correlation in user requests and show that our model is consistent with the observations of existing empirical studies. Most large-scale VoD services deliver content to users via a distributed network of servers as serving users requests via geographically co-located servers reduces latency and network bandwidth consumption. The content replication policy, i.e., determining which contents to cache on the servers is a key resource allocation problem for VoD services. Recent studies show that low start-up delay is a key Quality of Service (QoS) requirement of users of VoD services. This motivates the need to pre-fetch (fetch before contents are requested) and cache content likely to be request in the near future. Since pre-fetching leads to an increase in the network bandwidth usage, we use our Markovian model to explore the trade-offs and feasibility of implementing recommendation based pre-fetching.
The Incentive Ratio in Exchange Economies
Venue: arXiv cs.GT 2017
Year: 2017

The incentive ratio measures the utility gains from strategic behaviour. Without any restrictions on the setup, ratios for linear, Leontief and Cobb-Douglas exchange markets are unbounded, showing that manipulating the equilibrium is a worthwhile endeavour, even if it is computationally challenging. Such unbounded improvements can be achieved even if agents only misreport their utility functions. This provides a sharp contrast with previous results from Fisher markets. When the Cobb-Douglas setup is more restrictive, the maximum utility gain is bounded by the number of commodities. By means of an example, we show that it is possible to exceed a known upper bound for Fisher markets in exchange economies.
Guided Policy Search with Delayed Sensor Measurements
Venue: arXiv cs.RO 2017
Year: 2017

Guided policy search is a method for reinforcement learning that trains a general policy for accomplishing a given task by guiding the learning of the policy with multiple guiding distributions. Guided policy search relies on learning an underlying dynamical model of the environment and then, at each iteration of the algorithm, using that model to gradually improve the policy. This model, though, often makes the assumption that the environment dynamics are markovian, e.g., depend only on the current state and control signal. In this paper we apply guided policy search to a problem with non-markovian dynamics. Specifically, we apply it to the problem of pouring a precise amount of liquid from a cup into a bowl, where many of the sensor measurements experience non-trivial amounts of delay. We show that, with relatively simple state augmentation, guided policy search can be extended to non-markovian dynamical systems, where the non-markovianess is caused by delayed sensor readings.
A tool for stability and power sharing analysis of a generalized class of droop controllers for high-voltage direct-current transmission systems
Venue: arXiv cs.SY 2017
Year: 2017

The problem of primary control of high-voltage direct current transmission systems is addressed in this paper, which contains four main contributions. First, to propose a new nonlinear, more realistic, model for the system suitable for primary control design, which takes into account nonlinearities introduced by conventional inner controllers. Second, to determine necessary conditions - dependent on some free controller tuning parameters - for the existence of equilibria. Third, to formulate additional (necessary) conditions for these equilibria to satisfy the power sharing constraints. Fourth, to establish conditions for stability of a given equilibrium point. The usefulness of the theoretical results is illustrated via numerical calculations on a four-terminal example.
DESPOT: Online POMDP Planning with Regularization
Venue: arXiv cs.AI 2017
Year: 2017

The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimensionality" and the "curse of history". To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the "execution" of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.