OpenRaiser/Intern-Atlas huggingface dataset:
Computing exponentially faster: Implementing a nondeterministic universal Turing machine using DNA
Venue: arXiv cs.CC 2016
Year: 2016

The theory of computer science is based around Universal Turing Machines (UTMs): abstract machines able to execute all possible algorithms. Modern digital computers are physical embodiments of UTMs. The nondeterministic polynomial (NP) time complexity class of problems is the most significant in computer science, and an efficient (i.e. polynomial P) way to solve such problems would be of profound economic and social importance. By definition nondeterministic UTMs (NUTMs) solve NP complete problems in P time. However, NUTMs have previously been believed to be physically impossible to construct. Thue string rewriting systems are computationally equivalent to UTMs, and are naturally nondeterministic. Here we describe the physical design for a NUTM that implements a universal Thue system. The design exploits the ability of DNA to replicate to execute an exponential number of computational paths in P time. Each Thue rewriting step is embodied in a DNA edit implemented using a novel combination of polymerase chain reactions and site-directed mutagenesis. We demonstrate that this design works using both computational modelling and in vitro molecular biology experimentation. The current design has limitations, such as restricted error-correction. However, it opens up the prospect of engineering NUTM based computers able to outperform all standard computers on important practical problems.
White Paper: Brief overview of current practices for open consultation
Venue: arXiv cs.CY 2016
Year: 2016

The purpose of this document is to provide a brief overview of open consultation approaches in the current, international setting and propose a role for Information Technologies (IT) as a disruptive force in this setting.
Collision-free Operation in High Density WLAN Deployments
Venue: arXiv cs.NI 2016
Year: 2016

WiFi's popularity has led to crowded scenarios composed of many Access Points (AP) and clients, often operating on overlapping channels, producing interference that gravely degrades performance. This misallocation of resources is often the result of multiple WLANs ownership, that is, networks are frequently setup automatically without considering neighbouring APs. In this work we overview the effect of Overlapping BSS (OBSS) from the perspective of the MAC layer, taking special interest on describing the advantages of eliminating collisions with Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA). We propose a single Access Point (AP) and several multi-AP scenarios, including the residential building example proposed for testing the upcoming IEEE 802.11ax amendment. Results using the first NS-3 implementation of CSMA/ECA reveal the advantage of CSMA/ECA's deterministic backoff contention technique, confirming its suitability for very crowded scenarios.
DynaLog: An automated dynamic analysis framework for characterizing Android applications
Venue: arXiv cs.CR 2016
Year: 2016

Android is becoming ubiquitous and currently has the largest share of the mobile OS market with billions of application downloads from the official app market. It has also become the platform most targeted by mobile malware that are becoming more sophisticated to evade state-of-the-art detection approaches. Many Android malware families employ obfuscation techniques in order to avoid detection and this may defeat static analysis based approaches. Dynamic analysis on the other hand may be used to overcome this limitation. Hence in this paper we propose DynaLog, a dynamic analysis based framework for characterizing Android applications. The framework provides the capability to analyse the behaviour of applications based on an extensive number of dynamic features. It provides an automated platform for mass analysis and characterization of apps that is useful for quickly identifying and isolating malicious applications. The DynaLog framework leverages existing open source tools to extract and log high level behaviours, API calls, and critical events that can be used to explore the characteristics of an application, thus providing an extensible dynamic analysis platform for detecting Android malware. DynaLog is evaluated using real malware samples and clean applications demonstrating its capabilities for effective analysis and detection of malicious applications.
Android Malware Detection Using Parallel Machine Learning Classifiers
Venue: arXiv cs.CR 2016
Year: 2016

Mobile malware has continued to grow at an alarming rate despite on-going efforts towards mitigating the problem. This has been particularly noticeable on Android due to its being an open platform that has subsequently overtaken other platforms in the share of the mobile smart devices market. Hence, incentivizing a new wave of emerging Android malware sophisticated enough to evade most common detection methods. This paper proposes and investigates a parallel machine learning based classification approach for early detection of Android malware. Using real malware samples and benign applications, a composite classification model is developed from parallel combination of heterogeneous classifiers. The empirical evaluation of the model under different combination schemes demonstrates its efficacy and potential to improve detection accuracy. More importantly, by utilizing several classifiers with diverse characteristics, their strengths can be harnessed not only for enhanced Android malware detection but also quicker white box analysis by means of the more interpretable constituent classifiers.
Collective benefits in traffic during mega events via the use of information technologies
Venue: arXiv cs.SI 2016
Year: 2016

Information technologies today can inform each of us about the best alternatives for shortest paths from origins to destinations, but they do not contain incentives or alternatives that manage the information efficiently to get collective benefits. To obtain such benefits, we need to have not only good estimates of how the traffic is formed but also to have target strategies to reduce enough vehicles from the best possible roads in a feasible way. The opportunity is that during large events the traffic inconveniences in large cities are unusually high, yet temporary, and the entire population may be more willing to adopt collective recommendations for social good. In this paper, we integrate for the first time big data resources to quantify the impact of events and propose target strategies for collective good at urban scale. In the context of the Olympic Games in Rio de Janeiro, we first predict the expected increase in traffic. To that end, we integrate data from: mobile phones, Airbnb, Waze, and transit information, with game schedules and information of venues. Next, we evaluate the impact of the Olympic Games to the travel of commuters, and propose different route choice scenarios during the peak hours. Moreover, we gather information on the trips that contribute the most to the global congestion and that could be redirected from vehicles to transit. Interestingly, we show that (i) following new route alternatives during the event with individual shortest path can save more collective travel time than keeping the routine routes, uncovering the positive value of information technologies during events; (ii) with only a small proportion of people selected from specific areas switching from driving to public transport, the collective travel time can be reduced to a great extent. Results are presented on-line for the evaluation of the public and policy makers.
Robust Causal Transform Coding for LQG Systems with Delay Loss in Communications
Venue: arXiv cs.SY 2016
Year: 2016

A networked controlled system (NCS) in which the plant communicates to the controller over a channel with random delay loss is considered. The channel model is motivated by recent development of tree codes for NCS, which effectively translates an erasure channel to one with random delay. A causal transform coding scheme is presented which exploits the plant state memory for efficient communications (compression) and provides robustness to channel delay loss. In this setting, we analyze the performance of linear quadratic Gaussian (LQG) closed-loop systems and the design of the optimal controller. The design of the transform code for LQG systems is posed as a channel optimized source coding problem of minimizing a weighted mean squared error over the channel. The solution is characterized in two steps of obtaining the optimized causal encoding and decoding transforms and rate allocation across a set of transform coding quantizers. Numerical and simulation results for Gauss-Markov sources and an LQG system demonstrate the effectiveness of the proposed schemes.
PANDA: Extreme Scale Parallel K-Nearest Neighbor on Distributed Architectures
Venue: arXiv cs.DC 2016
Year: 2016

Computing $k$-Nearest Neighbors (KNN) is one of the core kernels used in many machine learning, data mining and scientific computing applications. Although kd-tree based $O(\log n)$ algorithms have been proposed for computing KNN, due to its inherent sequentiality, linear algorithms are being used in practice. This limits the applicability of such methods to millions of data points, with limited scalability for Big Data analytics challenges in the scientific domain. In this paper, we present parallel and highly optimized kd-tree based KNN algorithms (both construction and querying) suitable for distributed architectures. Our algorithm includes novel approaches for pruning search space and improving load balancing and partitioning among nodes and threads. Using TB-sized datasets from three science applications: astrophysics, plasma physics, and particle physics, we show that our implementation can construct kd-tree of 189 billion particles in 48 seconds on utilizing $\sim$50,000 cores. We also demonstrate computation of KNN of 19 billion queries in 12 seconds. We demonstrate almost linear speedup both for shared and distributed memory computers. Our algorithms outperforms earlier implementations by more than order of magnitude; thereby radically improving the applicability of our implementation to state-of-the-art Big Data analytics problems. In addition, we showcase performance and scalability on the recently released Intel Xeon Phi processor showing that our algorithm scales well even on massively parallel architectures.
Further improving security of Vector Stream Cipher
Venue: arXiv cs.IT 2016
Year: 2016

Vector Stream Cipher (VSC) is a stream cipher which consists of permutation polynomial over a ring of modulo $2^w$. The algorithm for generating key stream is very simple and the encryption is very fast. Some theoretical attacks for VSC have been reported so far since the invention of VSC in 2004. Then, the authors proposed some improvements and developed "Vector Stream Cipher 2.0 (VSC 2.0)" to be immune against the theoretical attacks. In this paper, we propose further improvement of VSC 2.0 to publish as a new chaos cipher "Vector Stream Cipher 2.1 (VSC2.1)". VSC 2.1 is faster and more secure than VSC 2.0. Our result suggests that permutation polynomials over a ring of modulo $2^w$ are useful for cryptography.
Cooperative Repair of Multiple Node Failures in Distributed Storage Systems
Venue: arXiv cs.IT 2016
Year: 2016

Cooperative regenerating codes are designed for repairing multiple node failures in distributed storage systems. In contrast to the original repair model of regenerating codes, which are for the repair of single node failure, data exchange among the new nodes is enabled. It is known that further reduction in repair bandwidth is possible with cooperative repair. Currently in the literature, we have an explicit construction of exact-repair cooperative code achieving all parameters corresponding to the minimum-bandwidth point. We give a slightly generalized and more flexible version of this cooperative regenerating code in this paper. For minimum-storage regeneration with cooperation, we present an explicit code construction which can jointly repair any number of systematic storage nodes.
AUGURY: A time-series based application for the analysis and forecasting of system and network performance metrics
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents AUGURY, an application for the analysis of monitoring data from computers, servers or cloud infrastructures. The analysis is based on the extraction of patterns and trends from historical data, using elements of time-series analysis. The purpose of AUGURY is to aid a server administrator by forecasting the behaviour and resource usage of specific applications and in presenting a status report in a concise manner. AUGURY provides tools for identifying network traffic congestion and peak usage times, and for making memory usage projections. The application data processing specialises in two tasks: the parametrisation of the memory usage of individual applications and the extraction of the seasonal component from network traffic data. AUGURY uses a different underlying assumption for each of these two tasks. With respect to the memory usage, a limited number of single-valued parameters are assumed to be sufficient to parameterize any application being hosted on the server. Regarding the network traffic data, long-term patterns, such as hourly or daily exist and are being induced by work-time schedules and automatised administrative jobs. In this paper, the implementation of each of the two tasks is presented, tested using locally-generated data, and applied to data from weather forecasting applications hosted on a web server. This data is used to demonstrate the insight that AUGURY can add to the monitoring of server and cloud infrastructures.
Stereo Video Deblurring
Venue: arXiv cs.CV 2016
Year: 2016

Videos acquired in low-light conditions often exhibit motion blur, which depends on the motion of the objects relative to the camera. This is not only visually unpleasing, but can hamper further processing. With this paper we are the first to show how the availability of stereo video can aid the challenging video deblurring task. We leverage 3D scene flow, which can be estimated robustly even under adverse conditions. We go beyond simply determining the object motion in two ways: First, we show how a piecewise rigid 3D scene flow representation allows to induce accurate blur kernels via local homographies. Second, we exploit the estimated motion boundaries of the 3D scene flow to mitigate ringing artifacts using an iterative weighting scheme. Being aware of 3D object motion, our approach can deal robustly with an arbitrary number of independently moving objects. We demonstrate its benefit over state-of-the-art video deblurring using quantitative and qualitative experiments on rendered scenes and real videos.
Further Results of the Cryptographic Properties on the Butterfly Structures
Venue: arXiv cs.IT 2016
Year: 2016

Recently, a new structure called butterfly introduced by Perrin et at. is attractive for that it has very good cryptographic properties: the differential uniformity is at most equal to 4 and algebraic degree is also very high when exponent $e=3$. It is conjecture that the nonlinearity is also optimal for every odd $k$, which was proposed as a open problem. In this paper, we further study the butterfly structures and show that these structure with exponent $e=2^i+1$ have also very good cryptographic properties. More importantly, we prove in theory the nonlinearity is optimal for every odd $k$, which completely solve the open problem. Finally, we study the butter structures with trivial coefficient and show these butterflies have also optimal nonlinearity. Furthermore, we show that the closed butterflies with trivial coefficient are bijective as well, which also can be used to serve as a cryptographic primitive.
Hegemonic structure of basic, clinical and patented knowledge on Ebola research: a US army reductionist initiative
Venue: arXiv cs.DL 2016
Year: 2016

Background: In this paper, we present an approach to understand how the basic, clinical and patent knowledge on Ebola is organized and intercommunicated and what leading factor could be shaping the evolution of the knowledge translation process for this disease. Methodology: A combination of citation network analysis; analysis of Medical heading Subject (MeSH) and Gene Ontology (GO) terms, and quantitative content analysis for patents and scientific literature, aimed to map the organization of Ebola research was carried out. Results: We found six putative research fronts (i.e. clusters of high interconnected papers). Three research fronts are basic research on Ebola virus structural proteins: glycoprotein, VP40 and VP35, respectively. There is a fourth research front of basic research papers on pathogenesis, which is the organizing hub of Ebola research. A fifth research front is pre-clinical research focused on vaccines and glycoproteins. Finally, a clinical-epidemiology research front related to the disease outbreaks was identified. The network structure of patent families shows that the dominant design is the use of Ebola virus proteins as targets of vaccines and other immunological treatments. Therefore, patents network organization resembles the organization of the scientific literature. Specifically, the knowledge on Ebola would flow from higher (clinical-epidemiology) to intermediated (cellular-tissular pathogenesis) to lower (molecular interactions) levels of organization. Conclusion: Our results suggest a strong reductionist approach for Ebola research probably influenced by the lethality of the disease. On the other hand, the ownership profile of the patent families network and the main researches relationship with the United State Army suggest a strong involvement of this military institution in Ebola research.
Mean-Payoff Games on Timed Automata
Venue: arXiv cs.GT 2016
Year: 2016

Mean-payoff games on timed automata are played on the infinite weighted graph of configurations of priced timed automata between two players, Player Min and Player Max, by moving a token along the states of the graph to form an infinite run. The goal of Player Min is to minimize the limit average weight of the run, while the goal of the Player Max is the opposite. Brenguier, Cassez, and Raskin recently studied a variation of these games and showed that mean-payoff games are undecidable for timed automata with five or more clocks. We refine this result by proving the undecidability of mean-payoff games with three clocks. On a positive side, we show the decidability of mean-payoff games on one-clock timed automata with binary price-rates. A key contribution of this paper is the application of dynamic programming based proof techniques applied in the context of average reward optimization on an uncountable state and action space.
Early and Late Time Acoustic Measures for Underwater Seismic Airgun Signals In Long-Term Acoustic Data Sets
Venue: arXiv cs.SD 2016
Year: 2016

This work presents a new toolkit for describing the acoustic properties of the ocean environment before, during and after a sound event caused by an underwater seismic air-gun. The toolkit uses existing sound measures, but uniquely applies these to capture the early time period (actual pulse) and late time period (reverberation and multiple arrivals). In total, 183 features are produced for each air-gun sound. This toolkit was utilized on data retrieved from a field deployment encompassing five marine autonomous recording units during a 46-day seismic air-gun survey in Baffin Bay, Greenland. Using this toolkit, a total of 147 million data points were identified from the Greenland deployment recordings. The feasibility of extracting a large number of features was then evaluated using two separate methods: a serial computer and a high performance system. Results indicate that data extraction performance took an estimated 216 hours for the serial system, and 18 hours for the high performance computer. This paper provides an analytical description of the new toolkit along with details for using it to identify relevant data.
On the Capacity of Diffusion-Based Molecular Communications with SiNW FET-Based Receiver
Venue: arXiv cs.ET 2016
Year: 2016

Molecular communication (MC) is a bio-inspired communication method based on the exchange of molecules for information transfer among nanoscale devices. Although MC has been extensively studied from various aspects, limitations imposed by the physical design of transceiving units have been largely neglected in the literature. Recently, we have proposed a nanobioelectronic MC receiver architecture based on the nanoscale field effect transistor-based biosensor (bioFET) technology, providing noninvasive and sensitive molecular detection at nanoscale while producing electrical signals at the output. In this paper, we derive analytical closed-form expressions for the capacity and capacity-achieving input distribution for a memoryless MC channel with a silicon nanowire (SiNW) FET-based MC receiver. The resulting expressions could be used to optimize the information flow in MC systems equipped with nanobioelectronic receivers.
A 58.6mW Real-Time Programmable Object Detector with Multi-Scale Multi-Object Support Using Deformable Parts Model on 1920x1080 Video at 30fps
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a programmable, energy-efficient and real-time object detection accelerator using deformable parts models (DPM), with 2x higher accuracy than traditional rigid body models. With 8 deformable parts detection, three methods are used to address the high computational complexity: classification pruning for 33x fewer parts classification, vector quantization for 15x memory size reduction, and feature basis projection for 2x reduction of the cost of each classification. The chip is implemented in 65nm CMOS technology, and can process HD (1920x1080) images at 30fps without any off-chip storage while consuming only 58.6mW (0.94nJ/pixel, 1168 GOPS/W). The chip has two classification engines to simultaneously detect two different classes of objects. With a tested high throughput of 60fps, the classification engines can be time multiplexed to detect even more than two object classes. It is energy scalable by changing the pruning factor or disabling the parts classification.
Signal Recovery in Uncorrelated and Correlated Dictionaries Using Orthogonal Least Squares
Venue: arXiv cs.IT 2016
Year: 2016

Though the method of least squares has been used for a long time in solving signal processing problems, in the recent field of sparse recovery from compressed measurements, this method has not been given much attention. In this paper we show that a method in the least squares family, known in the literature as Orthogonal Least Squares (OLS), adapted for compressed recovery problems, has competitive recovery performance and computation complexity, that makes it a suitable alternative to popular greedy methods like Orthogonal Matching Pursuit (OMP). We show that with a slight modification, OLS can exactly recover a $K$-sparse signal, embedded in an $N$ dimensional space ($K<<N$) in $M=\mathcal{O}(K\log (N/K))$ no of measurements with Gaussian dictionaries. We also show that OLS can be easily implemented in such a way that it requires $\mathcal{O}(KMN)$ no of floating point operations similar to that of OMP. In this paper performance of OLS is also studied with sensing matrices with correlated dictionary, in which algorithms like OMP does not exhibit good recovery performance. We study the recovery performance of OLS in a specific dictionary called \emph{generalized hybrid dictionary}, which is shown to be a correlated dictionary, and show numerically that OLS has is far superior to OMP in these kind of dictionaries in terms of recovery performance. Finally we provide analytical justifications that corroborate the findings in the numerical illustrations.