OpenRaiser/Intern-Atlas huggingface dataset:
Sequences with small correlation
Venue: arXiv cs.IT 2016
Year: 2016

The extent to which a sequence of finite length differs from a shifted version of itself is measured by its aperiodic autocorrelations. Of particular interest are sequences whose entries are 1 or -1, called binary sequences, and sequences whose entries are complex numbers of unit magnitude, called unimodular sequences. Since the 1950s, there is sustained interest in sequences with small aperiodic autocorrelations relative to the sequence length. One of the main motivations is that a sequence with small aperiodic autocorrelations is intrinsically suited for the separation of signals from noise, and therefore has natural applications in digital communications. This survey reviews the state of knowledge concerning the two central problems in this area: How small can the aperiodic autocorrelations of a binary or a unimodular sequence collectively be and how can we efficiently find the best such sequences? Since the analysis and construction of sequences with small aperiodic autocorrelations is closely tied to the (often much easier) analysis of periodic autocorrelation properties, several fundamental results on corresponding problems in the periodic setting are also reviewed.
A Language for the Declarative Composition of Concurrent Protocols
Venue: arXiv cs.PL 2016
Year: 2016

A recent study of bugs in real-world concurrent and distributed systems found that, while implementations of individual protocols tend to be robust, the composition of multiple protocols and its interplay with internal computation is the culprit for most errors. Multiparty Session Types and Choreographic Programming are methodologies for developing correct-by-construction concurrent and distributed software, based on global descriptions of communication flows. However, protocol composition is either limited or left unchecked. Inspired by these two methodologies, in this work we present a new language model for the safe composition of protocols, called Procedural Choreographies (PC). Protocols in PC are procedures, parameterised on the processes that enact them. Procedures define communications declaratively using global descriptions, and programs are written by invoking and composing these procedures. An implementation in terms of a process model is then mechanically synthesised, guaranteeing correctness and deadlock-freedom. We study PC in the settings of synchronous and asynchronous communications, and illustrate its expressivity with some representative examples.
Hitting Families of Schedules for Asynchronous Programs
Venue: arXiv cs.DM 2016
Year: 2016

We consider the following basic task in the testing of concurrent systems. The input to the task is a partial order of events, which models actions performed on or by the system and specifies ordering constraints between them. The task is to determine if some scheduling of these events can result in a bug. The number of schedules to be explored can, in general, be exponential. Empirically, many bugs in concurrent programs have been observed to have small bug depth; that is, these bugs are exposed by every schedule that orders $d$ specific events in a particular way, irrespective of how the other events are ordered, and $d$ is small compared to the total number of events. To find all bugs of depth $d$, one needs to only test a $d$-hitting family of schedules: we call a set of schedules a $d$-hitting family if for each set of $d$ events, and for each allowed ordering of these events, there is some schedule in the family that executes these events in this ordering. The size of a $d$-hitting family may be much smaller than the number of all possible schedules, and a natural question is whether one can find $d$-hitting families of schedules that have small size. In general, finding the size of optimal $d$-hitting families is hard, even for $d=2$. We show, however, that when the partial order is a tree, one can explicitly construct $d$-hitting families of schedules of small size. When the tree is balanced, our constructions are polylogarithmic in the number of events.
Local High-order Regularization on Data Manifolds
Venue: arXiv cs.CV 2016
Year: 2016

The common graph Laplacian regularizer is well-established in semi-supervised learning and spectral dimensionality reduction. However, as a first-order regularizer, it can lead to degenerate functions in high-dimensional manifolds. The iterated graph Laplacian enables high-order regularization, but it has a high computational complexity and so cannot be applied to large problems. We introduce a new regularizer which is globally high order and so does not suffer from the degeneracy of the graph Laplacian regularizer, but is also sparse for efficient computation in semi-supervised learning applications. We reduce computational complexity by building a local first-order approximation of the manifold as a surrogate geometry, and construct our high-order regularizer based on local derivative evaluations therein. Experiments on human body shape and pose analysis demonstrate the effectiveness and efficiency of our method.
How to group wireless nodes together?
Venue: arXiv cs.NI 2016
Year: 2016

This report presents a survey on how to group together in a static way planar nodes, that may belong to a wireless network (ad hoc or cellular). The aim is to identify appropriate methods that could also be applied for Point Processes. Specifically matching pairs and algorithms are initially discussed. Next, specifically for Point Processes, the Nearest Neighbour and Lilypond models are presented. Properties and results for the two models are stated. Original bounds are given for the value of the so-called generation number, which is related to the size of the nearest neighbour cluster. Finally, a variation of the nearest neighbour grouping is proposed and an original metric is introduced, named here the ancestor number. This is used to facilitate the analysis of the distribution of cluster size. Based on this certain related bounds are derived. The report and the analysis included show clearly the difficulty of working in point processes with static clusters of size greater than two, when these are defined by proximity criteria.
Designing a Mobile Game for Home Computer Users to Protect Against Phishing Attacks
Venue: arXiv cs.CY 2016
Year: 2016

This research aims to design an educational mobile game for home computer users to prevent from phishing attacks. Phishing is an online identity theft which aims to steal sensitive information such as username, password and online banking details from victims. To prevent this, phishing education needs to be considered. Mobile games could facilitate to embed learning in a natural environment. The paper introduces a mobile game design based on a story which is simplifying and exaggerating real life. We use a theoretical model derived from Technology Threat Avoidance Theory (TTAT) to address the game design issues and game design principles were used as a set of guidelines for structuring and presenting information. The overall mobile game design was aimed to enhance avoidance behaviour through motivation of home computer users to protect against phishing threats. The prototype game design is presented on Google App Inventor Emulator. We believe by training home computer users to protect against phishing attacks, would be an aid to enable the cyberspace as a secure environment.
Global Deconvolutional Networks for Semantic Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Semantic image segmentation is a principal problem in computer vision, where the aim is to correctly classify each individual pixel of an image into a semantic label. Its widespread use in many areas, including medical imaging and autonomous driving, has fostered extensive research in recent years. Empirical improvements in tackling this task have primarily been motivated by successful exploitation of Convolutional Neural Networks (CNNs) pre-trained for image classification and object recognition. However, the pixel-wise labelling with CNNs has its own unique challenges: (1) an accurate deconvolution, or upsampling, of low-resolution output into a higher-resolution segmentation mask and (2) an inclusion of global information, or context, within locally extracted features. To address these issues, we propose a novel architecture to conduct the equivalent of the deconvolution operation globally and acquire dense predictions. We demonstrate that it leads to improved performance of state-of-the-art semantic segmentation models on the PASCAL VOC 2012 benchmark, reaching 74.0% mean IU accuracy on the test set.
Signal periodic decomposition with conjugate subspaces
Venue: arXiv cs.CE 2016
Year: 2016

In this paper, we focus on hidden period identification and the periodic decomposition of signals. Based on recent results on the Ramanujan subspace, we reveal the conjugate symmetry of the Ramanujan subspace with a set of complex exponential basis functions and represent the subspace as the union of a series of conjugate subspaces. With these conjugate subspaces, the signal periodic model is introduced to characterize the periodic structure of a signal. To achieve the decomposition of the proposed model, the conjugate subspace matching pursuit (CSMP) algorithm is proposed based on two different greedy strategies. The CSMP is performed iteratively in two stages. In the first stage, the dominant hidden period is chosen with the periodicity strategy. Then, the dominant conjugate subspace is chosen with the energy strategy in the second stage. Compared with the current state-of-the-art methods for hidden period identification, the main advantages provided by the CSMP are the following: (i) the capability of identifying all the hidden periods in the range from $1$ to the maximum hidden period $Q$ of a signal of any length, without truncating the signal; (ii) the ability to identify the time-varying hidden period with its shifted version; and (iii) the low computational cost, without generating and using a large over-complete dictionary. Moreover, we provide examples and applications to demonstrate the abilities of the proposed two-stage CSMP algorithm, which include hidden period identification, signal approximation, time-varying period detection, and pitch detection of speech.
Complete contracts through specification drivers
Venue: arXiv cs.SE 2016
Year: 2016

Existing techniques of Design by Contract do not allow software developers to specify complete contracts in many cases. Incomplete contracts leave room for malicious implementations. This article complements Design by Contract with a simple yet powerful technique that removes the problem without adding syntactical mechanisms. The proposed technique makes it possible not only to derive complete contracts, but also to rigorously check and improve completeness of existing contracts without instrumenting them.
Energy, Latency, and Reliability Tradeoffs in Coding Circuits
Venue: arXiv cs.IT 2016
Year: 2016

It is shown that fully-parallel encoding and decoding schemes with asymptotic block error probability that scales as $O\left(f\left(n\right)\right)$ have Thompson energy that scales as $Ω\left(\sqrt{\ln f\left(n\right)}n\right)$. As well, it is shown that the number of clock cycles (denoted $T\left(n\right)$) required for any encoding or decoding scheme that reaches this bound must scale as $T\left(n\right)\ge\sqrt{\ln f\left(n\right)}$. Similar scaling results are extended to serialized computation. The Grover information-friction energy model is generalized to three dimensions and the optimal energy of encoding or decoding schemes with probability of block error $P_\mathrm{e}$ is shown to be at least $Ω\left(n\left(\ln P_{\mathrm{e}}\left(n\right)\right)^{\frac{1}{3}}\right)$.
Tracking the performance of an R&D programme in the Biomedical Sciences
Venue: arXiv cs.DL 2016
Year: 2016

This paper aims at offering an evaluation framework of an Research and Development programme in the Biomedical Sciences. It showcases the Spanish Biomedical Research Networking Centres initiative (CIBER) as an example of the effect of research policy management on performance. For this it focuses on three specific aspects: its role on the national research output in the biomedical sciences, its effect on promoting translational research through internal collaboration between research groups, and the perception of researchers on the programme as defined by their inclusion of their CIBER centres in the address field. Research output derived from this programme represents around 25 per cent of the country's publications in the biomedical fields. After analysing a seven year period, the programme has enhanced collaborations between its members, but they do not seem to be sufficiently strong. With regard to the credit given to the initiative, 54.5 per cent of the publications mentioned this programme in their address, however an increase on the share of papers mention it is observed two years after it was launched. We suggest that by finding the point in which the share of mentions stabilises may be a good strategy to identify the complete fulfilment of these types of Research and Development policies.
An Analytical Model of the IEEE 802.3ah MAC Protocol for EPON-based Access Systems
Venue: arXiv cs.NI 2016
Year: 2016

Ethernet Passive Optical Networks (EPON) access systems are considered as an alternative to ADSL for high speed access to the Internet. Supported by the Ethernet First Mile Alliance and the IEEE, the MPCP protocol has been adopted as the standardized MAC protocol for EPONs. Moreover, the IPACT dynamic bandwidth allocation mechanism has been proposed for hierarchical multiplexing. Today, IPACT is considered as interesting complement to MPCP for dynamic bandwidth allocation over EPONs. In this paper, we propose an original analytical model of the MPCP+IPACT protocol. Numerical results obtained from this model are commented and compared to computer simulations.
TouchSignatures: Identification of User Touch Actions and PINs Based on Mobile Sensor Data via JavaScript
Venue: arXiv cs.CR 2016
Year: 2016

Conforming to W3C specifications, mobile web browsers allow JavaScript code in a web page to access motion and orientation sensor data without the user's permission. The associated risks to user security and privacy are however not considered in W3C specifications. In this work, for the first time, we show how user security can be compromised using these sensor data via browser, despite that the data rate is 3 to 5 times slower than what is available in app. We examine multiple popular browsers on Android and iOS platforms and study their policies in granting permissions to JavaScript code with respect to access to motion and orientation sensor data. Based on our observations, we identify multiple vulnerabilities, and propose TouchSignatures which implements an attack where malicious JavaScript code on an attack tab listens to such sensor data measurements. Based on these streams, TouchSignatures is able to distinguish the user's touch actions (i.e., tap, scroll, hold, and zoom) and her PINs, allowing a remote website to learn the client-side user activities. We demonstrate the practicality of this attack by collecting data from real users and reporting high success rates using our proof-of-concept implementations. We also present a set of potential solutions to address the vulnerabilities. The W3C community and major mobile browser vendors including Mozilla, Google, Apple and Opera have acknowledge our work and are implementing some of our proposed countermeasures.
Practical Fault-Tolerant Data Aggregation
Venue: arXiv cs.CR 2016
Year: 2016

During Financial Cryptography 2012 Chan et al. presented a novel privacy-protection fault-tolerant data aggregation protocol. Comparing to previous work, their scheme guaranteed provable privacy of individuals and could work even if some number of users refused to participate. In our paper we demonstrate that despite its merits, their method provides unacceptably low accuracy of aggregated data for a wide range of assumed parameters and cannot be used in majority of real-life systems. To show this we use both precise analytic and experimental methods. Additionally, we present a precise data aggregation protocol that provides provable level of security even facing massive failures of nodes. Moreover, the protocol requires significantly less computation (limited exploiting of heavy cryptography) than most of currently known fault tolerant aggregation protocols and offers better security guarantees that make it suitable for systems of limited resources (including sensor networks). To obtain our result we relax however the model and allow some limited communication between the nodes.
Squish: Near-Optimal Compression for Archival of Relational Datasets
Venue: arXiv cs.DB 2016
Year: 2016

Relational datasets are being generated at an alarmingly rapid rate across organizations and industries. Compressing these datasets could significantly reduce storage and archival costs. Traditional compression algorithms, e.g., gzip, are suboptimal for compressing relational datasets since they ignore the table structure and relationships between attributes. We study compression algorithms that leverage the relational structure to compress datasets to a much greater extent. We develop Squish, a system that uses a combination of Bayesian Networks and Arithmetic Coding to capture multiple kinds of dependencies among attributes and achieve near-entropy compression rate. Squish also supports user-defined attributes: users can instantiate new data types by simply implementing five functions for a new class interface. We prove the asymptotic optimality of our compression algorithm and conduct experiments to show the effectiveness of our system: Squish achieves a reduction of over 50\% in storage size relative to systems developed in prior work on a variety of real datasets.
Systematic and Deterministic Graph-Minor Embedding for Cartesian Products of Graphs
Venue: arXiv cs.DM 2016
Year: 2016

The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph-minor embedding methods. These methods allow non-native problems to be adapted to the target annealer's architecture. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for solving real-world applications. To alleviate this difficulty, we propose a systematic and deterministic embedding method, exploiting the structures of both the input graph of the specific problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We divide the embedding problem by first embedding one of the factors of the Cartesian product in a repeatable pattern. The resulting simplified problem consists of the placement and connecting together of these copies to reach a valid solution. Aside from the obvious advantage of a systematic and deterministic approach with respect to speed and efficiency, the embeddings produced are easily scaled for larger processors and show desirable properties for the number of qubits used and the chain length distribution. To conclude, we briefly address the problem of circumventing inoperable qubits by presenting possible extensions of the method.
Dimension and codimension of simple games
Venue: arXiv cs.GT 2016
Year: 2016

This paper studies the complexity of computing a representation of a simple game as the intersection (union) of weighted majority games, as well as, the dimension or the codimension. We also present some examples with linear dimension and exponential codimension with respect to the number of players.
Semantic Scan: Detecting Subtle, Spatially Localized Events in Text Streams
Venue: arXiv cs.IR 2016
Year: 2016

Early detection and precise characterization of emerging topics in text streams can be highly useful in applications such as timely and targeted public health interventions and discovering evolving regional business trends. Many methods have been proposed for detecting emerging events in text streams using topic modeling. However, these methods have numerous shortcomings that make them unsuitable for rapid detection of locally emerging events on massive text streams. In this paper, we describe Semantic Scan (SS) that has been developed specifically to overcome these shortcomings in detecting new spatially compact events in text streams. Semantic Scan integrates novel contrastive topic modeling with online document assignment and principled likelihood ratio-based spatial scanning to identify emerging events with unexpected patterns of keywords hidden in text streams. This enables more timely and accurate detection and characterization of anomalous, spatially localized emerging events. Semantic Scan does not require manual intervention or labeled training data, and is robust to noise in real-world text data since it identifies anomalous text patterns that occur in a cluster of new documents rather than an anomaly in a single new document. We compare Semantic Scan to alternative state-of-the-art methods such as Topics over Time, Online LDA, and Labeled LDA on two real-world tasks: (i) a disease surveillance task monitoring free-text Emergency Department chief complaints in Allegheny County, and (ii) an emerging business trend detection task based on Yelp reviews. On both tasks, we find that Semantic Scan provides significantly better event detection and characterization accuracy than competing approaches, while providing up to an order of magnitude speedup.
Energy-Aware Cooperative Computation in Mobile Devices
Venue: arXiv cs.NI 2016
Year: 2016

New data intensive applications, which are continuously emerging in daily routines of mobile devices, significantly increase the demand for data, and pose a challenge for current wireless networks due to scarce resources. Although bandwidth is traditionally considered as the primary scarce resource in wireless networks, the developments in communication theory shifts the focus from bandwidth to other scarce resources including processing power and energy. Especially, in device-to-device networks, where data rates are increasing rapidly, processing power and energy are becoming the primary bottlenecks of the network. Thus, it is crucial to develop new networking mechanisms by taking into account the processing power and energy as bottlenecks. In this paper, we develop an energy-aware cooperative computation framework for mobile devices. In this setup, a group of cooperative mobile devices, within proximity of each other, (i) use their cellular or Wi-Fi (802.11) links as their primary networking interfaces, and (ii) exploit their device-to-device connections (e.g., Wi-Fi Direct) to overcome processing power and energy bottlenecks. We evaluate our energy-aware cooperative computation framework on a testbed consisting of smartphones and tablets, and we show that it brings significant performance benefits.