OpenRaiser/Intern-Atlas huggingface dataset:
On the cryptanalysis of Fridrich's chaotic image encryption scheme
Venue: arXiv cs.CR 2016
Year: 2016

Utilizing complex dynamics of chaotic maps and systems in encryption was studied comprehensively in the past two and a half decades. In 1989, Fridrich's chaotic image encryption scheme was designed by iterating chaotic position permutation and value substitution some rounds, which received intensive attention in the field of chaos-based cryptography. In 2010, Solak \textit{et al.} proposed a chosen-ciphertext attack on the Fridrich's scheme utilizing influence network between cipher-pixels and the corresponding plain-pixels. Based on their creative work, this paper scrutinized some properties of Fridrich's scheme with concise mathematical language. Then, some minor defects of the real performance of Solak's attack method were given. The work provides some bases for further optimizing attack on the Fridrich's scheme and its variants.
A Knowledge Ecosystem for the Food, Energy, and Water System
Venue: arXiv cs.DB 2016
Year: 2016

Food, energy, and water (FEW) are key resources to sustain human life and economic growth. There is an increasing stress on these interconnected resources due to population growth, natural disasters, and human activities. New research is necessary to foster more efficient, more secure, and safer use of FEW resources in the U.S. and globally. In this position paper, we present the idea of a knowledge ecosystem for enabling the semantic data integration of heterogeneous datasets in the FEW system to promote knowledge discovery and superior decision making through semantic reasoning. Rich, diverse datasets published by U.S. federal agencies will be utilized. Our knowledge ecosystem will build on Semantic Web technologies and advances in statistical relational learning to (a) represent, integrate, and harmonize diverse data sources and (b) perform ontology-based reasoning to discover actionable insights from FEW datasets.
Pose from Action: Unsupervised Learning of Pose Features based on Motion
Venue: arXiv cs.CV 2016
Year: 2016

Human actions are comprised of a sequence of poses. This makes videos of humans a rich and dense source of human poses. We propose an unsupervised method to learn pose features from videos that exploits a signal which is complementary to appearance and can be used as supervision: motion. The key idea is that humans go through poses in a predictable manner while performing actions. Hence, given two poses, it should be possible to model the motion that caused the change between them. We represent each of the poses as a feature in a CNN (Appearance ConvNet) and generate a motion encoding from optical flow maps using a separate CNN (Motion ConvNet). The data for this task is automatically generated allowing us to train without human supervision. We demonstrate the strength of the learned representation by finetuning the trained model for Pose Estimation on the FLIC dataset, for static image action recognition on PASCAL and for action recognition in videos on UCF101 and HMDB51.
Frameworks for Solving Turing Kernel Lower Bound Problem and Finding Natural Candidate Problems in NP-intermediate
Venue: arXiv cs.CC 2016
Year: 2016

Kernelization is a significant topic in parameterized complexity. Turing kernelization is a general form of kernelization. In the aspect of kernelization, an impressive hardness theory has been established [Bodlaender etc. (ICALP 2008, JCSS2009), Fortnow and Santhanam (STOC 2008, JCSS 2011), Dell and van Melkebeek (STOC 2010, J. ACM 2014), Drucker (FOCS 2012, SIAM J. Comput. 2015)], which can obtain lower bounds of kernel size. Unfortunately, there is yet no tool can prove Turing kernel lower bound for any FPT problem modulo any reasonable complexity hypothesis. Thus, constructing a framework for Turing kernel lower bound was proposed as an open problem in different occasions [Fernau etc. (STACS 2009), Misra etc. (Discrete Optimization 2011), Kratsch (Bulletin of the EATCS 2014), Cygan etc. (Dagstuhl Seminars on kernels 2014)]. Ladner [J. ACM 1975] proved that if $P \not = NP$, then there exist infinitely many NP-intermediate problems. However, the NP-intermediate problem constructed by Ladner is artificial. Thus, finding natural NP-intermediate problems under the assumption of $P \not= NP$ is a longstanding open problem in computation complexity community. This paper builds a new bridge between parameterized complexity and classic computational complexity. By using this new connection, some frameworks can be constructed. Based on the assumption that the polynomial hierarchy and the exponential hierarchy will not collapse, these frameworks have three main applications. Firstly, these frameworks can be used to obtain Turing kernel lower bounds of some important FPT problems, thus solving the first open problem. Secondly, these frameworks can also be used to obtain better kernel lower bounds for these problems. Thirdly, these frameworks can be used to figure out a large number of natural problems in NP-intermediate, thus making some contributions to the second open problem.
Efficient Integer Coefficient Search for Compute-and-Forward
Venue: arXiv cs.IT 2016
Year: 2016

Integer coefficient selection is an important decoding step in the implementation of compute-and-forward (C-F) relaying scheme. Choosing the optimal integer coefficients in C-F has been shown to be a shortest vector problem (SVP) which is known to be NP hard in its general form. Exhaustive search of the integer coefficients is only feasible in complexity for small number of users while approximation algorithms such as Lenstra-Lenstra-Lovasz (LLL) lattice reduction algorithm only find a vector within an exponential factor of the shortest vector. An optimal deterministic algorithm was proposed for C-F by Sahraei and Gastpar specifically for the real valued channel case. In this paper, we adapt their idea to the complex valued channel and propose an efficient search algorithm to find the optimal integer coefficient vectors over the ring of Gaussian integers and the ring of Eisenstein integers. A second algorithm is then proposed that generalises our search algorithm to the Integer-Forcing MIMO C-F receiver. Performance and efficiency of the proposed algorithms are evaluated through simulations and theoretical analysis.
Towards Deep Symbolic Reinforcement Learning
Venue: arXiv cs.AI 2016
Year: 2016

Deep reinforcement learning (DRL) brings the power of deep neural networks to bear on the generic task of trial-and-error learning, and its effectiveness has been convincingly demonstrated on tasks such as Atari video games and the game of Go. However, contemporary DRL systems inherit a number of shortcomings from the current generation of deep learning techniques. For example, they require very large datasets to work effectively, entailing that they are slow to learn even when such datasets are available. Moreover, they lack the ability to reason on an abstract level, which makes it difficult to implement high-level cognitive functions such as transfer learning, analogical reasoning, and hypothesis-based reasoning. Finally, their operation is largely opaque to humans, rendering them unsuitable for domains in which verifiability is important. In this paper, we propose an end-to-end reinforcement learning architecture comprising a neural back end and a symbolic front end with the potential to overcome each of these shortcomings. As proof-of-concept, we present a preliminary implementation of the architecture and apply it to several variants of a simple video game. We show that the resulting system -- though just a prototype -- learns effectively, and, by acquiring a set of symbolic rules that are easily comprehensible to humans, dramatically outperforms a conventional, fully neural DRL system on a stochastic variant of the game.
Modeling and Analysis for Cache-Enabled Networks with Dynamic Traffic
Venue: arXiv cs.IT 2016
Year: 2016

Instead of assuming fully loaded cells in the analysis on cache-enabled networks with tools of stochastic geometry, we focus on the dynamic traffic in this letter. With modeling traffic dynamics of request arrivals and departures, probabilities of full-, free-, and modest-load cells in the large-scale cache-enabled network are elaborated based on the traffic queue state. Moreover, we propose to exploit the packets cached at cache-enabled users as side information to cancel the incoming interference. Then the packet loss rates for both the cache-enabled and cache-untenable users are investigated. The simulation results verify our analysis.
Enhancing LambdaMART Using Oblivious Trees
Venue: arXiv cs.IR 2016
Year: 2016

Learning to rank is a machine learning technique broadly used in many areas such as document retrieval, collaborative filtering or question answering. We present experimental results which suggest that the performance of the current state-of-the-art learning to rank algorithm LambdaMART, when used for document retrieval for search engines, can be improved if standard regression trees are replaced by oblivious trees. This paper provides a comparison of both variants and our results demonstrate that the use of oblivious trees can improve the performance by more than $2.2\%$. Additional experimental analysis of the influence of a number of features and of a size of the training set is also provided and confirms the desirability of properties of oblivious decision trees.
Kmerlight: fast and accurate k-mer abundance estimation
Venue: arXiv cs.DS 2016
Year: 2016

k-mers (nucleotide strings of length k) form the basis of several algorithms in computational genomics. In particular, k-mer abundance information in sequence data is useful in read error correction, parameter estimation for genome assembly, digital normalization etc. We give a streaming algorithm Kmerlight for computing the k-mer abundance histogram from sequence data. Our algorithm is fast and uses very small memory footprint. We provide analytical bounds on the error guarantees of our algorithm. Kmerlight can efficiently process genome scale and metagenome scale data using standard desktop machines. Few applications of abundance histograms computed by Kmerlight are also shown. We use abundance histogram for de novo estimation of repetitiveness in the genome based on a simple probabilistic model that we propose. We also show estimation of k-mer error rate in the sampling using abundance histogram. Our algorithm can also be used for abundance estimation in a general streaming setting. The Kmerlight tool is written in C++ and is available for download and use from https://github.com/nsivad/kmerlight.
Geometry-Based Stochastic Channel Models for 5G: Extending Key Features for Massive MIMO
Venue: arXiv cs.IT 2016
Year: 2016

This paper introduces three key features in geometry-based stochastic channel models in order to include massive MIMO channels. Those key features consists of multi-user (MU) consistency, non-stationarities across the base station array and inclusion of spherical wave modelling. To ensure MU consistency, we introduce the concept of "user aura", which is a circle around the user with radius defined according to the stationarity interval. The overlap between auras determines the share of common clusters among users. To model non-stationarities across a massive array, sub-arrays are defined for which clusters are independently generated. At last, we describe a procedure to incorporate spherical wave modelling, where a cluster focal point is defined to account for distance between user and cluster.
Complementary Dual Algebraic Geometry Codes
Venue: arXiv cs.IT 2016
Year: 2016

Linear complementary dual (LCD) codes is a class of linear codes introduced by Massey in 1964. LCD codes have been extensively studied in literature recently. In addition to their applications in data storage, communications systems, and consumer electronics, LCD codes have been employed in cryptography. More specifically, it has been shown that LCD codes can also help improve the security of the information processed by sensitive devices, especially against so-called side-channel attacks (SCA) and fault non-invasive attacks. In this paper, we are interested in the construction of particular algebraic geometry (AG) LCD codes which could be good candidates to be resistant against SCA. We firstly provide a construction scheme for obtaining LCD codes from elliptic curves. Then, some explicit LCD codes from elliptic curve are presented. MDS codes are of the most importance in coding theory due to their theoretical significance and practical interests. In this paper, all the constructed LCD codes from elliptic curves are MDS or almost MDS. Some infinite classes of LCD codes from elliptic curves are optimal due to the Griesmer bound. Finally, we introduce a construction mechanism for obtaining LCD codes from any algebraic curve and derive some explicit LCD codes from hyperelliptic curves and Hermitian curves.
Low-Complexity and Basis-Free Channel Estimation for Switch-Based mmWave MIMO Systems via Matrix Completion
Venue: arXiv cs.IT 2016
Year: 2016

Recently, a switch-based hybrid massive MIMO structure that aims to reduce the hardware complexity and power consumption has been proposed as a potential candidate for millimeter wave (mmWave) communications. Exploiting the sparse nature of the mmWave channel, compressive sensing (CS)-based channel estimators have been proposed. When applied to real mmWave channels, the CS-based channel estimators may encounter heavy computational burden due to the high dimensionality of the basis. Meanwhile, knowledge about the response of the antenna array, which is needed for constructing the basis of the CS estimators, may not be perfect due to array uncertainties such as phase mismatch among array elements. This can result in the loss of sparse representation and hence the degraded performance of the CS estimator. In this paper, we propose a novel matrix completion (MC)-based low-complexity channel estimator. The proposed scheme is compatible with switch-based hybrid structures, does not need to specify a basis, and can avoid the basis mismatch issue. Compared with the existing CS-based estimator, the proposed basis-free scheme is immune to array response mismatch and exhibits a significantly lower complexity.
Monitor, Detect, Mitigate: Combating BGP Prefix Hijacking in Real-Time with ARTEMIS
Venue: arXiv cs.NI 2016
Year: 2016

The Border Gateway Protocol (BGP) is globally used by Autonomous Systems (ASes) to establish route paths for IP prefixes in the Internet. Due to the lack of authentication in BGP, an AS can hijack IP prefixes owned by other ASes (i.e., announce illegitimate route paths), impacting thus the Internet routing system and economy. To this end, a number of hijacking detection systems have been proposed. However, existing systems are usually third party services that -inherently- introduce a significant delay between the hijacking detection (by the service) and its mitigation (by the network administrators). To overcome this shortcoming, in this paper, we propose ARTEMIS, a tool that enables an AS to timely detect hijacks on its own prefixes, and automatically proceed to mitigation actions. To evaluate the performance of ARTEMIS, we conduct real hijacking experiments. To our best knowledge, it is the first time that a hijacking detection/mitigation system is evaluated through extensive experiments in the real Internet. Our results (a) show that ARTEMIS can detect (mitigate) a hijack within a few seconds (minutes) after it has been launched, and (b) demonstrate the efficiency of the different control-plane sources used by ARTEMIS, towards monitoring routing changes.
Toward a Science of Autonomy for Physical Systems: Service
Venue: arXiv cs.CY 2016
Year: 2016

A recent study by the Robotic Industries Association has highlighted how service robots are increasingly broadening our horizons beyond the factory floor. From robotic vacuums, bomb retrievers, exoskeletons and drones, to robots used in surgery, space exploration, agriculture, home assistance and construction, service robots are building a formidable resume. In just the last few years we have seen service robots deliver room service meals, assist shoppers in finding items in a large home improvement store, checking in customers and storing their luggage at hotels, and pour drinks on cruise ships. Personal robots are here to educate, assist and entertain at home. These domestic robots can perform daily chores, assist people with disabilities and serve as companions or pets for entertainment. By all accounts, the growth potential for service robotics is quite large.
A Cheap Linear Attention Mechanism with Fast Lookups and Fixed-Size Representations
Venue: arXiv cs.LG 2016
Year: 2016

The softmax content-based attention mechanism has proven to be very beneficial in many applications of recurrent neural networks. Nevertheless it suffers from two major computational limitations. First, its computations for an attention lookup scale linearly in the size of the attended sequence. Second, it does not encode the sequence into a fixed-size representation but instead requires to memorize all the hidden states. These two limitations restrict the use of the softmax attention mechanism to relatively small-scale applications with short sequences and few lookups per sequence. In this work we introduce a family of linear attention mechanisms designed to overcome the two limitations listed above. We show that removing the softmax non-linearity from the traditional attention formulation yields constant-time attention lookups and fixed-size representations of the attended sequences. These properties make these linear attention mechanisms particularly suitable for large-scale applications with extreme query loads, real-time requirements and memory constraints. Early experiments on a question answering task show that these linear mechanisms yield significantly better accuracy results than no attention, but obviously worse than their softmax alternative.
Ising spin model using Spin-Hall Effect (SHE) induced magnetization reversal in Magnetic-Tunnel-Junction
Venue: arXiv cs.ET 2016
Year: 2016

Ising spin model is considered as an efficient computing method to solve combinatorial optimization problems based on its natural tendency of convergence towards low energy state. The underlying basic functions facilitating the Ising model can be categorized into two parts, "Annealing and Majority vote". In this paper, we propose an Ising cell based on Spin Hall Effect (SHE) induced magnetization switching in a Magnetic Tunnel Junction (MTJ). The stochasticity of our proposed Ising cell based on SHE induced MTJ switching, can implement the natural annealing process by preventing the system from being stuck in solutions with local minima. Further, by controlling the current through the Heavy-Metal (HM) underlying the MTJ, we can mimic the majority vote function which determines the next state of the individual spins. By solving coupled \textit{Landau-Lifshitz-Gilbert} (LLG) equations, we demonstrate that our Ising cell can be replicated to map certain combinatorial problems. We present results for two representative problems - Maximum-cut and Graph coloring - to illustrate the feasibility of the proposed device-circuit configuration in solving combinatorial problems. Our proposed solution using a Heavy Metal (HM) based MTJ device can be exploited to implement compact, fast, and energy efficient Ising spin model.
On the Convex Geometry of Weighted Nuclear Norm Minimization
Venue: arXiv cs.IT 2016
Year: 2016

Low-rank matrix approximation, which aims to construct a low-rank matrix from an observation, has received much attention recently. An efficient method to solve this problem is to convert the problem of rank minimization into a nuclear norm minimization problem. However, soft-thresholding of singular values leads to the elimination of important information about the sensed matrix. Weighted nuclear norm minimization (WNNM) has been proposed, where the singular values are assigned different weights, in order to treat singular values differently. In this paper the solution for WNNM is analyzed under a particular weighting condition using the connection between convex geometry and compressed sensing algorithms. It is shown that the WNNM is convex where the weights are in non-descending order and there is a unique global minimizer for the minimization problem.
Incremental Sampling-based Motion Planners Using Policy Iteration Methods
Venue: arXiv cs.RO 2016
Year: 2016

Recent progress in randomized motion planners has led to the development of a new class of sampling-based algorithms that provide asymptotic optimality guarantees, notably the RRT* and the PRM* algorithms. Careful analysis reveals that the so-called "rewiring" step in these algorithms can be interpreted as a local policy iteration (PI) step (i.e., a local policy evaluation step followed by a local policy improvement step) so that asymptotically, as the number of samples tend to infinity, both algorithms converge to the optimal path almost surely (with probability 1). Policy iteration, along with value iteration (VI) are common methods for solving dynamic programming (DP) problems. Based on this observation, recently, the RRT$^{\#}$ algorithm has been proposed, which performs, during each iteration, Bellman updates (aka "backups") on those vertices of the graph that have the potential of being part of the optimal path (i.e., the "promising" vertices). The RRT$^{\#}$ algorithm thus utilizes dynamic programming ideas and implements them incrementally on randomly generated graphs to obtain high quality solutions. In this work, and based on this key insight, we explore a different class of dynamic programming algorithms for solving shortest-path problems on random graphs generated by iterative sampling methods. These class of algorithms utilize policy iteration instead of value iteration, and thus are better suited for massive parallelization. Contrary to the RRT* algorithm, the policy improvement during the rewiring step is not performed only locally but rather on a set of vertices that are classified as "promising" during the current iteration. This tends to speed-up the whole process. The resulting algorithm, aptly named Policy Iteration-RRT$^{\#}$ (PI-RRT$^{\#}$) is the first of a new class of DP-inspired algorithms for randomized motion planning that utilize PI methods.
A Large-scale Analysis of the Marketplace Characteristics in Fiverr
Venue: arXiv cs.SI 2016
Year: 2016

Crowdsourcing platforms have become quite popular due to the increasing demand of human computation-based tasks. Though the crowdsourcing systems are primarily demand-driven like MTurk, supply-driven marketplaces are becoming increasingly popular. Fiverr is a fast growing supply-driven marketplace where the sellers post micro-tasks (gigs) and users purchase them for prices as low as $5. In this paper, we study the Fiverr platform as a unique marketplace and characterize the sellers, buyers and the interactions among them. We find that sellers are more appeasing in their interactions and try to woo their buyers into buying their gigs. There are many small tightly-knit communities existing in the seller-seller network who support each other. We also study Fiverr as a seller-driven marketplace in terms of sales, churn rates, competitiveness among various sub-categories etc. and observe that while there are certain similarities with common marketplaces there are also many differences.