OpenRaiser/Intern-Atlas huggingface dataset:
Information Spreading in Dynamic Networks under Oblivious Adversaries
Venue: arXiv cs.DC 2016
Year: 2016

We study the problem of gossip in dynamic networks controlled by an adversary that can modify the network arbitrarily from one round to another, provided that the network is always connected. In the gossip problem, $n$ tokens are arbitrarily distributed among the $n$ network nodes, and the goal is to disseminate all the $n$ tokens to every node. Our focus is on token-forwarding algorithms, which do not manipulate tokens in any way other than storing, copying, and forwarding them. Gossip can be completed in linear time in any static network, but a basic open question for dynamic networks is the existence of a distributed protocol that can do significantly better than an easily achievable bound of $O(n^2)$ rounds. In previous work, it has been shown that under adaptive adversaries, every token forwarding algorithm requires $Ω(n^2/\log n)$ rounds. In this paper, we study oblivious adversaries, which differ from adaptive adversaries in one crucial aspect--- they are oblivious to random choices made by the protocol. We present an $\tildeΩ(n^{3/2})$ lower bound under an oblivious adversary for RANDDIFF, a natural algorithm in which neighbors exchange a token chosen uniformly at random from the difference of their token sets. We also present an $\tildeΩ(n^{4/3})$ bound under a stronger notion of oblivious adversary for symmetric knowledge-based algorithms. On the positive side, we present a centralized algorithm that completes gossip in $\tilde{O}(n^{3/2})$ rounds. We also show an $\tilde{O}(n^{5/3})$ upper bound for RANDDIFF in a restricted class of oblivious adversaries, which we call paths-respecting.
Time Reversal with Post-Equalization for OFDM without CP in Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies the possibility of eliminating the redundant cyclic prefix (CP) of orthogonal frequency division multiplexing (OFDM) in massive multiple-input multiple-output systems. The absence of CP increases the bandwidth efficiency in expense of intersymbol interference (ISI) and intercarrier interference (ICI). It is known that in massive MIMO, different types of interference fade away as the number of base station (BS) antennas tends to infinity. In this paper, we investigate if the channel distortions in the absence of CP are averaged out in the large antenna regime. To this end, we analytically study the performance of the conventional maximum ratio combining (MRC) and realize that there always remains some residual interference leading to saturation of signal to interference (SIR). This saturation of SIR is quantified through mathematical equations. Moreover, to resolve the saturation problem, we propose a technique based on time-reversal MRC with zero forcing multiuser detection (TR-ZF). Thus, the SIR of our proposed TR-ZF does not saturate and is a linear function of the number of BS antennas. We also show that TR-ZF only needs one OFDM demodulator per user irrespective of the number of BS antennas; reducing the BS signal processing complexity significantly. Finally, we corroborate our claims as well as analytical results through simulations.
The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems
Venue: arXiv cs.CR 2016
Year: 2016

Polycyclic groups are natural generalizations of cyclic groups but with more complicated algorithmic properties. They are finitely presented and the word, conjugacy, and isomorphism decision problems are all solvable in these groups. Moreover, the non-virtually nilpotent ones exhibit an exponential growth rate. These properties make them suitable for use in group-based cryptography, which was proposed in 2004 by Eick and Kahrobaei. Since then, many cryptosystems have been created that employ polycyclic groups. These include key exchanges such as non-commutative ElGamal, authentication schemes based on the twisted conjugacy problem, and secret sharing via the word problem. In response, heuristic and deterministic methods of cryptanalysis have been developed, including the length-based and linear decomposition attacks. Despite these efforts, there are classes of infinite polycyclic groups that remain suitable for cryptography. The analysis of algorithms for search and decision problems in polycyclic groups has also been developed. In addition to results for the aforementioned problems we present those concerning polycyclic representations, group morphisms, and orbit decidability. Though much progress has been made, many algorithmic and complexity problems remain unsolved, we conclude with a number of them. Of particular interest is to show that cryptosystems using infinite polycyclic groups are resistant to cryptanalysis on a quantum computer.
Asymptotic bounds on the globally optimal positions of orthogonal stiffeners for rectangular plates in elastostatic bending
Venue: arXiv cs.CE 2016
Year: 2016

The present paper treats the problem of finding the asymptotic bounds for the globally optimal locations of orthogonal stiffeners minimizing the compliance of a rectangular plate in elastostatic bending. The essence of the paper is the utilization of a method of analysis of orthogonally stiffened rectangular plates first presented by Mazurkiewicz in 1962, and obtained herein in a closed form for several special cases in the approximation of stiffeners having zero torsional rigidity. Asymptotic expansions of the expressions for the deflection field of a stiffened plate are used to derive limit-case globally optimal stiffening layouts for highly flexible and highly rigid stiffeners. A central result obtained in this work is an analytical proof of the fact that an array of flexible enough orthogonal stiffeners of any number, stiffening a simply-supported rectangular plate subjected to any lateral loading, is best to be put in the form of exactly two orthogonal stiffeners, one in each direction.
Juxtaposition of System Dynamics and Agent-based Simulation for a Case Study in Immunosenescence
Venue: arXiv cs.AI 2016
Year: 2016

Advances in healthcare and in the quality of life significantly increase human life expectancy. With the ageing of populations, new un-faced challenges are brought to science. The human body is naturally selected to be well-functioning until the age of reproduction to keep the species alive. However, as the lifespan extends, unseen problems due to the body deterioration emerge. There are several age-related diseases with no appropriate treatment; therefore, the complex ageing phenomena needs further understanding. Immunosenescence, the ageing of the immune system, is highly correlated to the negative effects of ageing, such as the increase of auto-inflammatory diseases and decrease in responsiveness to new diseases. Besides clinical and mathematical tools, we believe there is opportunity to further exploit simulation tools to understand immunosenescence. Compared to real-world experimentation, benefits include time and cost effectiveness due to the laborious, resource-intensiveness of the biological environment and the possibility of conducting experiments without ethic restrictions. Contrasted with mathematical models, simulation modelling is more suitable for representing complex systems and emergence. In addition, there is the belief that simulation models are easier to communicate in interdisciplinary contexts. Our work investigates the usefulness of simulations to understand immunosenescence by employing two different simulation methods, agent-based and system dynamics simulation, to a case study of immune cells depletion with age.
Simulating user learning in authoritative technology adoption: An agent based model for council-led smart meter deployment planning in the UK
Venue: arXiv cs.AI 2016
Year: 2016

How do technology users effectively transit from having zero knowledge about a technology to making the best use of it after an authoritative technology adoption? This post-adoption user learning has received little research attention in technology management literature. In this paper we investigate user learning in authoritative technology adoption by developing an agent-based model using the case of council-led smart meter deployment in the UK City of Leeds. Energy consumers gain experience of using smart meters based on the learning curve in behavioural learning. With the agent-based model we carry out experiments to validate the model and test different energy interventions that local authorities can use to facilitate energy consumers' learning and maintain their continuous use of the technology. Our results show that the easier energy consumers become experienced, the more energy-efficient they are and the more energy saving they can achieve; encouraging energy consumers' contacts via various informational means can facilitate their learning; and developing and maintaining their positive attitude toward smart metering can enable them to use the technology continuously. Contributions and energy policy/intervention implications are discussed in this paper.
Color Homography Color Correction
Venue: arXiv cs.CV 2016
Year: 2016

Homographies -- a mathematical formalism for relating image points across different camera viewpoints -- are at the foundations of geometric methods in computer vision and are used in geometric camera calibration, image registration, and stereo vision and other tasks. In this paper, we show the surprising result that colors across a change in viewing condition (changing light color, shading and camera) are also related by a homography. We propose a new color correction method based on color homography. Experiments demonstrate that solving the color homography problem leads to more accurate calibration.
Occam's Razor Applied to the Petri Net Coverability Problem
Venue: arXiv cs.LO 2016
Year: 2016

The verification of safety properties for concurrent systems often reduces to the coverability problem for Petri nets. This problem was shown to be ExpSpace-complete forty years ago. Driven by the concurrency revolution, it has regained a lot of interest over the last decade. In this paper, we propose a generic and simple approach to solve this problem. Our method is inspired from the recent approach of Blondin, Finkel, Haase and Haddad. Basically, we combine forward invariant generation techniques for Petri nets with backward reachability for well- structured transition systems. An experimental evaluation demonstrates the efficiency of our approach.
Indoor occupancy estimation from carbon dioxide concentration
Venue: arXiv cs.SY 2016
Year: 2016

This paper presents an indoor occupancy estimator with which we can estimate the number of real-time indoor occupants based on the carbon dioxide (CO2) measurement. The estimator is actually a dynamic model of the occupancy level. To identify the dynamic model, we propose the Feature Scaled Extreme Learning Machine (FS-ELM) algorithm, which is a variation of the standard Extreme Learning Machine (ELM) but is shown to perform better for the occupancy estimation problem. The measured CO2 concentration suffers from serious spikes. We find that pre-smoothing the CO2 data can greatly improve the estimation accuracy. In real applications, however, we cannot obtain the real-time globally smoothed CO2 data. We provide a way to use the locally smoothed CO2 data instead, which is real-time available. We introduce a new criterion, i.e. $x$-tolerance accuracy, to assess the occupancy estimator. The proposed occupancy estimator was tested in an office room with 24 cubicles and 11 open seats. The accuracy is up to 94 percent with a tolerance of four occupants.
Supervised quantum gate "teaching" for quantum hardware design
Venue: arXiv cs.LG 2016
Year: 2016

We show how to train a quantum network of pairwise interacting qubits such that its evolution implements a target quantum algorithm into a given network subset. Our strategy is inspired by supervised learning and is designed to help the physical construction of a quantum computer which operates with minimal external classical control.
Local Multiple Directional Pattern of Palmprint Image
Venue: arXiv cs.CV 2016
Year: 2016

Lines are the most essential and discriminative features of palmprint images, which motivate researches to propose various line direction based methods for palmprint recognition. Conventional methods usually capture the only one of the most dominant direction of palmprint images. However, a number of points in palmprint images have double or even more than two dominant directions because of a plenty of crossing lines of palmprint images. In this paper, we propose a local multiple directional pattern (LMDP) to effectively characterize the multiple direction features of palmprint images. LMDP can not only exactly denote the number and positions of dominant directions but also effectively reflect the confidence of each dominant direction. Then, a simple and effective coding scheme is designed to represent the LMDP and a block-wise LMDP descriptor is used as the feature space of palmprint images in palmprint recognition. Extensive experimental results demonstrate the superiority of the LMDP over the conventional powerful descriptors and the state-of-the-art direction based methods in palmprint recognition.
An ensemble of machine learning and anti-learning methods for predicting tumour patient survival rates
Venue: arXiv cs.LG 2016
Year: 2016

This paper primarily addresses a dataset relating to cellular, chemical and physical conditions of patients gathered at the time they are operated upon to remove colorectal tumours. This data provides a unique insight into the biochemical and immunological status of patients at the point of tumour removal along with information about tumour classification and post-operative survival. The relationship between severity of tumour, based on TNM staging, and survival is still unclear for patients with TNM stage 2 and 3 tumours. We ask whether it is possible to predict survival rate more accurately using a selection of machine learning techniques applied to subsets of data to gain a deeper understanding of the relationships between a patient's biochemical markers and survival. We use a range of feature selection and single classification techniques to predict the 5 year survival rate of TNM stage 2 and 3 patients which initially produces less than ideal results. The performance of each model individually is then compared with subsets of the data where agreement is reached for multiple models. This novel method of selective ensembling demonstrates that significant improvements in model accuracy on an unseen test set can be achieved for patients where agreement between models is achieved. Finally we point at a possible method to identify whether a patients prognosis can be accurately predicted or not.
Jamming in the Internet of Things: A Game-Theoretic Perspective
Venue: arXiv cs.IT 2016
Year: 2016

Due to its scale and largely interconnected nature, the Internet of Things (IoT) will be vulnerable to a number of security threats that range from physical layer attacks to network layer attacks. In this paper, a novel anti-jamming strategy for OFDM-based IoT systems is proposed which enables an IoT controller to protect the IoT devices against a malicious radio jammer. The interaction between the controller node and the jammer is modeled as a Colonel Blotto game with continuous and asymmetric resources in which the IoT controller, acting as defender, seeks to thwart the jamming attack by distributing its power among the subcarries in a smart way to decrease the aggregate bit error rate (BER) caused by the jammer. The jammer, on the other hand, aims at disrupting the system performance by allocating jamming power to different frequency bands. To solve the game, an evolutionary algorithm is proposed which can find a mixed-strategy Nash equilibrium of the Blotto game. Simulation results show that the proposed algorithm enables the IoT controller to maintain the BER above an acceptable threshold, thereby preserving the IoT network performance in the presence of malicious jamming.
Topological Data Analysis with Bregman Divergences
Venue: arXiv cs.CG 2016
Year: 2016

Given a finite set in a metric space, the topological analysis generalizes hierarchical clustering using a 1-parameter family of homology groups to quantify connectivity in all dimensions. The connectivity is compactly described by the persistence diagram. One limitation of the current framework is the reliance on metric distances, whereas in many practical applications objects are compared by non-metric dissimilarity measures. Examples are the Kullback-Leibler divergence, which is commonly used for comparing text and images, and the Itakura-Saito divergence, popular for speech and sound. These are two members of the broad family of dissimilarities called Bregman divergences. We show that the framework of topological data analysis can be extended to general Bregman divergences, widening the scope of possible applications. In particular, we prove that appropriately generalized Cech and Delaunay (alpha) complexes capture the correct homotopy type, namely that of the corresponding union of Bregman balls. Consequently, their filtrations give the correct persistence diagram, namely the one generated by the uniformly growing Bregman balls. Moreover, we show that unlike the metric setting, the filtration of Vietoris-Rips complexes may fail to approximate the persistence diagram. We propose algorithms to compute the thus generalized Cech, Vietoris-Rips and Delaunay complexes and experimentally test their efficiency. Lastly, we explain their surprisingly good performance by making a connection with discrete Morse theory.
Hierarchical Clustering of Asymmetric Networks
Venue: arXiv cs.LG 2016
Year: 2016

This paper considers networks where relationships between nodes are represented by directed dissimilarities. The goal is to study methods that, based on the dissimilarity structure, output hierarchical clusters, i.e., a family of nested partitions indexed by a connectivity parameter. Our construction of hierarchical clustering methods is built around the concept of admissible methods, which are those that abide by the axioms of value - nodes in a network with two nodes are clustered together at the maximum of the two dissimilarities between them - and transformation - when dissimilarities are reduced, the network may become more clustered but not less. Two particular methods, termed reciprocal and nonreciprocal clustering, are shown to provide upper and lower bounds in the space of admissible methods. Furthermore, alternative clustering methodologies and axioms are considered. In particular, modifying the axiom of value such that clustering in two-node networks occurs at the minimum of the two dissimilarities entails the existence of a unique admissible clustering method.
Excisive Hierarchical Clustering Methods for Network Data
Venue: arXiv cs.LG 2016
Year: 2016

We introduce two practical properties of hierarchical clustering methods for (possibly asymmetric) network data: excisiveness and linear scale preservation. The latter enforces imperviousness to change in units of measure whereas the former ensures local consistency of the clustering outcome. Algorithmically, excisiveness implies that we can reduce computational complexity by only clustering a data subset of interest while theoretically guaranteeing that the same hierarchical outcome would be observed when clustering the whole dataset. Moreover, we introduce the concept of representability, i.e. a generative model for describing clustering methods through the specification of their action on a collection of networks. We further show that, within a rich set of admissible methods, requiring representability is equivalent to requiring both excisiveness and linear scale preservation. Leveraging this equivalence, we show that all excisive and linear scale preserving methods can be factored into two steps: a transformation of the weights in the input network followed by the application of a canonical clustering method. Furthermore, their factorization can be used to show stability of excisive and linear scale preserving methods in the sense that a bounded perturbation in the input network entails a bounded perturbation in the clustering output.
Characterizing Smartphone Power Management in the Wild
Venue: arXiv cs.OH 2016
Year: 2016

For better reliability and prolonged battery life, it is important that users and vendors understand the quality of charging and the performance of smartphone batteries. Considering the diverse set of devices and user behavior it is a challenge. In this work, we analyze a large collection of battery analytics dataset collected from 30K devices of 1.5K unique smartphone models. We analyze their battery properties and state of charge while charging, and reveal the characteristics of different components of their power management systems: charging mechanisms, state of charge estimation techniques, and their battery properties. We explore diverse charging behavior of devices and their users.
Novel Graph Processor Architecture, Prototype System, and Results
Venue: arXiv cs.DC 2016
Year: 2016

Graph algorithms are increasingly used in applications that exploit large databases. However, conventional processor architectures are inadequate for handling the throughput and memory requirements of graph computation. Lincoln Laboratory's graph-processor architecture represents a rethinking of parallel architectures for graph problems. Our processor utilizes innovations that include a sparse matrix-based graph instruction set, a cacheless memory system, accelerator-based architecture, a systolic sorter, high-bandwidth multi-dimensional toroidal communication network, and randomized communications. A field-programmable gate array (FPGA) prototype of the new graph processor has been developed with significant performance enhancement over conventional processors in graph computational throughput.
Scheduler Technologies in Support of High Performance Data Analysis
Venue: arXiv cs.DC 2016
Year: 2016

Job schedulers are a key component of scalable computing infrastructures. They orchestrate all of the work executed on the computing infrastructure and directly impact the effectiveness of the system. Recently, job workloads have diversified from long-running, synchronously-parallel simulations to include short-duration, independently parallel high performance data analysis (HPDA) jobs. Each of these job types requires different features and scheduler tuning to run efficiently. A number of schedulers have been developed to address both job workload and computing system heterogeneity. High performance computing (HPC) schedulers were designed to schedule large-scale scientific modeling and simulations on supercomputers. Big Data schedulers were designed to schedule data processing and analytic jobs on clusters. This paper compares and contrasts the features of HPC and Big Data schedulers with a focus on accommodating both scientific computing and high performance data analytic workloads. Job latency is critical for the efficient utilization of scalable computing infrastructures, and this paper presents the results of job launch benchmarking of several current schedulers: Slurm, Son of Grid Engine, Mesos, and Yarn. We find that all of these schedulers have low utilization for short-running jobs. Furthermore, employing multilevel scheduling significantly improves the utilization across all schedulers.