OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Algorithms for Generating and Analyzing Structural Brain Networks with a Varying Number of Nodes
Venue: arXiv cs.CE 2016
Year: 2016

Diffusion Magnetic Resonance Imaging (MRI) exploits the anisotropic diffusion of water molecules in the brain to enable the estimation of the brain's anatomical fiber tracts at a relatively high resolution. In particular, tractographic methods can be used to generate whole-brain anatomical connectivity matrix where each element provides an estimate of the connectivity strength between the corresponding voxels. Structural brain networks are built using the connectivity information and a predefined brain parcellation, where the nodes of the network represent the brain regions and the edge weights capture the connectivity strengths between the corresponding brain regions. This paper introduces a number of novel scalable methods to generate and analyze structural brain networks with a varying number of nodes. In particular, we introduce a new parallel algorithm to quickly generate large scale connectivity-based parcellations for which voxels in a region possess highly similar connectivity patterns to the rest of the regions. We show that the corresponding regional structural consistency is always superior to randomly generated parcellations over a wide range of parcellation sizes. Corresponding brain networks with a varying number of nodes are analyzed using standard graph-theorectic measures, as well as, new measures derived from spectral graph theory. Our results indicate increasingly more statistical power of brain networks with larger numbers of nodes and the relatively unique shape of the spectral profile of large brain networks relative to other well-known networks.
The CUDA LATCH Binary Descriptor: Because Sometimes Faster Means Better
Venue: arXiv cs.CV 2016
Year: 2016

Accuracy, descriptor size, and the time required for extraction and matching are all important factors when selecting local image descriptors. To optimize over all these requirements, this paper presents a CUDA port for the recent Learned Arrangement of Three Patches (LATCH) binary descriptors to the GPU platform. The design of LATCH makes it well suited for GPU processing. Owing to its small size and binary nature, the GPU can further be used to efficiently match LATCH features. Taken together, this leads to breakneck descriptor extraction and matching speeds. We evaluate the trade off between these speeds and the quality of results in a feature matching intensive application. To this end, we use our proposed CUDA LATCH (CLATCH) to recover structure from motion (SfM), comparing 3D reconstructions and speed using different representations. Our results show that CLATCH provides high quality 3D reconstructions at fractions of the time required by other representations, with little, if any, loss of reconstruction quality.
A Generic Bet-and-run Strategy for Speeding Up Traveling Salesperson and Minimum Vertex Cover
Venue: arXiv cs.AI 2016
Year: 2016

A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.
Book Review of Susan Greenfield's 'Mind Change: How Digital Technologies Are Leaving Their Mark On Our Brains'
Venue: arXiv cs.CY 2016
Year: 2016

This is a review of Susan Greenfield's 2015 book 'Mind Change: How Digital Technologies Are Leaving Their Mark On Our Brains'. Greenfield is a neuroscientist and a member of the UK House of Lords, who argues that digital technologies are changing the human environment "in an unprecedented way," and that by adapting to this environment, "the brain may also be changing in an unprecedented way." The book and its author have created a surprising amount of controversy. I discuss both Greenfield's book and a prominent critique by Bell et al. (2015). The exchange points to some flaws in Greenfield's argument and represents an interesting debate about the public role of scientists, but it does not undermine the value of the book as a springboard for discussions about possible policies and future research.
Partial Solvers for Parity Games: Effective Polynomial-Time Composition
Venue: arXiv cs.LO 2016
Year: 2016

Partial methods play an important role in formal methods and beyond. Recently such methods were developed for parity games, where polynomial-time partial solvers decide the winners of a subset of nodes. We investigate here how effective polynomial-time partial solvers can be by studying interactions of partial solvers based on generic composition patterns that preserve polynomial-time computability. We show that use of such composition patterns discovers new partial solvers - including those that merge node sets that have the same but unknown winner - by studying games that composed partial solvers can neither solve nor simplify. We experimentally validate that this data-driven approach to refinement leads to polynomial-time partial solvers that can solve all standard benchmarks of structured games. For one of these polynomial-time partial solvers not even a sole random game from a few billion random games of varying configuration was found that it won't solve completely.
Stochastic Equilibria under Imprecise Deviations in Terminal-Reward Concurrent Games
Venue: arXiv cs.GT 2016
Year: 2016

We study the existence of mixed-strategy equilibria in concurrent games played on graphs. While existence is guaranteed with safety objectives for each player, Nash equilibria need not exist when players are given arbitrary terminal-reward objectives, and their existence is undecidable with qualitative reachability objectives (and only three players). However, these results rely on the fact that the players can enforce infinite plays while trying to improve their payoffs. In this paper, we introduce a relaxed notion of equilibria, where deviations are imprecise. We prove that contrary to Nash equilibria, such (stationary) equilibria always exist, and we develop a PSPACE algorithm to compute one.
Liveness for Verification
Venue: arXiv cs.PL 2016
Year: 2016

We explore the use of liveness for interactive program verification for a simple concurrent object language. Our experimental IDE integrates two (formally dual) kinds of continuous testing into the development environment: compatibility-checking, which verifies an object's use of other objects, and compliance-checking, which verifies an object's claim to refine the behaviour of another object. Source code errors highlighted by the IDE are not static type errors but the reflection back to the source of runtime errors that occur in some execution of the system. We demonstrate our approach, and discuss opportunities and challenges.
A Linear Time Parameterized Algorithm for Directed Feedback Vertex Set
Venue: arXiv cs.DS 2016
Year: 2016

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed graph $D$ on $n$ vertices and $m$ edges, and an integer $k$. The objective is to determine whether there exists a set of at most $k$ vertices intersecting every directed cycle of $D$. Whether or not DFVS admits a fixed parameter tractable (FPT) algorithm was considered the most important open problem in parameterized complexity until Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008] answered the question in the affirmative. They gave an algorithm for the problem with running time $O(k!4^kk^4nm)$. Since then, no faster algorithm for the problem has been found. In this paper, we give an algorithm for DFVS with running time $O(k!4^kk^5(n+m))$. Our algorithm is the first algorithm for DFVS with linear dependence on input size. Furthermore, the asymptotic dependence of the running time of our algorithm on the parameter $k$ matches up to a factor $k$ the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon. On the way to designing our algorithm for DFVS, we give a general methodology to shave off a factor of $n$ from iterative-compression based algorithms for a few other well-studied covering problems in parameterized complexity. We demonstrate the applicability of this technique by speeding up by a factor of $n$, the current best FPT algorithms for Multicut [STOC 2011, SICOMP 2014] and Directed Subset Feedback Vertex Set [ICALP 2012, TALG 2014].
Sampling Generative Networks
Venue: arXiv cs.NE 2016
Year: 2016

We introduce several techniques for sampling and visualizing the latent spaces of generative models. Replacing linear interpolation with spherical linear interpolation prevents diverging from a model's prior distribution and produces sharper samples. J-Diagrams and MINE grids are introduced as visualizations of manifolds created by analogies and nearest neighbors. We demonstrate two new techniques for deriving attribute vectors: bias-corrected vectors with data replication and synthetic vectors with data augmentation. Binary classification using attribute vectors is presented as a technique supporting quantitative analysis of the latent space. Most techniques are intended to be independent of model type and examples are shown on both Variational Autoencoders and Generative Adversarial Networks.
Sort Race
Venue: arXiv cs.DS 2016
Year: 2016

Sorting is one of the oldest computing problems and is still very important in the age of big data. Various algorithms and implementation techniques have been proposed. In this study, we focus on comparison based, internal sorting algorithms. We created 12 data types of various sizes for experiments and tested extensively various implementations in a single setting. Using some effective techniques, we discovered that quicksort is adaptive to nearly sorted inputs and is still the best overall sorting algorithm. We also identified which techniques are effective in timsort, one of the most popular and efficient sorting method based on natural mergesort, and created our version of mergesort, which runs faster than timsort on nearly sorted instances. Our implementations of quicksort and mergesort are different from other implementations reported in all textbooks or research articles, faster than any version of the C library qsort functions, not only for randomly generated data, but also for various types of nearly sorted data. This experiment can help the user to choose the best sorting algorithm for the hard sorting job at hand. This work provides a platform for anyone to test their own sorting algorithm against the best in the field.
Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection
Venue: arXiv cs.DS 2016
Year: 2016

We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a $k$-way merge intersection, for constant $k$, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a $k$-way merge, for non-constant $k$, and a crossing of two-way traffic is NP-complete.
Minimum Eccentricity Shortest Path Problem: an Approximation Algorithm and Relation with the k-Laminarity Problem
Venue: arXiv cs.CC 2016
Year: 2016

The Minimum Eccentricity Shortest Path (MESP) Problem consists in determining a shortest path (a path whose length is the distance between its extremities) of minimum eccentricity in a graph. It was introduced by Dragan and Leitert [9] who described a linear-time algorithm which is an 8-approximation of the problem. In this paper, we study deeper the double-BFS procedure used in that algorithm and extend it to obtain a linear-time 3-approximation algorithm. We moreover study the link between the MESP problem and the notion of laminarity, introduced by V{ö}lkel et al [12], corresponding to its restriction to a diameter (i.e. a shortest path of maximum length), and show tight bounds between MESP and laminarity parameters.
Automating Large-Scale Simulation and Data Analysis with OMNeT++: Lession Learned and Future Perspectives
Venue: arXiv cs.PF 2016
Year: 2016

Simulation is widely adopted in the study of modern computer networks. In this context, OMNeT++ provides a set of very effective tools that span from the definition of the network, to the automation of simulation execution and quick result representation. However, as network models become more and more complex to cope with the evolution of network systems, the amount of simulation factors, the number of simulated nodes and the size of results grow consequently, leading to simulations with larger scale. In this work, we perform a critical analysis of the tools provided by OMNeT++ in case of such large-scale simulations. We then propose a unified and flexible software architecture to support simulation automation.
WiFi-Direct Simulation for INET in OMNeT++
Venue: arXiv cs.NI 2016
Year: 2016

Wi-Fi Direct is a popular wireless technology which is integrated in most of today's smartphones and tablets. This technology allows a set of devices to dynamically negotiate and select a group owner which plays the role access point. This important feature is the strength of Wi-Fi Direct and makes it more and more widely used in telecommunications networks. In this paper, we present the implementation of Wi-Fi Direct in the INET framework of OMNeT++. We have implemented the main procedures of Wi-Fi Direct such as discovery, negotiation and group formation. The implementation has been validated by two test scenarios which show the conformity of the implementation to the protocol specification.
C-Planarity of Overlapping Clusterings Including Unions of Two Partitions
Venue: arXiv cs.CG 2016
Year: 2016

We show that clustered planarity with overlapping clusters as introduced by Didimo et al. can be solved in polynomial time if each cluster induces a connected subgraph. It can be solved in linear time if the set of clusters is the union of two partitions of the vertex set such that, for each cluster, both the cluster and its complement, induce connected subgraphs. Clustered planarity with overlapping clusters is NP-complete, even if restricted to instances where the underlying graph is 2-connected, the set of clusters is the union of two partitions and each cluster contains at most two connected components while their complements contain at most three connected components.
Sequencing Chess
Venue: arXiv cs.AI 2016
Year: 2016

We analyze the structure of the state space of chess by means of transition path sampling Monte Carlo simulation. Based on the typical number of moves required to transpose a given configuration of chess pieces into another, we conclude that the state space consists of several pockets between which transitions are rare. Skilled players explore an even smaller subset of positions that populate some of these pockets only very sparsely. These results suggest that the usual measures to estimate both, the size of the state space and the size of the tree of legal moves, are not unique indicators of the complexity of the game, but that topological considerations are equally important.
Results of a Collective Awareness Platforms Investigation
Venue: arXiv cs.HC 2016
Year: 2016

In this paper we provide two introductory analyses of CAPs, based exclusively on the analysis of documents found on the Internet. The first analysis allowed us to investigate the world of CAPs, in particular for what concerned their status (dead or alive), the scope of those platforms and the typology of users. In order to develop a more accurate model of CAPs, and to understand more deeply the motivation of the users and the type of expected payoff, we analysed those CAPs from the above list that are still alive and we used two models developed for what concerned the virtual community and the collective intelligence.
Non-trivial reputation effects on social decision making in virtual environment
Venue: arXiv cs.SI 2016
Year: 2016

Reputation systems are currently used, often with success, to ensure the functioning of online services as well as of e-commerce sites. Despite the relationship between reputation and material cooperative behaviours is quite supported, less obvious appears the relationship with informative behaviours, which are crucial for the transmission of reputational information and therefore for the maintenance of cooperation among individuals. The purpose of this study was to verify how reputation affects cooperation dynamics in virtual environment, within a social dilemma situation (i.e., where there are incentives to act selfishly). The results confirm that reputation can activate prosocial conducts, however it highlights also the limitations and distortions that reputation can create.
Glassbox: Dynamic Analysis Platform for Malware Android Applications on Real Devices
Venue: arXiv cs.CR 2016
Year: 2016

Android is the most widely used smartphone OS with 82.8% market share in 2015. It is therefore the most widely targeted system by malware authors. Researchers rely on dynamic analysis to extract malware behaviors and often use emulators to do so. However, using emulators lead to new issues. Malware may detect emulation and as a result it does not execute the payload to prevent the analysis. Dealing with virtual device evasion is a never-ending war and comes with a non-negligible computation cost. To overcome this state of affairs, we propose a system that does not use virtual devices for analysing malware behavior. Glassbox is a functional prototype for the dynamic analysis of malware applications. It executes applications on real devices in a monitored and controlled environment. It is a fully automated system that installs, tests and extracts features from the application for further analysis. We present the architecture of the platform and we compare it with existing Android dynamic analysis platforms. Lastly, we evaluate the capacity of Glassbox to trigger application behaviors by measuring the average coverage of basic blocks on the AndroCoverage dataset. We show that it executes on average 13.52% more basic blocks than the Monkey program.
Mechanism Design with Exchangeable Allocations
Venue: arXiv cs.GT 2016
Year: 2016

We investigate mechanism design without payments when agents have different types of preferences. Contrary to most settings in the literature where agents have the same preference, e.g. in the facility location games all agents would like to stay close to (or away from) the facility, we demonstrate the limitation of mechanism design without payments when agents have different preferences by introducing exchanging phases. We consider two types of exchanging phases. The first model is called central exchanges where the exchanges are performed by a central authority. The other model is called individual exchanges where agents exchange their outcomes by themselves. By using facility location games as an example, we provide a truthful mechanism that optimizes social welfare in central exchanges. We also provide a universally truthful randomized mechanism that achieves at least a half of the optimal social welfare in individual exchanges.
Model Selection Framework for Graph-based data
Venue: arXiv cs.SI 2016
Year: 2016

Graphs are powerful abstractions for capturing complex relationships in diverse application settings. An active area of research focuses on theoretical models that define the generative mechanism of a graph. Yet given the complexity and inherent noise in real datasets, it is still very challenging to identify the best model for a given observed graph. We discuss a framework for graph model selection that leverages a long list of graph topological properties and a random forest classifier to learn and classify different graph instances. We fully characterize the discriminative power of our approach as we sweep through the parameter space of two generative models, the Erdos-Renyi and the stochastic block model. We show that our approach gets very close to known theoretical bounds and we provide insight on which topological features play a critical discriminating role.
Visual Stability Prediction and Its Application to Manipulation
Venue: arXiv cs.CV 2016
Year: 2016

Understanding physical phenomena is a key competence that enables humans and animals to act and interact under uncertain perception in previously unseen environments containing novel objects and their configurations. Developmental psychology has shown that such skills are acquired by infants from observations at a very early stage. In this paper, we contrast a more traditional approach of taking a model-based route with explicit 3D representations and physical simulation by an {\em end-to-end} approach that directly predicts stability from appearance. We ask the question if and to what extent and quality such a skill can directly be acquired in a data-driven way---bypassing the need for an explicit simulation at run-time. We present a learning-based approach based on simulated data that predicts stability of towers comprised of wooden blocks under different conditions and quantities related to the potential fall of the towers. We first evaluate the approach on synthetic data and compared the results to human judgments on the same stimuli. Further, we extend this approach to reason about future states of such towers that in turn enables successful stacking.
NPCs as People, Too: The Extreme AI Personality Engine
Venue: arXiv cs.AI 2016
Year: 2016

PK Dick once asked "Do Androids Dream of Electric Sheep?" In video games, a similar question could be asked of non-player characters: Do NPCs have dreams? Can they live and change as humans do? Can NPCs have personalities, and can these develop through interactions with players, other NPCs, and the world around them? Despite advances in personality AI for games, most NPCs are still undeveloped and undeveloping, reacting with flat affect and predictable routines that make them far less than human--in fact, they become little more than bits of the scenery that give out parcels of information. This need not be the case. Extreme AI, a psychology-based personality engine, creates adaptive NPC personalities. Originally developed as part of the thesis "NPCs as People: Using Databases and Behaviour Trees to Give Non-Player Characters Personality," Extreme AI is now a fully functioning personality engine using all thirty facets of the Five Factor model of personality and an AI system that is live throughout gameplay. This paper discusses the research leading to Extreme AI; develops the ideas found in that thesis; discusses the development of other personality engines; and provides examples of Extreme AI's use in two game demos.