OpenRaiser/Intern-Atlas huggingface dataset:
Healthcare IT: Is your Information at Risk?
Venue: arXiv cs.CR 2015
Year: 2015

Healthcare Information Technology (IT) has made great advances over the past few years and while these advances have enable healthcare professionals to provide higher quality healthcare to a larger number of individuals it also provides the criminal element more opportunities to access sensitive information, such as patient protected health information (PHI) and Personal identification Information (PII). Having an Information Assurance (IA) programallows for the protection of information and information systems and ensures the organization is in compliance with all requires regulations, laws and directive is essential. While most organizations have such a policy in place, often it is inadequate to ensure the proper protection to prevent security breaches. The increase of data breaches in the last few years demonstrates the importance of an effective IA program. To ensure an effective IA policy, the policy must manage the operational risk, including identifying risks, assessment and mitigation of identified risks and ongoing monitoring to ensure compliance
Fast Algorithms for Game-Theoretic Centrality Measures
Venue: arXiv cs.GT 2015
Year: 2015

In this dissertation, we analyze the computational properties of game-theoretic centrality measures. The key idea behind game-theoretic approach to network analysis is to treat nodes as players in a cooperative game, where the value of each coalition of nodes is determined by certain graph properties. Next, the centrality of any individual node is determined by a chosen game-theoretic solution concept (notably, the Shapley value) in the same way as the payoff of a player in a cooperative game. On one hand, the advantage of game-theoretic centrality measures is that nodes are ranked not only according to their individual roles but also according to how they contribute to the role played by all possible subsets of nodes. On the other hand, the disadvantage is that the game-theoretic solution concepts are typically computationally challenging. The main contribution of this dissertation is that we show that a wide variety of game-theoretic solution concepts on networks can be computed in polynomial time. Our focus is on centralities based on the Shapley value and its various extensions, such as the Semivalues and Coalitional Semivalues. Furthermore, we prove #P-hardness of computing the Shapley value in connectivity games and propose an algorithm to compute it. Finally, we analyse computational properties of generalized version of cooperative games in which order of player matters. We propose a new representation for such games, called generalized marginal contribution networks, that allows for polynomial computation in the size of the representation of two dedicated extensions of the Shapley value to this class of games.
GreenInfra: Capacity of Large-Scale Hybrid Networks With Cost-Effective Infrastructure
Venue: arXiv cs.IT 2015
Year: 2015

The cost-effective impact and fundamental limits of infrastructure support with rate-limited wired backhaul links (i.e., GreenInfra support), directly connecting base stations (BSs), are analyzed in a large-scale hybrid network of unit node density, where multi-antenna BSs are deployed. We consider a general scenario such that the rate of each BS-to-BS link scales at an arbitrary rate relative to the number of randomly located wireless nodes, $n$. For the operating regimes with respect to the number of BSs and the number of antennas at each BS, we first analyze the minimum rate of each backhaul link, $C_{\textrm{BS}}$, required to guarantee the same throughput scaling as in the infinite-capacity backhaul link case. We then identify the operating regimes in which the required rate $C_{\textrm{BS}}$ scales slower than $n^ε$ for an arbitrarily small $ε>0$ (i.e., the regimes where $C_{\textrm{BS}}$ does not need to be infinitely large). We also show the case where our network with GreenInfra is fundamentally in the infrastructure-limited regime, in which the performance is limited by the rate of backhaul links. In addition, we derive a generalized throughput scaling law including the case where the rate of each backhaul link scales slower than $C_{\textrm{BS}}$. To validate the throughput scaling law for finite values of system parameters, numerical evaluation is also shown via computer simulations.
Image reconstruction from dense binary pixels
Venue: arXiv cs.CV 2015
Year: 2015

Recently, the dense binary pixel Gigavision camera had been introduced, emulating a digital version of the photographic film. While seems to be a promising solution for HDR imaging, its output is not directly usable and requires an image reconstruction process. In this work, we formulate this problem as the minimization of a convex objective combining a maximum-likelihood term with a sparse synthesis prior. We present MLNet - a novel feed-forward neural network, producing acceptable output quality at a fixed complexity and is two orders of magnitude faster than iterative algorithms. We present state of the art results in the abstract.
Approximate nearest neighbor search for $\ell_p$-spaces ($2 < p < \infty$) via embeddings
Venue: arXiv cs.CG 2015
Year: 2015

While the problem of approximate nearest neighbor search has been well-studied for Euclidean space and $\ell_1$, few non-trivial algorithms are known for $\ell_p$ when ($2 < p < \infty$). In this paper, we revisit this fundamental problem and present approximate nearest-neighbor search algorithms which give the first non-trivial approximation factor guarantees in this setting.
On Routing Disjoint Paths in Bounded Treewidth Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We study the problem of routing on disjoint paths in bounded treewidth graphs with both edge and node capacities. The input consists of a capacitated graph $G$ and a collection of $k$ source-destination pairs $\mathcal{M} = \{(s_1, t_1), \dots, (s_k, t_k)\}$. The goal is to maximize the number of pairs that can be routed subject to the capacities in the graph. A routing of a subset $\mathcal{M}'$ of the pairs is a collection $\mathcal{P}$ of paths such that, for each pair $(s_i, t_i) \in \mathcal{M}'$, there is a path in $\mathcal{P}$ connecting $s_i$ to $t_i$. In the Maximum Edge Disjoint Paths (MaxEDP) problem, the graph $G$ has capacities $\mathrm{cap}(e)$ on the edges and a routing $\mathcal{P}$ is feasible if each edge $e$ is in at most $\mathrm{cap}(e)$ of the paths of $\mathcal{P}$. The Maximum Node Disjoint Paths (MaxNDP) problem is the node-capacitated counterpart of MaxEDP. In this paper we obtain an $O(r^3)$ approximation for MaxEDP on graphs of treewidth at most $r$ and a matching approximation for MaxNDP on graphs of pathwidth at most $r$. Our results build on and significantly improve the work by Chekuri et al. [ICALP 2013] who obtained an $O(r \cdot 3^r)$ approximation for MaxEDP.
Designing Applications in a Hybrid Cloud
Venue: arXiv cs.DC 2015
Year: 2015

Designing applications for hybrid cloud has many features, including dynamic virtualization management and route switching. This makes it impossible to evaluate the query and hence the optimal distribution of data. In this paper, we formulate the main challenges of designing and simulation, offer installation for processing.
Fixation prediction with a combined model of bottom-up saliency and vanishing point
Venue: arXiv cs.CV 2015
Year: 2015

By predicting where humans look in natural scenes, we can understand how they perceive complex natural scenes and prioritize information for further high-level visual processing. Several models have been proposed for this purpose, yet there is a gap between best existing saliency models and human performance. While many researchers have developed purely computational models for fixation prediction, less attempts have been made to discover cognitive factors that guide gaze. Here, we study the effect of a particular type of scene structural information, known as the vanishing point, and show that human gaze is attracted to the vanishing point regions. We record eye movements of 10 observers over 532 images, out of which 319 have vanishing points. We then construct a combined model of traditional saliency and a vanishing point channel and show that our model outperforms state of the art saliency models using three scores on our dataset.
Continuous integration in a social-coding world: Empirical evidence from GitHub. **Updated version with corrections**
Venue: arXiv cs.SE 2015
Year: 2015

Continuous integration is a software engineering practice of frequently merging all developer working copies with a shared main branch, e.g., several times a day. With the advent of GitHub, a platform well known for its "social coding" features that aid collaboration and sharing, and currently the largest code host in the open source world, collaborative software development has never been more prominent. In GitHub development one can distinguish between two types of developer contributions to a project: direct ones, coming from a typically small group of developers with write access to the main project repository, and indirect ones, coming from developers who fork the main repository, update their copies locally, and submit pull requests for review and merger. In this paper we explore how GitHub developers use continuous integration as well as whether the contribution type (direct versus indirect) and different project characteristics (e.g., main programming language, or project age) are associated with the success of the automatic builds.
Probabilistic Structural Controllability in Causal Bayesian Networks
Venue: arXiv cs.AI 2015
Year: 2015

Humans routinely confront the following key question which could be viewed as a probabilistic variant of the controllability problem: While faced with an uncertain environment governed by causal structures, how should they practice their autonomy by intervening on driver variables, in order to increase (or decrease) the probability of attaining their desired (or undesired) state for some target variable? In this paper, for the first time, the problem of probabilistic controllability in Causal Bayesian Networks (CBNs) is studied. More specifically, the aim of this paper is two-fold: (i) to introduce and formalize the problem of probabilistic structural controllability in CBNs, and (ii) to identify a sufficient set of driver variables for the purpose of probabilistic structural controllability of a generic CBN. We also elaborate on the nature of minimality the identified set of driver variables satisfies. In this context, the term "structural" signifies the condition wherein solely the structure of the CBN is known.
Risk Minimization in Structured Prediction using Orbit Loss
Venue: arXiv cs.LG 2015
Year: 2015

We introduce a new surrogate loss function called orbit loss in the structured prediction framework, which has good theoretical and practical advantages. While the orbit loss is not convex, it has a simple analytical gradient and a simple perceptron-like learning rule. We analyze the new loss theoretically and state a PAC-Bayesian generalization bound. We also prove that the new loss is consistent in the strong sense; namely, the risk achieved by the set of the trained parameters approaches the infimum risk achievable by any linear decoder over the given features. Methods that are aimed at risk minimization, such as the structured ramp loss, the structured probit loss and the direct loss minimization require at least two inference operations per training iteration. In this sense, the orbit loss is more efficient as it requires only one inference operation per training iteration, while yields similar performance. We conclude the paper with an empirical comparison of the proposed loss function to the structured hinge loss, the structured ramp loss, the structured probit loss and the direct loss minimization method on several benchmark datasets and tasks.
Level-Based Analysis of Genetic Algorithms for Combinatorial Optimization
Venue: arXiv cs.NE 2015
Year: 2015

The paper is devoted to upper bounds on run-time of Non-Elitist Genetic Algorithms until some target subset of solutions is visited for the first time. In particular, we consider the sets of optimal solutions and the sets of local optima as the target subsets. Previously known upper bounds are improved by means of drift analysis. Finally, we propose conditions ensuring that a Non-Elitist Genetic Algorithm efficiently finds approximate solutions with constant approximation ratio on the class of combinatorial optimization problems with guaranteed local optima (GLO).
Evaluation of Energy-Efficient Heuristics for ACO-based Routing in Mobile Wireless Sensor Networks
Venue: arXiv cs.NI 2015
Year: 2015

Mobile ad-hoc networks demand routing algorithms able to adapt to network topologies subject to constant change. Moreover, with the advent of the Internet-of-Things (IoT), network nodes tend not only to show increased mobility, but also impose further restrictions to these mobile network systems. These restrictions include non-functional requirements of low-power consumption, small-size, and low-cost. ADHOP (Ant-based Dynamic Hop Optimization Protocol) is a routing algorithm based on ant-colony optimizations that target such small-size and low-cost platforms, consuming little amounts of memory and processing power. This paper elaborates on ADHOP to investigate the use of energy-related heuristics to guide routing decisions. The goal is to minimize network usage without jeopardizing network operation. We replace the original ADHOP heuristic of network latency by two energy-related heuristics based on the battery charge and the estimated node lifetime. Simulations compare the energy-aware versions of ADHOP to its original version, to AODV and to AOER. Results show that the proposed approaches are able to balance network load among nodes, resulting in a lower number of failures due to battery depletion. The energy-aware versions of ADHOP also deliver more packets than their counter-parts in the simulated scenario, delivering 2x more packets than the original ADHOP, and, respectively, 5x and 9x more packets than AOER and AODV.
FabSim: facilitating computational research through automation on large-scale and distributed e-infrastructures
Venue: arXiv cs.DC 2015
Year: 2015

We present FabSim, a toolkit developed to simplify a range of computational tasks for researchers in diverse disciplines. FabSim is flexible, adaptable, and allows users to perform a wide range of tasks with ease. It also provides a systematic way to automate the use of resourcess, including HPC and distributed resources, and to make tasks easier to repeat by recording contextual information. To demonstrate this, we present three use cases where FabSim has enhanced our research productivity. These include simulating cerebrovascular bloodflow, modelling clay-polymer nanocomposites across multiple scales, and calculating ligand-protein binding affinities.
Approximation algorithms for the two-center problem of convex polygon
Venue: arXiv cs.CG 2015
Year: 2015

Given a convex polygon $P$ with $n$ vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover $P$. We propose an algorithm for this problem in the streaming setup, where the input stream is the vertices of the polygon in clockwise order. It produces a radius $r$ satisfying $r\leq2r_{opt}$ using $O(1)$ space, where $r_{opt}$ is the optimum solution. Next, we show that in non-streaming setup, we can improve the approximation factor by $r\leq 1.84 r_{opt}$, maintaining the time complexity of the algorithm to $O(n)$, and using $O(1)$ extra space in addition to the space required for storing the input.
Even and Odd Cycles Passing a Given Edge or a Vertex
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we provide some sufficient conditions for the existence of an odd or even cycle that passing a given vertex or an edge in $2$-connected or $2$-edge connected graphs. We provide some similar conditions for the existence of an odd or even circuit that passing a given vertex or an edge in 2-edge connected graphs. We show that if $G$ is a $2$-connected $k$-regular graph, $k \geq 3$, then every edge of $G$ is contained in an even cycle. We also prove that in a $2$-edge connected graph, if a vertex has odd degree, then there is an even cycle containing this vertex.
Study of Structured Root-LDPC Codes and PEG Techniques for Block-Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we propose structured Root-Low-Density Parity-Check (LDPC) codes and design techniques for block-fading channels. In particular, Quasi-Cyclic Root-LDPC codes, Irregular repeat-accumulate Root-LDPC codes and Controlled Doping Root-LDPC codes based on Progressive Edge Growth (PEG) techniques for block-fading channels are proposed. The proposed Root-LDPC codes are both suitable for channels under $F = 2, 3$ and $4$ independent fading per codeword. The performance of the proposed codes is investigated in terms of Frame Error Rate (FER). The proposed Root-LDPC codes are capable of achieving the channel diversity and outperform standard LDPC codes. For block-fading channel with $F = 2$ our proposed PEG-based Root-LDPC codes outperform PEG-based LDPC codes by $7.5$dB at a FER close to $10^{-3}$.
Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
Venue: arXiv cs.CL 2015
Year: 2015

We show that an end-to-end deep learning approach can be used to recognize either English or Mandarin Chinese speech--two vastly different languages. Because it replaces entire pipelines of hand-engineered components with neural networks, end-to-end learning allows us to handle a diverse variety of speech including noisy environments, accents and different languages. Key to our approach is our application of HPC techniques, resulting in a 7x speedup over our previous system. Because of this efficiency, experiments that previously took weeks now run in days. This enables us to iterate more quickly to identify superior architectures and algorithms. As a result, in several cases, our system is competitive with the transcription of human workers when benchmarked on standard datasets. Finally, using a technique called Batch Dispatch with GPUs in the data center, we show that our system can be inexpensively deployed in an online setting, delivering low latency when serving users at scale.
The Ethics of Hacking: Should It Be Taught?
Venue: arXiv cs.CY 2015
Year: 2015

Poor software quality can adversely affect application security by increasing the potential for a malicious breach of a system. Because computer security and cybersecurity are becoming such relevant topics for practicing software engineers, the need for educational opportunities in this area is steadily increasing. Universities and colleges have recognized this, and have started to offer programs in cybersecurity. At face value, these new programs may not appear controversial, but developing their curriculum requires answering a complex ethical question: Should programs teach hacking to their students? Even though there are different types of hackers, media reports of cybersecurity incidents tend to reserve the "hacker" label for cyber criminals, which overlooks the value in hacking (and, by extension, teaching students to hack). This article examines the full spectrum of hacking behavior, as well as arguments for and against including hacking in education programs, and recommends that hacking skills be considered an essential component of an education and practice in software quality assurance.
Formal Proofs of Transcendence for e and $π$ as an Application of Multivariate and Symmetric Polynomials
Venue: arXiv cs.LO 2015
Year: 2015

We describe the formalisation in Coq of a proof that the numbers e and $π$ are transcendental. This proof lies at the interface of two domains of mathematics that are often considered separately: calculus (real and elementary complex analysis) and algebra. For the work on calculus, we rely on the Coquelicot library and for the work on algebra, we rely on the Mathematical Components library. Moreover, some of the elements of our formalized proof originate in the more ancient library for real numbers included in the Coq distribution. The case of $π$ relies extensively on properties of multivariate polynomials and this experiment was also an occasion to put to test a newly developed library for these multivariate polynomials.
Reduced Complexity Detection for Network-Coded Slotted ALOHA using Sphere Decoding
Venue: arXiv cs.IT 2015
Year: 2015

Network-coded slotted ALOHA (NCSA) is a re- finement to the classic slotted ALOHA protocol which im- proves throughput by enabling multiple source transmissions per ALOHA slot using physical-layer network coding (PNC). The receiver detects the network-coded combination of bits during every slot and recovers information bits by solving a system of linear equations. This work develops a receiver capable of detecting the network-coded combination of bits during a slot considering an arbitrary number of sources, orthogonal modulation, and a block fading channel. Maximum-likelihood detection of the network-coded symbol at the receiver becomes complex as the number of sources is increased. To reduce this complexity, sphere decoding is applied at the receiver to limit the number of constellation symbols the receiver must consider for detection. The system is simulated for two modulation orders and two through five sources, and error-rate performance results are provided.
Bigger Buffer k-d Trees on Multi-Many-Core Systems
Venue: arXiv cs.DC 2015
Year: 2015

A buffer k-d tree is a k-d tree variant for massively-parallel nearest neighbor search. While providing valuable speed-ups on modern many-core devices in case both a large number of reference and query points are given, buffer k-d trees are limited by the amount of points that can fit on a single device. In this work, we show how to modify the original data structure and the associated workflow to make the overall approach capable of dealing with massive data sets. We further provide a simple yet efficient way of using multiple devices given in a single workstation. The applicability of the modified framework is demonstrated in the context of astronomy, a field that is faced with huge amounts of data.
Video captioning with recurrent networks based on frame- and video-level features and visual content classification
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we describe the system for generating textual descriptions of short video clips using recurrent neural networks (RNN), which we used while participating in the Large Scale Movie Description Challenge 2015 in ICCV 2015. Our work builds on static image captioning systems with RNN based language models and extends this framework to videos utilizing both static image features and video-specific features. In addition, we study the usefulness of visual content classifiers as a source of additional information for caption generation. With experimental results we show that utilizing keyframe based features, dense trajectory video features and content classifier outputs together gives better performance than any one of them individually.