OpenRaiser/Intern-Atlas huggingface dataset:
Fast Deterministic Selection
Venue: arXiv cs.DS 2016
Year: 2016

The Median of Medians (also known as BFPRT) algorithm, although a landmark theoretical achievement, is seldom used in practice because it and its variants are slower than simple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection algorithm QuickselectAdaptive based on a refined definition of MedianOfMedians. The algorithm's performance brings deterministic selection---along with its desirable properties of reproducible runs, predictable run times, and immunity to pathological inputs---in the range of practicality. We demonstrate results on independent and identically distributed random inputs and on normally-distributed inputs. Measurements show that QuickselectAdaptive is faster than state-of-the-art baselines.
Program Repair by Stepwise Correctness Enhancement
Venue: arXiv cs.SE 2016
Year: 2016

Relative correctness is the property of a program to be more-correct than another with respect to a given specification. Whereas the traditional definition of (absolute) correctness divides candidate program into two classes (correct, and incorrect), relative correctness arranges candidate programs on the richer structure of a partial ordering. In other venues we discuss the impact of relative correctness on program derivation, and on program verification. In this paper, we discuss the impact of relative correctness on program testing; specifically, we argue that when we remove a fault from a program, we ought to test the new program for relative correctness over the old program, rather than for absolute correctness. We present analytical arguments to support our position, as well as an empirical argument in the form of a small program whose faults are removed in a stepwise manner as its relative correctness rises with each fault removal until we obtain a correct program.
Using Multi-Viewpoint Contracts for Negotiation of Embedded Software Updates
Venue: arXiv cs.SE 2016
Year: 2016

In this paper we address the issue of change after deployment in safety-critical embedded system applications. Our goal is to substitute lab-based verification with in-field formal analysis to determine whether an update may be safely applied. This is challenging because it requires an automated process able to handle multiple viewpoints such as functional correctness, timing, etc. For this purpose, we propose an original methodology for contract-based negotiation of software updates. The use of contracts allows us to cleanly split the verification effort between the lab and the field. In addition, we show how to rely on existing viewpoint-specific methods for update negotiation. We illustrate our approach on a concrete example inspired by the automotive domain.
Massively-Parallel Lossless Data Decompression
Venue: arXiv cs.DC 2016
Year: 2016

Today's exponentially increasing data volumes and the high cost of storage make compression essential for the Big Data industry. Although research has concentrated on efficient compression, fast decompression is critical for analytics queries that repeatedly read compressed data. While decompression can be parallelized somewhat by assigning each data block to a different process, break-through speed-ups require exploiting the massive parallelism of modern multi-core processors and GPUs for data decompression within a block. We propose two new techniques to increase the degree of parallelism during decompression. The first technique exploits the massive parallelism of GPU and SIMD architectures. The second sacrifices some compression efficiency to eliminate data dependencies that limit parallelism during decompression. We evaluate these techniques on the decompressor of the DEFLATE scheme, called Inflate, which is based on LZ77 compression and Huffman encoding. We achieve a 2X speed-up in a head-to-head comparison with several multi-core CPU-based libraries, while achieving a 17% energy saving with comparable compression ratios.
Initial and Eventual Software Quality Relating to Continuous Integration in GitHub
Venue: arXiv cs.SE 2016
Year: 2016

The constant demand for new features and bug fixes are forcing software projects to shorten cycles and deliver updates ever faster, while sustaining software quality. The availability of inexpensive, virtualized, cloud-computing has helped shorten schedules, by enabling continuous integration (CI) on demand. Platforms like GitHub support CI in-the-cloud. In projects using CI, a user submitting a pull request triggers a CI step. Besides speeding up build and test, this fortuitously creates voluminous archives of build and test successes and failures. CI is a relatively new phenomenon, and these archives allow a detailed study of CI. How many problems are exposed? Where do they occur? What factors affect CI failures? Does the "initial quality" as ascertained by CI predict how many bugs will later appear ("eventual quality") in the code? In this paper, we undertake a large-scale, fine resolution study of these records, to better understand CI processes, the nature, and predictors of CI failures, and the relationship of CI failures to the eventual quality of the code. We find that: a) CI failures appear to be concentrated in a few files, just like normal bugs; b) CI failures are not very highly correlated with eventual failures; c) The use of CI in a pull request doesn't necessarily mean the code in that request is of good quality.
Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we tackle the compressive phase retrieval problem in the presence of noise. The noisy compressive phase retrieval problem is to recover a $K$-sparse complex signal $s \in \mathbb{C}^n$, from a set of $m$ noisy quadratic measurements: $ y_i=| a_i^H s |^2+w_i$, where $a_i^H\in\mathbb{C}^n$ is the $i$th row of the measurement matrix $A\in\mathbb{C}^{m\times n}$, and $w_i$ is the additive noise to the $i$th measurement. We consider the regime where $K=βn^δ$, with constants $β>0$ and $δ\in(0,1)$. We use the architecture of PhaseCode algorithm, and robustify it using two schemes: the almost-linear scheme and the sublinear scheme. We prove that with high probability, the almost-linear scheme recovers $s$ with sample complexity $Θ(K \log(n))$ and computational complexity $Θ(n \log(n))$, and the sublinear scheme recovers $s$ with sample complexity $Θ(K\log^3(n))$ and computational complexity $Θ(K\log^3(n))$. To the best of our knowledge, this is the first scheme that achieves sublinear computational complexity for compressive phase retrieval problem. Finally, we provide simulation results that support our theoretical contributions.
Parallel Triangular Solvers on GPU
Venue: arXiv cs.MS 2016
Year: 2016

In this paper, we investigate GPU based parallel triangular solvers systematically. The parallel triangular solvers are fundamental to incomplete LU factorization family preconditioners and algebraic multigrid solvers. We develop a new matrix format suitable for GPU devices. Parallel lower triangular solvers and upper triangular solvers are developed for this new data structure. With these solvers, ILU preconditioners and domain decomposition preconditioners are developed. Numerical results show that we can speed triangular solvers around seven times faster.
Maximum-Quality Tree Construction for Deadline-Constrained Aggregation in WSNs
Venue: arXiv cs.DC 2016
Year: 2016

In deadline-constrained wireless sensor networks (WSNs), quality of aggregation (QoA) is determined by the number of participating nodes in the data aggregation process. The previous studies have attempted to propose optimal scheduling algorithms to obtain the maximum QoA assuming a fixed underlying aggregation tree. However, there exists no prior work to address the issue of constructing optimal aggregation tree in deadline-constraints WSNs. The structure of underlying aggregation tree is important since our analysis demonstrates that the ratio between the maximum achievable QoAs of different trees could be as large as O(2^D), where D is the deadline. This paper casts a combinatorial optimization problem to address optimal tree construction for deadline-constrained data aggregation in WSNs. While the problem is proved to be NP-hard, we employ the recently proposed Markov approximation framework and devise two distributed algorithms with different computation overheads to find close-to-optimal solutions with bounded approximation gap. To further improve the convergence of the proposed Markov-based algorithms, we devise another initial tree construction algorithm with low computational complexity. Our extensive experiments for a set randomly-generated scenarios demonstrate that the proposed algorithms outperforms the existing alternative methods by obtaining better quality of aggregations.
Constrained Phase Noise Estimation in OFDM Using Scattered Pilots Without Decision Feedback
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider an OFDM radio link corrupted by oscillator phase noise in the receiver, namely the problem of estimating and compensating for the impairment. To lessen the computational burden and delay incurred onto the receiver, we estimate phase noise using only scattered pilot subcarriers, i.e., no tentative symbol decisions are used in obtaining and improving the phase noise estimate. In particular, the phase noise estimation problem is posed as an unconstrained optimization problem whose minimizer suffers from the so-called amplitude and phase estimation error. These errors arise due to receiver noise, estimation from limited scattered pilot subcarriers and estimation using a dimensionality reduction model. It is empirically shown that, at high signal-to-noise-ratios, the phase estimation error is small. To reduce the amplitude estimation error, we restrict the minimizer to be drawn from the so-called phase noise geometry set when minimizing the cost function. The resulting optimization problem is a non-convex program. However, using the S-procedure for quadratic equalities, we show that the optimal solution can be obtained by solving the convex dual problem. We also consider a less complex heuristic scheme that achieves the same objective of restricting the minimizer to the phase noise geometry set. Through simulations, we demonstrate improved coded bit-error-rate and phase noise estimation error performance when enforcing the phase noise geometry. For example, at high signal-to-noise-ratios, the probability density function of the phase noise estimation error exhibits thinner tails which results in lower bit-error-rate.
A Multi Perspective Approach for Understanding the Determinants of Cloud Computing Adoption among Australian SMEs
Venue: arXiv cs.CY 2016
Year: 2016

Cloud computing is proved to be an effective computing technology for organisations through the advantages that it offers such as cost-effectiveness, IT technical agility and scalability, enhancing businesses processes, and increasing enterprises competitiveness. In Australia, there is an emerging trend that small and medium-sized enterprises (SMEs) begin to adopt this technology in the conventional working practices. However, there is a dearth of prior studies on examining the factors that influence the cloud computing adoption among Australian SMEs. To fill the empirical vacuum, this research-in-progress proposes an integrated framework for examining the determinants of cloud computing service adoption with the consideration of the unique characteristics of Australian SMEs, such as relatively low adoption of cloud computing services, less innovative, and limited knowledge about cloud computing and its benefits and hindrances. To this end, we are conducting consecutive studies to investigate this research issue. An exploratory interview study will be undertaken to identify and verify the unique characteristics of Australian SMEs toward the cloud computing adoption. This is followed by an organisational level survey that examines the effects of those determinants on cloud computing adoption. Finally, a decision model for cloud computing adoption among Australian SMEs will be developed by using a Multi Criteria Decision Approach (MCDA) through rating, prioritising, and ranking of various criteria and alternatives available to the decision makers. Adopting the mixed-method research fashion, this research-in-progress intends to make significant implications to scholars and practitioners alike in the cloud computing research and applications areas.
Fears and Triggers: A Conceptual Study of Vendor-Supplied Maintenance and Maintenance Deferral of Standard Package Software
Venue: arXiv cs.CY 2016
Year: 2016

Enterprises rely more on Information Systems (IS) and software than ever before. However the issue of maintaining a vendor-supplied IS, in particular standard packaged software, has been poorly represented within academic literature. This paper presents a conceptual study that synthesises the current state of research concerning the deferral or execution of vendor-supplied maintenance by the purchasing organisation. Based on a systematic review process that adopts the purchasers viewpoint, a series of fears and triggers emerge and are captured from the literature. Fears are articulated as reasons for the purchasing organisation deferring the installation of vendor-supplied maintenance, whereas triggers are events that upset the equilibrium of the purchasing organisations IS or software and require the installation of the vendor-supplied maintenance to proceed. Although prevalent in literature, fears and triggers have not previously been recognised as an area of focus for academic research.
Multi-synchronous collaboration between desktop and mobile users: A case study of report writing for emergency management
Venue: arXiv cs.CY 2016
Year: 2016

The development of multi-synchronous decision support systems to facilitate collaboration between diverse users is an emerging field in emergency management. Traditionally, information management for emergency response has been a centralised effort. However, modern devices such as smartphones provide new methods for gaining real-time information about a disaster from users in the field. In this paper, we present a framework for multi-synchronous collaborative report writing in the scope of emergency management. This framework supports desktop-based users as information providers and consumers, alongside mobile users as information providers to facilitate multi-synchronous collaboration. We consider the benefits of our framework for writing collaborative Situation Reports and discuss future directions for research.
Training a Hidden Markov Model with a Bayesian Spiking Neural Network
Venue: arXiv cs.NE 2016
Year: 2016

It is of some interest to understand how statistically based mechanisms for signal processing might be integrated with biologically motivated mechanisms such as neural networks. This paper explores a novel hybrid approach for classifying segments of sequential data, such as individual spoken works. The approach combines a hidden Markov model (HMM) with a spiking neural network (SNN). The HMM, consisting of states and transitions, forms a fixed backbone with nonadaptive transition probabilities. The SNN, however, implements a biologically based Bayesian computation that derives from the spike timing-dependent plasticity (STDP) learning rule. The emission (observation) probabilities of the HMM are represented in the SNN and trained with the STDP rule. A separate SNN, each with the same architecture, is associated with each of the states of the HMM. Because of the STDP training, each SNN implements an expectation maximization algorithm to learn the emission probabilities for one HMM state. The model was studied on synthesized spike-train data and also on spoken word data. Preliminary results suggest its performance compares favorably with other biologically motivated approaches. Because of the model's uniqueness and initial promise, it warrants further study. It provides some new ideas on how the brain might implement the equivalent of an HMM in a neural circuit.
Mobile phone data for public health: towards data-sharing solutions that protect individual privacy and national security
Venue: arXiv cs.OH 2016
Year: 2016

We outline the constraints faced by operators when deciding to share de-identified data with researchers or policy makers. We describe a conservative approach that we have taken to harness the value of CDRs for infectious disease epidemiology while ensuring that identification of individuals is impossible. We believe this approach serves as a useful and highly conservative model for productive partnerships between mobile operators, researchers, and public health practitioners.
How E-Mental Health Services Benefit University Students with ADHD: A literature Review
Venue: arXiv cs.CY 2016
Year: 2016

E-mental health is an area within e-health in which the key role of IS/IT has not been well established. Both clinicians and scholars are uncertain as to the role of IS/IT and its potential benefits. This research review is introduced to assist in understanding the enabling role in e-mental health and it focused on one area of mental health, Attention Deficit Hyperactivity Disorder (ADHD) in university students. ADHD is estimated to affect approximately 6% of university students by negatively impacting students' academic performance and social life; hence, fewer of these students complete their degrees as compared to their peers. This review outlines the potentials of using IS/IT in the treatment of ADHD in university students. It also serves to greatly contribute to e-mental health development and thereby to help to uncover further possibilities of IT/IT to support broad areas within mental health disorders and services.
Aligning Enterprise Systems with the Organisation A Sensemaking Perspective
Venue: arXiv cs.CY 2016
Year: 2016

This paper explores the alignment of enterprise systems and organisations on the post-adoptive phase. A research model is presented focusing on the alignment decisions in the managerial search process for solutions to business problems related to enterprise systems. Based on the research model we propose research questions for future research, particularly to analyse how managerial identity would affect the alignment decisions.
The Effect of ICT Self-Discipline in the Workplace
Venue: arXiv cs.CY 2016
Year: 2016

The ubiquity of Information and Communication Technologies (ICTs) in work settings has changed the way employees behave. ICTs such as smartphones, email and social media makes employees more connected than has ever been possible. The degree of ICT connectivity can create a positive as well as a negative impact on employees' productivity. In this context, the notion of ICT self-discipline - an individual's ability to control their behaviours towards ICTs - becomes pivotal in the process of managing ICT connectivity. This follow-on study reports the results of an online survey of 443 to New Zealand professionals regarding the influence of ICT self-discipline on the relationship between ICT connectivity and employee productivity. Findings indicated that the impact of ICT self-discipline varies depending on the organisation and industry an employee works in. Insights and recommendations for future research are shared in this paper. Findings from this study contribute to IS research and practice.
Graph Clustering with Density-Cut
Venue: arXiv cs.SI 2016
Year: 2016

How can we find a good graph clustering of a real-world network, that allows insight into its underlying structure and also potential functions? In this paper, we introduce a new graph clustering algorithm Dcut from a density point of view. The basic idea is to envision the graph clustering as a density-cut problem, such that the vertices in the same cluster are densely connected and the vertices between clusters are sparsely connected. To identify meaningful clusters (communities) in a graph, a density-connected tree is first constructed in a local fashion. Owing to the density-connected tree, Dcut allows partitioning a graph into multiple densely tight-knit clusters directly. We demonstrate that our method has several attractive benefits: (a) Dcut provides an intuitive criterion to evaluate the goodness of a graph clustering in a more natural and precise way; (b) Built upon the density-connected tree, Dcut allows identifying the meaningful graph clusters of densely connected vertices efficiently; (c) The density-connected tree provides a connectivity map of vertices in a graph from a local density perspective. We systematically evaluate our new clustering approach on synthetic as well as real data to demonstrate its good performance.
Physical Zero-Knowledge Proofs for Akari, Takuzu, Kakuro and KenKen
Venue: arXiv cs.CR 2016
Year: 2016

Akari, Takuzu, Kakuro and KenKen are logic games similar to Sudoku. In Akari, a labyrinth on a grid has to be lit by placing lanterns, respecting various constraints. In Takuzu a grid has to be filled with 0's and 1's, while respecting certain constraints. In Kakuro a grid has to be filled with numbers such that the sums per row and column match given values; similarly in KenKen a grid has to be filled with numbers such that in given areas the product, sum, difference or quotient equals a given value. We give physical algorithms to realize zero-knowledge proofs for these games which allow a player to show that he knows a solution without revealing it. These interactive proofs can be realized with simple office material as they only rely on cards and envelopes. Moreover, we formalize our algorithms and prove their security.
Set-Theoretic Types for Polymorphic Variants
Venue: arXiv cs.PL 2016
Year: 2016

Polymorphic variants are a useful feature of the OCaml language whose current definition and implementation rely on kinding constraints to simulate a subtyping relation via unification. This yields an awkward formalization and results in a type system whose behaviour is in some cases unintuitive and/or unduly restrictive. In this work, we present an alternative formalization of poly-morphic variants, based on set-theoretic types and subtyping, that yields a cleaner and more streamlined system. Our formalization is more expressive than the current one (it types more programs while preserving type safety), it can internalize some meta-theoretic properties, and it removes some pathological cases of the current implementation resulting in a more intuitive and, thus, predictable type system. More generally, this work shows how to add full-fledged union types to functional languages of the ML family that usually rely on the Hindley-Milner type system. As an aside, our system also improves the theory of semantic subtyping, notably by proving completeness for the type reconstruction algorithm.
Packing Coloring of Undirected and Oriented Generalized Theta Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The packing chromatic number $χ$ $ρ$ (G) of an undirected (resp. oriented) graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1,..., V k, in such a way that every two distinct vertices in V i are at distance (resp. directed distance) greater than i in G for every i, 1 $\le$ i $\le$ k. The generalized theta graph $Θ$ {\ell} 1,...,{\ell}p consists in two end-vertices joined by p $\ge$ 2 internally vertex-disjoint paths with respective lengths 1 $\le$ {\ell} 1 $\le$ . . . $\le$ {\ell} p. We prove that the packing chromatic number of any undirected generalized theta graph lies between 3 and max{5, n 3 + 2}, where n 3 = |{i / 1 $\le$ i $\le$ p, {\ell} i = 3}|, and that both these bounds are tight. We then characterize undirected generalized theta graphs with packing chromatic number k for every k $\ge$ 3. We also prove that the packing chromatic number of any oriented generalized theta graph lies between 2 and 5 and that both these bounds are tight.