OpenRaiser/Intern-Atlas huggingface dataset:
Parameter Compilation
Venue: arXiv cs.CC 2015
Year: 2015

In resolving instances of a computational problem, if multiple instances of interest share a feature in common, it may be fruitful to compile this feature into a format that allows for more efficient resolution, even if the compilation is relatively expensive. In this article, we introduce a formal framework for classifying problems according to their compilability. The basic object in our framework is that of a parameterized problem, which here is a language along with a parameterization---a map which provides, for each instance, a so-called parameter on which compilation may be performed. Our framework is positioned within the paradigm of parameterized complexity, and our notions are relatable to established concepts in the theory of parameterized complexity. Indeed, we view our framework as playing a unifying role, integrating together parameterized complexity and compilability theory.
An Introduction to Temporal Graphs: An Algorithmic Perspective
Venue: arXiv cs.DM 2015
Year: 2015

A \emph{temporal graph} is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence $G_1,G_2\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.
Investigating the Impact of Global Positioning System Evidence
Venue: arXiv cs.CY 2015
Year: 2015

The continued amalgamation of Global Positioning Systems (GPS) into everyday activities stimulates the idea that these devices will increasingly contribute evidential importance in digital forensics cases. This study investigates the extent to which GPS devices are being used in criminal and civil court cases in the United Kingdom through the inspection of Lexis Nexis, Westlaw, and the British and Irish Legal Information Institute (BAILII) legal databases. The research identified 83 cases which involved GPS evidence from within the United Kingdom and Europe for the time period from 01 June 1993 to 01 June 2013. The initial empirical analysis indicates that GPS evidence in court cases is rising over time and the majority of those court cases are criminal cases.
Flexible and Robust Privacy-Preserving Implicit Authentication
Venue: arXiv cs.CR 2015
Year: 2015

Implicit authentication consists of a server authenticating a user based on the user's usage profile, instead of/in addition to relying on something the user explicitly knows (passwords, private keys, etc.). While implicit authentication makes identity theft by third parties more difficult, it requires the server to learn and store the user's usage profile. Recently, the first privacy-preserving implicit authentication system was presented, in which the server does not learn the user's profile. It uses an ad hoc two-party computation protocol to compare the user's fresh sampled features against an encrypted stored user's profile. The protocol requires storing the usage profile and comparing against it using two different cryptosystems, one of them order-preserving; furthermore, features must be numerical. We present here a simpler protocol based on set intersection that has the advantages of: i) requiring only one cryptosystem; ii) not leaking the relative order of fresh feature samples; iii) being able to deal with any type of features (numerical or non-numerical). Keywords: Privacy-preserving implicit authentication, privacy-preserving set intersection, implicit authentication, active authentication, transparent authentication, risk mitigation, data brokers.
Learning Immune-Defectives Graph through Group Tests
Venue: arXiv cs.IT 2015
Year: 2015

This paper deals with an abstraction of a unified problem of drug discovery and pathogen identification. Pathogen identification involves identification of disease-causing biomolecules. Drug discovery involves finding chemical compounds, called lead compounds, that bind to pathogenic proteins and eventually inhibit the function of the protein. In this paper, the lead compounds are abstracted as inhibitors, pathogenic proteins as defectives, and the mixture of "ineffective" chemical compounds and non-pathogenic proteins as normal items. A defective could be immune to the presence of an inhibitor in a test. So, a test containing a defective is positive iff it does not contain its "associated" inhibitor. The goal of this paper is to identify the defectives, inhibitors, and their "associations" with high probability, or in other words, learn the Immune Defectives Graph (IDG) efficiently through group tests. We propose a probabilistic non-adaptive pooling design, a probabilistic two-stage adaptive pooling design and decoding algorithms for learning the IDG. For the two-stage adaptive-pooling design, we show that the sample complexity of the number of tests required to guarantee recovery of the inhibitors, defectives, and their associations with high probability, i.e., the upper bound, exceeds the proposed lower bound by a logarithmic multiplicative factor in the number of items. For the non-adaptive pooling design too, we show that the upper bound exceeds the proposed lower bound by at most a logarithmic multiplicative factor in the number of items.
Offloading on the Edge: Analysis and Optimization of Local Data Storage and Offloading in HetNets
Venue: arXiv cs.NI 2015
Year: 2015

The rapid increase in data traffic demand has overloaded existing cellular networks. Planned upgrades in the communication architecture (e.g. LTE), while helpful, are not expected to suffice to keep up with demand. As a result, extensive densification through small cells, caching content closer to or even at the device, and device-to-device (D2D) communications are seen as necessary components for future heterogeneous cellular networks to withstand the data crunch. Nevertheless, these options imply new CAPEX and OPEX costs, extensive backhaul support, contract plan incentives for D2D, and a number of interesting tradeoffs arise for the operator. In this paper, we propose an analytical model to explore how much local storage and communication through "edge" nodes could help offload traffic in various heterogeneous network (HetNet) setups and levels of user tolerance to delays. We then use this model to optimize the storage allocation and access mode of different contents as a tradeoff between user satisfaction and cost to the operator. Finally, we validate our findings through realistic simulations and show that considerable amounts of traffic can be offloaded even under moderate densification levels.
Demystifying Reachability in Vector Addition Systems
Venue: arXiv cs.LO 2015
Year: 2015

More than 30 years after their inception, the decidability proofs for reachability in vector addition systems (VAS) still retain much of their mystery. These proofs rely crucially on a decomposition of runs successively refined by Mayr, Kosaraju, and Lambert, which appears rather magical, and for which no complexity upper bound is known. We first offer a justification for this decomposition technique, by showing that it computes the ideal decomposition of the set of runs, using the natural embedding relation between runs as well quasi ordering. In a second part, we apply recent results on the complexity of termination thanks to well quasi orders and well orders to obtain a cubic Ackermann upper bound for the decomposition algorithms, thus providing the first known upper bounds for general VAS reachability.
On the Convergence and Performance of MF Precoding in Distributed Massive MU-MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we analyze both the rate of convergence and the performance of a matched-filter (MF) precoder in a massive multi-user (MU) multiple-input-multiple-output (MIMO) system, with the aim of determining the impact of distributing the transmit antennas into multiple clusters. We consider cases of transmit spatial correlation, unequal link gains and imperfect channel state information (CSI). Furthermore, we derive a MF signal-to-interference-plus-noise-ratio (SINR) limit as both the number of transmit antennas and the number of users tend to infinity. In our results, we show that both the rate of convergence and performance is strongly dependent on spatial correlation. In the presence of spatial correlation, distributing the antennas into multiple clusters renders significant gains over a co-located antenna array scenario. In uncorrelated scenarios, a co-located antenna cluster has a marginally better mean per-user SINR performance due to its superior single-user signal-to-noise-ratio (SNR) regime, i.e., when a user is close to the base station (BS), the links between the user and all transmit antennas becomes strong.
An Introduction to Logics of Knowledge and Belief
Venue: arXiv cs.AI 2015
Year: 2015

This chapter provides an introduction to some basic concepts of epistemic logic, basic formal languages, their semantics, and proof systems. It also contains an overview of the handbook, and a brief history of epistemic logic and pointers to the literature.
Mobile Application for Dengue Fever Monitoring and Tracking via GPS: Case Study for Fiji
Venue: arXiv cs.CY 2015
Year: 2015

The 2013 outbreak of Dengue in Fiji resulted in an alarming number of deaths and has been is a matter of serious concern. Dengue fever is a disease caused by the four types of the Dengue virus serotypes and transmitted mostly from mosquito bites. In Fiji, dengue diagnosis is only done in hospitals which are slow and time consuming. It is also important to monitor the spread of Dengue. Fiji needs an convenient method of monitoring the spread of Dengue. With increase in affordable smartphones and better Internet coverage, there is scope for a mobile application for Dengue fever monitoring and tracking. This paper proposes a mobile application for Dengue monitoring based on global positioning system (GPS) enabled mobile phone technology. It also provides an information network that shows the spread of dengue which will allow health authorities to quickly identify dengue infected areas in Fiji. A mobile application prototype is developed and tested and the scope for further testing and implementation is also given.
Towards Reasoning About Properties of Imperative Programs using Linear Logic
Venue: arXiv cs.LO 2015
Year: 2015

In this paper we propose an approach to reasoning about properties of imperative programs. We assume in this context that the meanings of program constructs are described using rules in the natural semantics style with the additional observation that these rules may involve the treatment of state. Our approach involves modeling natural semantics style rules within a logic and then reasoning about the behavior of particular programs by reasoning about proofs in that logic. A key aspect of our proposal is to use a fragment of linear logic called Lolli (invented by Hodas and Miller) to model natural semantics style descriptions. Being based on linear logic, Lolli can provide logical expression to resources such as state. Lolli additionally possesses proof-theoretic properties that allow it to encode natural semantics style descriptions in such a way that proofs in Lolli mimic the structure of derivations based on the natural semantics rules. We will discuss these properties of Lolli and demonstrate how they can be exploited in modeling the semantics of imperative programs and in reasoning about such models.
A Selectivity based approach to Continuous Pattern Detection in Streaming Graphs
Venue: arXiv cs.DB 2015
Year: 2015

Cyber security is one of the most significant technical challenges in current times. Detecting adversarial activities, prevention of theft of intellectual properties and customer data is a high priority for corporations and government agencies around the world. Cyber defenders need to analyze massive-scale, high-resolution network flows to identify, categorize, and mitigate attacks involving networks spanning institutional and national boundaries. Many of the cyber attacks can be described as subgraph patterns, with prominent examples being insider infiltrations (path queries), denial of service (parallel paths) and malicious spreads (tree queries). This motivates us to explore subgraph matching on streaming graphs in a continuous setting. The novelty of our work lies in using the subgraph distributional statistics collected from the streaming graph to determine the query processing strategy. We introduce a "Lazy Search" algorithm where the search strategy is decided on a vertex-to-vertex basis depending on the likelihood of a match in the vertex neighborhood. We also propose a metric named "Relative Selectivity" that is used to select between different query processing strategies. Our experiments performed on real online news, network traffic stream and a synthetic social network benchmark demonstrate 10-100x speedups over selectivity agnostic approaches.
An Interoperable Realization of Smart Cities with Plug and Play based Device Management
Venue: arXiv cs.SY 2015
Year: 2015

The primal problem with Internet of Things (IoT) solutions for smart cities is the lack of interoperability at various levels, and more predominately at the device level. While there exist multitude of platforms from multiple manufacturers, the existing ecosystem still remains highly closed. In this paper, we propose SNaaS or Sensor/Network as a Service: a service layer that enables the creation of the plug-n-play infrastructure, across platforms from multiple vendors, necessary for interoperability and successful deployment of large-scale city wide systems. In order to correctly position the new service layer, we present a high level reference IoT architecture for smart city implementations, and follow it up with the workflow details of SNaaS along with preliminary microbenchmarks.
Transform Domain Analysis of Sequences
Venue: arXiv cs.CR 2015
Year: 2015

In cryptanalysis, security of ciphers vis-a-vis attacks is gauged against three criteria of complexities, i.e., computations, memory and time. Some features may not be so apparent in a particular domain, and their analysis in a transformed domain often reveals interesting patterns. Moreover, the complexity criteria in different domains are different and performance improvements are often achieved by transforming the problem in an alternate domain. Owing to the results of coding theory and signal processing, Discrete Fourier Transform (DFT) based attacks have proven to be efficient than algebraic attacks in terms of their computational complexity. Motivated by DFT based attacks, we present a transform domain analysis of Linear Feedback Shift Register(LFSR) based sequence generators. The time and frequency domain behavior of non-linear filter and combiner generators is discussed along with some novel observations based on the Chinese Remainder Theorem (CRT). CRT is exploited to establish patterns in LFSR sequences and underlying cyclic structures of finite fields. Application of DFT spectra attacks on combiner generators is also demonstrated. Our proposed method saves on the last stage computations of selective DFT attacks for combiner generators. The proposed approach is demonstrated on some examples of combiner generators and is scalable to general configuration of combiner generators.
On memetic search for the max-mean dispersion problem
Venue: arXiv cs.AI 2015
Year: 2015

Given a set $V$ of $n$ elements and a distance matrix $[d_{ij}]_{n\times n}$ among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset $M$ from $V$ such that the mean dispersion (or distance) among the selected elements is maximized. Being a useful model to formulate several relevant applications, MaxMeanDP is known to be NP-hard and thus computationally difficult. In this paper, we present a highly effective memetic algorithm for MaxMeanDP which relies on solution recombination and local optimization to find high quality solutions. Computational experiments on the set of 160 benchmark instances with up to 1000 elements commonly used in the literature show that the proposed algorithm improves or matches the published best known results for all instances in a short computing time, with only one exception, while achieving a high success rate of 100\%. In particular, we improve 59 previous best results out of the 60 most challenging instances. Results on a set of 40 new large instances with 3000 and 5000 elements are also presented. The key ingredients of the proposed algorithm are investigated to shed light on how they affect the performance of the algorithm.
Design for Online Deliberative Processes and Technologies: Towards a Multidisciplinary Research Agenda
Venue: arXiv cs.HC 2015
Year: 2015

There has been rapidly growing interest in studying and designing online deliberative processes and technologies. This SIG aims at providing a venue for continuous and constructive dialogue between social, political and cognitive sciences as well as computer science, HCI, and CSCW. Through an online community and a modified version of world cafe discussions, we contribute to the definition of the theoretical building blocks, the identification of a research agenda for the CHI community, and the network of individuals from academia, industry, and the public sector who share interests in different aspects of online deliberation.
Random Pulse Train Spectrum Calculation Unleashed
Venue: arXiv cs.IT 2015
Year: 2015

For the first time the problem of the full solution for the calculation of the power spectrum density of the random pulse train is solved. This well known problem led to a mistaken publication in the past and even its partial solution was considered worthy of publication in a textbook. The little known solution for only the continues random pulse train spectrum is explained by examples and is extended to cover each signal having a discrete spectrum, too. A developed approach is used to derive the general equation for two important representative pulse trains with unbalanced symbol duration: a signal with stretched pulse with a transition from one to zero, and shortened blank symbols. The developed theoretical results are validated by simulation. It is shown that the pulse trains under consideration pose spectrum peaks. The characteristics of these peaks are investigated.
A Markovian Approach to the Optimal Demodulation of Diffusion-based Molecular Communication Networks
Venue: arXiv cs.IT 2015
Year: 2015

In a diffusion-based molecular communication network, transmitters and receivers communicate by using signalling molecules (or ligands) in a fluid medium. This paper assumes that the transmitter uses different chemical reactions to generate different emission patterns of signalling molecules to represent different transmission symbols, and the receiver consists of receptors. When the signalling molecules arrive at the receiver, they may react with the receptors to form ligand-receptor complexes. Our goal is to study the demodulation in this setup assuming that the transmitter and receiver are synchronised. We derive an optimal demodulator using the continuous history of the number of complexes at the receiver as the input to the demodulator. We do that by first deriving a communication model which includes the chemical reactions in the transmitter, diffusion in the transmission medium and the ligand-receptor process in the receiver. This model, which takes the form of a continuous-time Markov process, captures the noise in the receiver signal due to the stochastic nature of chemical reactions and diffusion. We then adopt a maximum a posterior framework and use Bayesian filtering to derive the optimal demodulator. We use numerical examples to illustrate the properties of this optimal demodulator.
Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints
Venue: arXiv cs.LG 2015
Year: 2015

We study online prediction where regret of the algorithm is measured against a benchmark defined via evolving constraints. This framework captures online prediction on graphs, as well as other prediction problems with combinatorial structure. A key aspect here is that finding the optimal benchmark predictor (even in hindsight, given all the data) might be computationally hard due to the combinatorial nature of the constraints. Despite this, we provide polynomial-time \emph{prediction} algorithms that achieve low regret against combinatorial benchmark sets. We do so by building improper learning algorithms based on two ideas that work together. The first is to alleviate part of the computational burden through random playout, and the second is to employ Lasserre semidefinite hierarchies to approximate the resulting integer program. Interestingly, for our prediction algorithms, we only need to compute the values of the semidefinite programs and not the rounded solutions. However, the integrality gap for Lasserre hierarchy \emph{does} enter the generic regret bound in terms of Rademacher complexity of the benchmark set. This establishes a trade-off between the computation time and the regret bound of the algorithm.
Temporal Pyramid Pooling Based Convolutional Neural Networks for Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Encouraged by the success of Convolutional Neural Networks (CNNs) in image classification, recently much effort is spent on applying CNNs to video based action recognition problems. One challenge is that video contains a varying number of frames which is incompatible to the standard input format of CNNs. Existing methods handle this issue either by directly sampling a fixed number of frames or bypassing this issue by introducing a 3D convolutional layer which conducts convolution in spatial-temporal domain. To solve this issue, here we propose a novel network structure which allows an arbitrary number of frames as the network input. The key of our solution is to introduce a module consisting of an encoding layer and a temporal pyramid pooling layer. The encoding layer maps the activation from previous layers to a feature vector suitable for pooling while the temporal pyramid pooling layer converts multiple frame-level activations into a fixed-length video-level representation. In addition, we adopt a feature concatenation layer which combines appearance information and motion information. Compared with the frame sampling strategy, our method avoids the risk of missing any important frames. Compared with the 3D convolutional method which requires a huge video dataset for network training, our model can be learned on a small target dataset because we can leverage the off-the-shelf image-level CNN for model parameter initialization. Experiments on two challenging datasets, Hollywood2 and HMDB51, demonstrate that our method achieves superior performance over state-of-the-art methods while requiring much fewer training data.
A new method on deterministic construction of the measurement matrix in compressed sensing
Venue: arXiv cs.IT 2015
Year: 2015

Construction on the measurement matrix $A$ is a central problem in compressed sensing. Although using random matrices is proven optimal and successful in both theory and applications. A deterministic construction on the measurement matrix is still very important and interesting. In fact, it is still an open problem proposed by T. Tao. In this paper, we shall provide a new deterministic construction method and prove it is optimal with regard to the mutual incoherence.