OpenRaiser/Intern-Atlas huggingface dataset:
Linear Precoding for MIMO Channels with QAM Constellations and Reduced Complexity
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the problem of designing a linear precoder for Multiple-Input Multiple-Output (MIMO) systems in conjunction with Quadrature Amplitude Modulation (QAM) is addressed. First, a novel and efficient methodology to evaluate the input-output mutual information for a general Multiple-Input Multiple-Output (MIMO) system as well as its corresponding gradients is presented, based on the Gauss-Hermite quadrature rule. Then, the method is exploited in a block coordinate gradient ascent optimization process to determine the globally optimal linear precoder with respect to the MIMO input-output mutual information for QAM systems with relatively moderate MIMO channel sizes. The proposed methodology is next applied in conjunction with the complexity-reducing per-group processing (PGP) technique, which is semi-optimal, to both perfect channel state information at the transmitter (CSIT) as well as statistical channel state information (SCSI) scenarios, with high transmitting and receiving antenna size, and for constellation size up to $M=64$. We show by numerical results that the precoders developed offer significantly better performance than the configuration with no precoder, and the maximum diversity precoder for QAM with constellation sizes $M=16,~32$, and $~64$ and for MIMO channel size $100\times100$.
Jump-starting coordination in a stag hunt: Motivation, mechanisms, and their analysis
Venue: arXiv cs.GT 2016
Year: 2016

The stag hunt (or assurance game) is a simple game that has been used as a prototype of a variety of social coordination problems (ranging from the social contract to the adoption of technical standards). Players have the option to either use a superior cooperative strategy whose payoff depends on the other players' choices or use an inferior strategy whose payoff is independent of what other players do; the cooperative strategy may incur a loss if sufficiently many other players do not cooperate. Stag hunts have two (strict) pure Nash equilibria, namely, universal cooperation and universal defection (as well as a mixed equilibrium of low predictive value). Selection of the inferior (pure) equilibrium is called a coordination failure. In this paper, we present and analyze using game-theoretic techniques mechanisms aiming to avert coordination failures and incite instead selection of the superior equilibrium. Our analysis is based on the solution concepts of Nash equilibrium, dominance solvability, as well as a formalization of the notion of "incremental deployability," which is shown to be keenly relevant to the sink equilibrium.
Network Coding as a Service
Venue: arXiv cs.NI 2016
Year: 2016

Network Coding (NC) shows great potential in various communication scenarios through changing the packet forwarding principles of current networks. It can improve not only throughput, latency, reliability and security but also alleviates the need of coordination in many cases. However, it is still controversial due to widespread misunderstandings on how to exploit the advantages of it. The aim of the paper is to facilitate the usage of NC by $(i)$ explaining how it can improve the performance of the network (regardless the existence of any butterfly in the network), $(ii)$ showing how Software Defined Networking (SDN) can resolve the crucial problems of deployment and orchestration of NC elements, and $(iii)$ providing a prototype architecture with measurement results on the performance of our network coding capable software router implementation compared by fountain codes.
Termination of LCTRSs
Venue: arXiv cs.LO 2016
Year: 2016

Logically Constrained Term Rewriting Systems (LCTRSs) provide a general framework for term rewriting with constraints. We discuss a simple dependency pair approach to prove termination of LCTRSs. We see that existing techniques transfer to the constrained setting in a natural way.
Neural Signal Multiplexing via Compressed Sensing
Venue: arXiv cs.IT 2016
Year: 2016

Transport of neural signals in the brain is challenging, owing to neural interference and neural noise. There is experimental evidence of multiplexing of sensory information across population of neurons, particularly in the vertebrate visual and olfactory systems. Recently, it has been discovered that in lateral intraparietal cortex of the brain, decision signals are multiplexed with decision-irrelevant visual signals. Furthermore, it is well known that several cortical neurons exhibit chaotic spiking patterns. Multiplexing of chaotic neural signals and their successful demultiplexing in the neurons amidst interference and noise, is difficult to explain. In this work, a novel compressed sensing model for efficient multiplexing of chaotic neural signals constructed using the Hindmarsh-Rose spiking model is proposed. The signals are multiplexed from a pre-synaptic neuron to its neighbouring post-synaptic neuron, in the presence of $10^4$ interfering noisy neural signals and demultiplexed using compressed sensing techniques.
PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions
Venue: arXiv cs.DB 2016
Year: 2016

Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. This leads to inferior data utility due to the following dilemma: if we use a small h, then the resulting histogram would be too coarse-grained to provide an accurate approximation of data distribution; meanwhile, a large h would yield a fine-grained histogram, but its quality would be severely degraded by the increased amount of noise in the tuple counts. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that also applies hierarchical decomposition but features a crucial (and somewhat surprising) improvement: when deciding whether or not to split a sub-domain, the amount of noise required in the corresponding tuple count is independent of the recursive depth. This enables PrivTree to adaptively generate high-quality histograms without even asking for a pre-defined threshold on the depth of sub-domain splitting. As concrete examples, we demonstrate an application of PrivTree in modelling spatial data, and show that it can also be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree significantly outperforms the states of the art in terms of data utility.
Digital Image Forensics vs. Image Composition: An Indirect Arms Race
Venue: arXiv cs.CV 2016
Year: 2016

The field of image composition is constantly trying to improve the ways in which an image can be altered and enhanced. While this is usually done in the name of aesthetics and practicality, it also provides tools that can be used to maliciously alter images. In this sense, the field of digital image forensics has to be prepared to deal with the influx of new technology, in a constant arms-race. In this paper, the current state of this arms-race is analyzed, surveying the state-of-the-art and providing means to compare both sides. A novel scale to classify image forensics assessments is proposed, and experiments are performed to test composition techniques in regards to different forensics traces. We show that even though research in forensics seems unaware of the advanced forms of image composition, it possesses the basic tools to detect it.
Improved Algorithmic Bounds for Discrepancy of Sparse Set Systems
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of finding a low discrepancy coloring for sparse set systems where each element lies in at most $t$ sets. We give an algorithm that finds a coloring with discrepancy $O((t \log n \log s)^{1/2})$ where $s$ is the maximum cardinality of a set. This improves upon the previous constructive bound of $O(t^{1/2} \log n)$ based on algorithmic variants of the partial coloring method, and for small $s$ (e.g.$s=\textrm{poly}(t)$) comes close to the non-constructive $O((t \log n)^{1/2})$ bound due to Banaszczyk. Previously, no algorithmic results better than $O(t^{1/2}\log n)$ were known even for $s = O(t^2)$. Our method is quite robust and we give several refinements and extensions. For example, the coloring we obtain satisfies the stronger size-sensitive property that each set $S$ in the set system incurs an $O((t \log n \log |S|)^{1/2})$ discrepancy. Another variant can be used to essentially match Banaszczyk's bound for a wide class of instances even where $s$ is arbitrarily large. Finally, these results also extend directly to the more general Komlós setting.
EvoGrader: an online formative assessment tool for automatically evaluating written evolutionary explanations
Venue: arXiv cs.CL 2016
Year: 2016

EvoGrader is a free, online, on-demand formative assessment service designed for use in undergraduate biology classrooms. EvoGrader's web portal is powered by Amazon's Elastic Cloud and run with LightSIDE Lab's open-source machine-learning tools. The EvoGrader web portal allows biology instructors to upload a response file (.csv) containing unlimited numbers of evolutionary explanations written in response to 86 different ACORNS (Assessing COntextual Reasoning about Natural Selection) instrument items. The system automatically analyzes the responses and provides detailed information about the scientific and naive concepts contained within each student's response, as well as overall student (and sample) reasoning model types. Graphs and visual models provided by EvoGrader summarize class-level responses; downloadable files of raw scores (in .csv format) are also provided for more detailed analyses. Although the computational machinery that EvoGrader employs is complex, using the system is easy. Users only need to know how to use spreadsheets to organize student responses, upload files to the web, and use a web browser. A series of experiments using new samples of 2,200 written evolutionary explanations demonstrate that EvoGrader scores are comparable to those of trained human raters, although EvoGrader scoring takes 99% less time and is free. EvoGrader will be of interest to biology instructors teaching large classes who seek to emphasize scientific practices such as generating scientific explanations, and to teach crosscutting ideas such as evolution and natural selection. The software architecture of EvoGrader is described as it may serve as a template for developing machine-learning portals for other core concepts within biology and across other disciplines.
A Constraint Satisfaction Method for Configuring Non-Local Service Interfaces
Venue: arXiv cs.LO 2016
Year: 2016

Modularity and decontextualisation are core principles of a service-oriented architecture. However, the principles are often lost when it comes to an implementation of services, as a result of a rigidly defined service interface. The interface, which defines a data format, is typically specific to a particular context and its change entails significant redevelopment costs. This paper focuses on a two-fold problem. On the one hand, the interface description language must be flexible enough for maintaining service compatibility in a variety of different contexts without modification of the service itself. On the other hand, the composition of interfaces in a distributed environment must be provably consistent. The existing approaches for checking compatibility of service choreographies are either inflexible (WS-CDL and WSCI) or require behaviour specification associated with each service, which is often impossible to provide in practice. We present a novel approach for automatic interface configuration in distributed stream-connected components operating as closed-source services (i.e. the behavioural protocol is unknown). We introduce a Message Definition Language (MDL), which can extend the existing interfaces description languages, such as WSDL, with support of subtyping, inheritance and polymorphism. The MDL supports configuration variables that link input and output interfaces of a service and propagate requirements over an application graph. We present an algorithm that solves the interface reconciliation problem using constraint satisfaction that relies on Boolean satisfiability as a subproblem.
Greedy-Knapsack Algorithm for Optimal Downlink Resource Allocation in LTE Networks
Venue: arXiv cs.NI 2016
Year: 2016

The Long Term Evolution (LTE) as a mobile broadband technology supports a wide domain of communication services with different requirements. Therefore, scheduling of all flows from various applications in overload states in which the requested amount of bandwidth exceeds the limited available spectrum resources is a challenging issue. Accordingly, in this paper, a greedy algorithm is presented to evaluate user candidates which are waiting for scheduling and select an optimal set of the users to maximize system performance, without exceeding available bandwidth capacity. The greedy-knapsack algorithm is defined as an optimal solution to the resource allocation problem, formulated based on the fractional knapsack problem. A compromise between throughput and QoS provisioning is obtained by proposing a class-based ranking function, which is a combination of throughput and QoS related parameters defined for each application. The simulation results show that the proposed method provides high performance in terms of throughput, loss and delay for different classes of QoS over the existing ones, especially under overload traffic.
Dynamic Privacy For Distributed Machine Learning Over Network
Venue: arXiv cs.LG 2016
Year: 2016

Privacy-preserving distributed machine learning becomes increasingly important due to the recent rapid growth of data. This paper focuses on a class of regularized empirical risk minimization (ERM) machine learning problems, and develops two methods to provide differential privacy to distributed learning algorithms over a network. We first decentralize the learning algorithm using the alternating direction method of multipliers (ADMM), and propose the methods of dual variable perturbation and primal variable perturbation to provide dynamic differential privacy. The two mechanisms lead to algorithms that can provide privacy guarantees under mild conditions of the convexity and differentiability of the loss function and the regularizer. We study the performance of the algorithms, and show that the dual variable perturbation outperforms its primal counterpart. To design an optimal privacy mechanisms, we analyze the fundamental tradeoff between privacy and accuracy, and provide guidelines to choose privacy parameters. Numerical experiments using customer information database are performed to corroborate the results on privacy and utility tradeoffs and design.
Similarity-First Search: a new algorithm with application to Robinsonian matrix recognition
Venue: arXiv cs.DM 2016
Year: 2016

We present a new efficient combinatorial algorithm for recognizing if a given symmetric matrix is Robinsonian, i.e., if its rows and columns can be simultaneously reordered so that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. As main ingredient we introduce a new algorithm, named Similarity-First-Search (SFS), which extends Lexicographic Breadth-First Search (Lex-BFS) to weighted graphs and which we use in a multisweep algorithm to recognize Robinsonian matrices. Since Robinsonian binary matrices correspond to unit interval graphs, our algorithm can be seen as a generalization to weighted graphs of the 3-sweep Lex-BFS algorithm of Corneil for recognizing unit interval graphs. This new recognition algorithm is extremely simple and it exploits new insight on the combinatorial structure of Robinsonian matrices. For an $n\times n$ nonnegative matrix with $m$ nonzero entries, it terminates in $n-1$ SFS sweeps, with overall running time $O(n^2 +nm\log n)$.
A Taxonomy for Tools, Processes and Languages in Automotive Software Engineering
Venue: arXiv cs.SE 2016
Year: 2016

Within the growing domain of software engineering in the automotive sector, the number of used tools, processes, methods and languages has increased distinctly in the past years. To be able to choose proper methods for particular development use cases, factors like the intended use, key-features and possible limitations have to be evaluated. This requires a taxonomy that aids the decision making. An analysis of the main existing taxonomies revealed two major deficiencies: the lack of the automotive focus and the limitation to particular engineering method types. To face this, a graphical taxonomy is proposed based on two well-established engineering approaches and enriched with additional classification information. It provides a self-evident and -explanatory overview and comparison technique for engineering methods in the automotive domain. The taxonomy is applied to common automotive engineering methods. The resulting diagram classifies each method and enables the reader to select appropriate solutions for given project requirements.
Arbitrary Overlap Constraints in Graph Packing Problems
Venue: arXiv cs.DS 2016
Year: 2016

In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound [17,5,11,8]. In this paper, we introduce the $Π$-Packing with $α()$-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let $\mathcal{V}^r$ be all possible subsets of vertices of $V(G)$ each of size at most $r$, and $α: \mathcal{V}^r \times \mathcal{V}^r \to \{0,1\}$ be a function. The $Π$-Packing with $α()$-Overlap problem seeks at least $k$ induced subgraphs in a graph $G$ subject to: (i) each subgraph has at most $r$ vertices and obeys a property $Π$, and (ii) for any pair $H_i,H_j$, with $i\neq j$, $α(H_i, H_j) = 0$ (i.e., $H_i,H_j$ do not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets $\mathcal{C}$, and no pair of subgraphs may share vertices from the sets of $\mathcal{C}$. In addition, we propose similar formulations for packing hypergraphs. We give an $O(r^{rk} k^{(r+1)k} n^{cr})$ algorithm for our problems where $k$ is the parameter and $c$ and $r$ are constants, provided that: i) $Π$ is computable in polynomial time in $n$ and ii) the function $α()$ satisfies specific conditions. Specifically, $α()$ is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in $n$. Motivated by practical applications we give several examples of $α()$ functions which meet those conditions.
Benchmarking, System Design and Case-studies for Multi-core based Embedded Automotive Systems
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, using of automotive use cases as benchmarks for real-time system design has been proposed. The use cases are described in a format supported by AMALTHEA platform, which is a model based open source development environment for automotive multi-core systems. An example of a simple Electronic Control Unit has been analysed and presented with enough details to reconstruct this system in any format. For researchers willing to use AMALTHEA file format directly, an appropriate parser has been developed and offered. An example of applying this parser and benchmark for optimising makespan while not violating the timing constraints by allocating functionality to different Network on Chip resource is demonstrated.
ActiveClean: Interactive Data Cleaning While Learning Convex Loss Models
Venue: arXiv cs.DB 2016
Year: 2016

Data cleaning is often an important step to ensure that predictive models, such as regression and classification, are not affected by systematic errors such as inconsistent, out-of-date, or outlier data. Identifying dirty data is often a manual and iterative process, and can be challenging on large datasets. However, many data cleaning workflows can introduce subtle biases into the training processes due to violation of independence assumptions. We propose ActiveClean, a progressive cleaning approach where the model is updated incrementally instead of re-training and can guarantee accuracy on partially cleaned data. ActiveClean supports a popular class of models called convex loss models (e.g., linear regression and SVMs). ActiveClean also leverages the structure of a user's model to prioritize cleaning those records likely to affect the results. We evaluate ActiveClean on five real-world datasets UCI Adult, UCI EEG, MNIST, Dollars For Docs, and WorldBank with both real and synthetic errors. Our results suggest that our proposed optimizations can improve model accuracy by up-to 2.5x for the same amount of data cleaned. Furthermore for a fixed cleaning budget and on all real dirty datasets, ActiveClean returns more accurate models than uniform sampling and Active Learning.
Virtual Machine Migration Enabled Cloud Resource Management: A Challenging Task
Venue: arXiv cs.DC 2016
Year: 2016

Virtualization technology reduces cloud operational cost by increasing cloud resource utilization level. The incorporation of virtualization within cloud data centers can severely degrade cloud performance if not properly managed. Virtual machine (VM) migration is a method that assists cloud service providers to efficiently manage cloud resources while eliminating the need of human supervision. VM migration methodology migrates current-hosted workload from one server to another by either employing live or non-live migration pattern. In comparison to non-live migration, live migration does not suspend application services prior to VM migration process. VM migration enables cloud operators to achieve various resource management goals, such as, green computing, load balancing, fault management, and real time server maintenance. In this paper, we have thoroughly surveyed VM migration methods and applications. We have briefly discussed VM migration applications. Some open research issues have been highlighted to represent future challenges in this domain. A queue based migration model has been proposed and discussed to efficiently migrate VM memory pages.
Human Behaviour as an aspect of Cyber Security Assurance
Venue: arXiv cs.CR 2016
Year: 2016

There continue to be numerous breaches publicised pertaining to cyber security despite security practices being applied within industry for many years. This article is intended to be the first in a number of articles as research into cyber security assurance processes. This article is compiled based on current research related to cyber security assurance and the impact of the human element on it. The objective of this work is to identify elements of cyber security that would benefit from further research and development based on the literature review findings. The results outlined in this article present a need for the cyber security field to look in to established industry areas to benefit from effective practices such as human reliability assessment, along with improved methods of validation such as statistical quality control in order to obtain true assurance. The article proposes the development of a framework that will be based upon defined and repeatable quantification, specifically relating to the range of human aspect tasks that provide, or are intended not to negatively affect cyber security posture.