OpenRaiser/Intern-Atlas huggingface dataset:
A Model for Partial Kantian Cooperation
Venue: arXiv cs.GT 2018
Year: 2018

In several game situations, the behavior of the players may depend not only on individual interests, but also on what each player considers as the correct thing to do. This work presents a game theoretic model, aiming to describe game situations in which the players' behavior is affected by ethical considerations. Particularly, we assume that they partially follow, Kant's `Categorical Imperative'. The model is stated for games with a continuum of players. The basic assumption made is that the participants perceive that they belong to virtual (imagined) groups, in which they optimize their actions as if they were bound to follow the same strategy. A partially cooperative equilibrium, called $r$-Kant-Nash equilibrium is then introduced. We then study the relationship of the $r$-Kant-Nash equilibrium with the Nash, (Bentham-) Harsanyi, Rawls difference and Roemer solutions. For the case where the set of possible player types is finite, we prove sufficient conditions for the existence and uniqueness of the $r$-Kant-Nash equilibrium and the equilibrium is characterized in terms of a variational inequality. For the case of continuous types, necessary conditions characterizing the partial Kantian equilibria are derived using a reduction to a set of optimal control problems. Finally, some numerical examples are given.
A Linear-Time Variational Integrator for Multibody Systems
Venue: arXiv cs.RO 2018
Year: 2018

We present an efficient variational integrator for multibody systems. Variational integrators reformulate the equations of motion for multibody systems as discrete Euler-Lagrange (DEL) equations, transforming forward integration into a root-finding problem for the DEL equations. Variational integrators have been shown to be more robust and accurate in preserving fundamental properties of systems, such as momentum and energy, than many frequently used numerical integrators. However, state-of-the-art algorithms suffer from $O(n^3)$ complexity, which is prohibitive for articulated multibody systems with a large number of degrees of freedom, $n$, in generalized coordinates. Our key contribution is to derive a recursive algorithm that evaluates DEL equations in $O(n)$, which scales up well for complex multibody systems such as humanoid robots. Inspired by recursive Newton-Euler algorithm, our key insight is to formulate DEL equation individually for each body rather than for the entire system. Furthermore, we introduce a new quasi-Newton method that exploits the impulse-based dynamics algorithm, which is also $O(n)$, to avoid the expensive Jacobian inversion in solving DEL equations. We demonstrate scalability and efficiency, as well as extensibility to holonomic constraints through several case studies.
Hardness Results for Consensus-Halving
Venue: arXiv cs.GT 2018
Year: 2018

We study the consensus-halving problem of dividing an object into two portions, such that each of $n$ agents has equal valuation for the two portions. The $ε$-approximate consensus-halving problem allows each agent to have an $ε$ discrepancy on the values of the portions. We prove that computing $ε$-approximate consensus-halving solution using $n$ cuts is in PPA, and is PPAD-hard, where $ε$ is some positive constant; the problem remains PPAD-hard when we allow a constant number of additional cuts. It is NP-hard to decide whether a solution with $n-1$ cuts exists for the problem. As a corollary of our results, we obtain that the approximate computational version of the Continuous Necklace Splitting Problem is PPAD-hard when the number of portions $t$ is two.
On the adoption of abductive reasoning for time series interpretation
Venue: arXiv cs.AI 2018
Year: 2018

Time series interpretation aims to provide an explanation of what is observed in terms of its underlying processes. The present work is based on the assumption that the common classification-based approaches to time series interpretation suffer from a set of inherent weaknesses, whose ultimate cause lies in the monotonic nature of the deductive reasoning paradigm. In this document we propose a new approach to this problem, based on the initial hypothesis that abductive reasoning properly accounts for the human ability to identify and characterize the patterns appearing in a time series. The result of this interpretation is a set of conjectures in the form of observations, organized into an abstraction hierarchy and explaining what has been observed. A knowledge-based framework and a set of algorithms for the interpretation task are provided, implementing a hypothesize-and-test cycle guided by an attentional mechanism. As a representative application domain, interpretation of the electrocardiogram allows us to highlight the strengths of the proposed approach in comparison with traditional classification-based approaches.
Consensus-based Privacy-preserving Data Aggregation
Venue: arXiv cs.SY 2018
Year: 2018

Privacy-preserving data aggregation in ad hoc networks is a challenging problem, considering the distributed communication and control requirement, dynamic network topology, unreliable communication links, etc. Different from the widely used cryptographic approaches, in this paper, we address this challenging problem by exploiting the distributed consensus technique. We first propose a secure consensus-based data aggregation (SCDA) algorithm that guarantees an accurate sum aggregation while preserving the privacy of sensitive data. Then, we prove that the proposed algorithm converges accurately and is $(ε, σ)$-data-privacy, and the mathematical relationship between $ε$ and $σ$ is provided. Extensive simulations have shown that the proposed algorithm has high accuracy and low complexity, and they are robust against network dynamics.
Parallelization of JOREK-STARWALL for non-linear MHD simulations including resistive walls (Report of the EUROfusion High Level Support Team Projects JORSTAR/JORSTAR2)
Venue: arXiv cs.DC 2018
Year: 2018

Large scale plasma instabilities inside a tokamak can be influenced by the currents flowing in the conducting vessel wall. This involves non linear plasma dynamics and its interaction with the wall current. In order to study this problem the code that solves the magneto-hydrodynamic (MHD) equations, called JOREK [Huysmans G.T.A. and Czarny O. NF 47, 659 (2007); Czarny O. and Huysmans G. JCP 227, 7423 (2008)], was coupled [Hoelzl M., et al. Journal of Physics: Conference Series, 401, 012010 (2012)] with the model for the vacuum region and the resistive conducting structure named STARWALL [Merkel P., Strumberger E., arXiv:150804911 (2015)]. The JOREK-STARWALL model has been already applied to perform simulations of Vertical Displacement Events (VDEs), Resistive Wall Modes (RWMs), Quiescent H-Mode, and vertical kick ELM triggering. At the beginning of the project it was not possible to resolve the realistic wall structure with a large number of finite element triangles due to the huge consumption of memory and wall clock time by STARWALL and the corresponding coupling routine in JOREK. Moreover, both the STARWALL code and the JOREK coupling routine were only partially parallelized via OpenMP. The aim of this project is to implement an MPI parallelization to reduce memory consumption and execution time such that simulations with large resolutions become possible.
Optimizing positional scoring rules for rank aggregation
Venue: arXiv cs.GT 2018
Year: 2018

Nowadays, several crowdsourcing projects exploit social choice methods for computing an aggregate ranking of alternatives given individual rankings provided by workers. Motivated by such systems, we consider a setting where each worker is asked to rank a fixed (small) number of alternatives and, then, a positional scoring rule is used to compute the aggregate ranking. Among the apparently infinite such rules, what is the best one to use? To answer this question, we assume that we have partial access to an underlying true ranking. Then, the important optimization problem to be solved is to compute the positional scoring rule whose outcome, when applied to the profile of individual rankings, is as close as possible to the part of the underlying true ranking we know. We study this fundamental problem from a theoretical viewpoint and present positive and negative complexity results and, furthermore, complement our theoretical findings with experiments on real-world and synthetic data.
From Monocular SLAM to Autonomous Drone Exploration
Venue: arXiv cs.RO 2018
Year: 2018

Micro aerial vehicles (MAVs) are strongly limited in their payload and power capacity. In order to implement autonomous navigation, algorithms are therefore desirable that use sensory equipment that is as small, low-weight, and low-power consuming as possible. In this paper, we propose a method for autonomous MAV navigation and exploration using a low-cost consumer-grade quadrocopter equipped with a monocular camera. Our vision-based navigation system builds on LSD-SLAM which estimates the MAV trajectory and a semi-dense reconstruction of the environment in real-time. Since LSD-SLAM only determines depth at high gradient pixels, texture-less areas are not directly observed so that previous exploration methods that assume dense map information cannot directly be applied. We propose an obstacle mapping and exploration approach that takes the properties of our semi-dense monocular SLAM system into account. In experiments, we demonstrate our vision-based autonomous navigation and exploration system with a Parrot Bebop MAV.
Differentially-Private Counting of Users' Spatial Regions
Venue: arXiv cs.DB 2018
Year: 2018

Mining of spatial data is an enabling technology for mobile services, Internet-connected cars, and the Internet of Things. But the very distinctiveness of spatial data that drives utility, can cost user privacy. Past work has focused upon points and trajectories for differentially-private release. In this work, we continue the tradition of privacy-preserving spatial analytics, focusing not on point or path data, but on planar spatial regions. Such data represents the area of a user's most frequent visitation---such as "around home and nearby shops". Specifically we consider the differentially-private release of data structures that support range queries for counting users' spatial regions. Counting planar regions leads to unique challenges not faced in existing work. A user's spatial region that straddles multiple data structure cells can lead to duplicate counting at query time. We provably avoid this pitfall by leveraging the Euler characteristic for the first time with differential privacy. To address the increased sensitivity of range queries to spatial region data, we calibrate privacy-preserving noise using bounded user region size and a constrained inference that uses robust least absolute deviations. Our novel constrained inference reduces noise and promotes covertness by (privately) imposing consistency. We provide a full end-to-end theoretical analysis of both differential privacy and high-probability utility for our approach using concentration bounds. A comprehensive experimental study on several real-world datasets establishes practical validity.
How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
Venue: arXiv cs.DS 2018
Year: 2018

In the last years, kernelization with structural parameters has been an active area of research within the field of parameterized complexity. As a relevant example, Gajarsk{y} et al. [ESA 2013] proved that every graph problem satisfying a property called finite integer index admits a linear kernel on graphs of bounded expansion and an almost linear kernel on nowhere dense graphs, parameterized by the size of a $c$-treedepth modulator, which is a vertex set whose removal results in a graph of treedepth at most $c$, where $c \geq 1$ is a fixed integer. The authors left as further research to investigate this parameter on general graphs, and in particular to find problems that, while admitting polynomial kernels on sparse graphs, behave differently on general graphs. In this article we answer this question by finding two very natural such problems: we prove that Vertex Cover admits a polynomial kernel on general graphs for any integer $c \geq 1$, and that Dominating Set does not for any integer $c \geq 2$ even on degenerate graphs, unless $\text{NP} \subseteq \text{coNP}/\text{poly}$. For the positive result, we build on the techniques of Jansen and Bodlaender [STACS 2011], and for the negative result we use a polynomial parameter transformation for $c\geq 3$ and an OR-cross-composition for $c = 2$. As existing results imply that Dominating Set admits a polynomial kernel on degenerate graphs for $c = 1$, our result provides a dichotomy about the existence of polynomial kernels for Dominating Set on degenerate graphs with this parameter.
Fast and Compact Planar Embeddings
Venue: arXiv cs.DS 2018
Year: 2018

There are many representations of planar graphs, but few are as elegant as Turán's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multi-edges, and can store any specified embedding. Its main disadvantage has been that "it does not allow efficient searching" (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turán's representation such that it supports fast navigation while retaining simplicity. As a consequence of the inherited simplicity, we offer the first efficient parallel construction of a compact encoding of a planar graph embedding. Our experimental results show that the resulting representation uses about 6 bits per edge in practice, supports basic navigation operations within a few microseconds, and can be built sequentially at a rate below 1 microsecond per edge, featuring a linear speedup with a parallel efficiency around 50\% for large datasets.
Approximate Gram-Matrix Interpolation for Wideband Massive MU-MIMO Systems
Venue: arXiv cs.IT 2018
Year: 2018

Numerous linear and non-linear data-detection and precoding algorithms for wideband massive multi-user (MU) multiple-input multiple-output (MIMO) wireless systems that rely on orthogonal frequency-division multiplexing (OFDM) or single-carrier frequency-division multiple access (SC-FDMA) require the computation of the Gram matrix for each active subcarrier. Computing the Gram matrix for each active subcarrier, however, results in excessively high computational complexity. In this paper, we propose novel, approximate algorithms that significantly reduce the complexity of Gram-matrix computation by simultaneously exploiting correlation across subcarriers and channel hardening. We show analytically that a small fraction of Gram-matrix computations in combination with approximate interpolation schemes are sufficient to achieve near-optimal error-rate performance at low computational complexity in massive MU-MIMO systems. We also demonstrate that the proposed methods exhibit improved robustness against channel-estimation errors compared to exact Gram-matrix interpolation algorithms that typically require high computational complexity.
Plug-and-Play CNN for Crowd Motion Analysis: An Application in Abnormal Event Detection
Venue: arXiv cs.CV 2018
Year: 2018

Most of the crowd abnormal event detection methods rely on complex hand-crafted features to represent the crowd motion and appearance. Convolutional Neural Networks (CNN) have shown to be a powerful tool with excellent representational capacities, which can leverage the need for hand-crafted features. In this paper, we show that keeping track of the changes in the CNN feature across time can facilitate capturing the local abnormality. We specifically propose a novel measure-based method which allows measuring the local abnormality in a video by combining semantic information (inherited from existing CNN models) with low-level Optical-Flow. One of the advantage of this method is that it can be used without the fine-tuning costs. The proposed method is validated on challenging abnormality detection datasets and the results show the superiority of our method compared to the state-of-the-art methods.
Should Algorithms for Random SAT and Max-SAT be Different?
Venue: arXiv cs.AI 2018
Year: 2018

We analyze to what extent the random SAT and Max-SAT problems differ in their properties. Our findings suggest that for random $k$-CNF with ratio in a certain range, Max-SAT can be solved by any SAT algorithm with subexponential slowdown, while for formulae with ratios greater than some constant, algorithms under the random walk framework require substantially different heuristics. In light of these results, we propose a novel probabilistic approach for random Max-SAT called ProMS. Experimental results illustrate that ProMS outperforms many state-of-the-art local search solvers on random Max-SAT benchmarks.
Technical Report on the CleverHans v2.1.0 Adversarial Examples Library
Venue: arXiv cs.LG 2018
Year: 2018

CleverHans is a software library that provides standardized reference implementations of adversarial example construction techniques and adversarial training. The library may be used to develop more robust machine learning models and to provide standardized benchmarks of models' performance in the adversarial setting. Benchmarks constructed without a standardized implementation of adversarial example construction are not comparable to each other, because a good result may indicate a robust model or it may merely indicate a weak implementation of the adversarial example construction procedure. This technical report is structured as follows. Section 1 provides an overview of adversarial examples in machine learning and of the CleverHans software. Section 2 presents the core functionalities of the library: namely the attacks based on adversarial examples and defenses to improve the robustness of machine learning models to these attacks. Section 3 describes how to report benchmark results using the library. Section 4 describes the versioning system.
Notes on Pure Dataflow Matrix Machines: Programming with Self-referential Matrix Transformations
Venue: arXiv cs.PL 2018
Year: 2018

Dataflow matrix machines are self-referential generalized recurrent neural nets. The self-referential mechanism is provided via a stream of matrices defining the connectivity and weights of the network in question. A natural question is: what should play the role of untyped lambda-calculus for this programming architecture? The proposed answer is a discipline of programming with only one kind of streams, namely the streams of appropriately shaped matrices. This yields Pure Dataflow Matrix Machines which are networks of transformers of streams of matrices capable of defining a pure dataflow matrix machine.
Adaptive Graph-based Total Variation for Tomographic Reconstructions
Venue: arXiv cs.CV 2018
Year: 2018

Sparsity exploiting image reconstruction (SER) methods have been extensively used with Total Variation (TV) regularization for tomographic reconstructions. Local TV methods fail to preserve texture details and often create additional artefacts due to over-smoothing. Non-Local TV (NLTV) methods have been proposed as a solution to this but they either lack continuous updates due to computational constraints or limit the locality to a small region. In this paper, we propose Adaptive Graph-based TV (AGTV). The proposed method goes beyond spatial similarity between different regions of an image being reconstructed by establishing a connection between similar regions in the entire image regardless of spatial distance. As compared to NLTV the proposed method is computationally efficient and involves updating the graph prior during every iteration making the connection between similar regions stronger. Moreover, it promotes sparsity in the wavelet and graph gradient domains. Since TV is a special case of graph TV the proposed method can also be seen as a generalization of SER and TV methods.
Fundamental properties of solutions to utility maximization problems in wireless networks
Venue: arXiv cs.IT 2018
Year: 2018

We introduce a unified framework for the study of the utility and the energy efficiency of solutions to a large class of weighted max-min utility maximization problems in interference-coupled wireless networks. In more detail, given a network utility maximization problem parameterized by a maximum power budget $\bar{p}$ available to network elements, we define two functions that map the power budget $\bar{p}$ to the energy efficiency and to the utility achieved by the solution. Among many interesting properties, we prove that these functions are continuous and monotonic. In addition, we derive bounds revealing that the solutions to utility maximization problems are characterized by a low and a high power regime. In the low power regime, the energy efficiency of the solution can decrease slowly as the power budget increases, and the network utility grows linearly at best. In contrast, in the high power regime, the energy efficiency typically scales as $Θ(1/\bar{p})$ as $\bar{p}\to\infty$, and the network utility scales as $Θ(1)$. We apply the theoretical findings to a novel weighted rate maximization problem involving the joint optimization of the uplink power and the base station assignment.
Polynomial methods for Procedural Terrain Generation
Venue: arXiv cs.GR 2018
Year: 2018

A new method is presented, allowing for the generation of 3D terrain and texture from coherent noise. The method is significantly faster than prevailing fractal brownian motion approaches, while producing results of equivalent quality. The algorithm is derived through a systematic approach that generalizes to an arbitrary number of spatial dimensions and gradient smoothness. The results are compared, in terms of performance and quality, to fundamental and efficient gradient noise methods widely used in the domain of fast terrain generation: Perlin noise and OpenSimplex noise. Finally, to objectively quantify the degree of realism of the results, a fractal analysis of the generated landscapes is performed and compared to real terrain data.
Tensorial Mixture Models
Venue: arXiv cs.LG 2018
Year: 2018

Casting neural networks in generative frameworks is a highly sought-after endeavor these days. Contemporary methods, such as Generative Adversarial Networks, capture some of the generative capabilities, but not all. In particular, they lack the ability of tractable marginalization, and thus are not suitable for many tasks. Other methods, based on arithmetic circuits and sum-product networks, do allow tractable marginalization, but their performance is challenged by the need to learn the structure of a circuit. Building on the tractability of arithmetic circuits, we leverage concepts from tensor analysis, and derive a family of generative models we call Tensorial Mixture Models (TMMs). TMMs assume a simple convolutional network structure, and in addition, lend themselves to theoretical analyses that allow comprehensive understanding of the relation between their structure and their expressive properties. We thus obtain a generative model that is tractable on one hand, and on the other hand, allows effective representation of rich distributions in an easily controlled manner. These two capabilities are brought together in the task of classification under missing data, where TMMs deliver state of the art accuracies with seamless implementation and design.