OpenRaiser/Intern-Atlas huggingface dataset:
An Encoding for Order-Preserving Matching
Venue: arXiv cs.DS 2017
Year: 2017

Encoding data structures store enough information to answer the queries they are meant to support but not enough to recover their underlying datasets. In this paper we give the first encoding data structure for the challenging problem of order-preserving pattern matching. This problem was introduced only a few years ago but has already attracted significant attention because of its applications in data analysis. Two strings are said to be an order-preserving match if the {\em relative order} of their characters is the same: e.g., $4, 1, 3, 2$ and $10, 3, 7, 5$ are an order-preserving match. We show how, given a string $S [1..n]$ over an arbitrary alphabet and a constant $c \geq 1$, we can build an $O (n \log \log n)$-bit encoding such that later, given a pattern $P [1..m]$ with $m \leq \lg^c n$, we can return the number of order-preserving occurrences of $P$ in $S$ in $O (m)$ time. Within the same time bound we can also return the starting position of some order-preserving match for $P$ in $S$ (if such a match exists). We prove that our space bound is within a constant factor of optimal; our query time is optimal if $\log σ= Ω(\log n)$. Our space bound contrasts with the $Ω(n \log n)$ bits needed in the worst case to store $S$ itself, an index for order-preserving pattern matching with no restrictions on the pattern length, or an index for standard pattern matching even with restrictions on the pattern length. Moreover, we can build our encoding knowing only how each character compares to $O (\lg^c n)$ neighbouring characters.
A kilobit hidden SNFS discrete logarithm computation
Venue: arXiv cs.CR 2017
Year: 2017

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software. Our chosen prime $p$ looks random, and $p--1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our p has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\mathbb{F}\_p^*$ , yet detecting that p has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of back-doored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild. As can be expected from a trapdoor mechanism which we say is hard to detect, our research did not reveal any trapdoored prime in wide use. The only way for a user to defend against a hypothetical trapdoor of this kind is to require verifiably random primes.
Energy Efficiency in Two-Tiered Wireless Sensor Networks
Venue: arXiv cs.NI 2017
Year: 2017

We study a two-tiered wireless sensor network (WSN) consisting of $N$ access points (APs) and $M$ base stations (BSs). The sensing data, which is distributed on the sensing field according to a density function $f$, is first transmitted to the APs and then forwarded to the BSs. Our goal is to find an optimal deployment of APs and BSs to minimize the average weighted total, or Lagrangian, of sensor and AP powers. For $M=1$, we show that the optimal deployment of APs is simply a linear transformation of the optimal $N$-level quantizer for density $f$, and the sole BS should be located at the geometric centroid of the sensing field. Also, for a one-dimensional network and uniform $f$, we determine the optimal deployment of APs and BSs for any $N$ and $M$. Moreover, to numerically optimize node deployment for general scenarios, we propose one- and two-tiered Lloyd algorithms and analyze their convergence properties. Simulation results show that, when compared to random deployment, our algorithms can save up to 79\% of the power on average.
Channel Training for Analog FDD Repeaters: Optimal Estimators and Cramér-Rao Bounds
Venue: arXiv cs.IT 2017
Year: 2017

For frequency division duplex channels, a simple pilot loop-back procedure has been proposed that allows the estimation of the UL & DL channels at an antenna array without relying on any digital signal processing at the terminal side. For this scheme, we derive the maximum likelihood (ML) estimators for the UL & DL channel subspaces, formulate the corresponding Cramér-Rao bounds and show the asymptotic efficiency of both (SVD-based) estimators by means of Monte Carlo simulations. In addition, we illustrate how to compute the underlying (rank-1) SVD with quadratic time complexity by employing the power iteration method. To enable power control for the data transmission, knowledge of the channel gains is needed. Assuming that the UL & DL channels have on average the same gain, we formulate the ML estimator for the channel norm, and illustrate its robustness against strong noise by means of simulations.
Model Reduction for Systems with Inhomogeneous Initial Conditions
Venue: arXiv cs.SY 2017
Year: 2017

We consider the model reduction problem for linear time-invariant dynamical systems having nonzero (but otherwise indeterminate) initial conditions. Building upon the observation that the full system response is decomposable as a superposition of the response map for an unforced system having nontrivial initial conditions and the response map for a forced system having null initial conditions, we develop a new approach that involves reducing these component responses independently and then combining the reduced responses into an aggregate reduced system response. This approach allows greater flexibility and offers better approximation properties than other comparable methods.
Language Models with Pre-Trained (GloVe) Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

In this work we implement a training of a Language Model (LM), using Recurrent Neural Network (RNN) and GloVe word embeddings, introduced by Pennigton et al. in [1]. The implementation is following the general idea of training RNNs for LM tasks presented in [2], but is rather using Gated Recurrent Unit (GRU) [3] for a memory cell, and not the more commonly used LSTM [4].
Detecting Unseen Falls from Wearable Devices using Channel-wise Ensemble of Autoencoders
Venue: arXiv cs.CV 2017
Year: 2017

A fall is an abnormal activity that occurs rarely, so it is hard to collect real data for falls. It is, therefore, difficult to use supervised learning methods to automatically detect falls. Another challenge in using machine learning methods to automatically detect falls is the choice of engineered features. In this paper, we propose to use an ensemble of autoencoders to extract features from different channels of wearable sensor data trained only on normal activities. We show that the traditional approach of choosing a threshold as the maximum of the reconstruction error on the training normal data is not the right way to identify unseen falls. We propose two methods for automatic tightening of reconstruction error from only the normal activities for better identification of unseen falls. We present our results on two activity recognition datasets and show the efficacy of our proposed method against traditional autoencoder models and two standard one-class classification methods.
An efficient strongly connected components algorithm in the fault tolerant model
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value $k\geq 1$, there is an algorithm that computes in $O(2^{k}n\log^2 n)$ time for any set $F$ of size at most $k$ the strongly connected components of the graph $G\setminus F$. The running time of our algorithm is almost optimal since the time for outputting the SCCs of $G\setminus F$ is at least $Ω(n)$. The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size $O(2^{k} n^2)$. Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.
Estimation of linear operators from scattered impulse responses
Venue: arXiv cs.IT 2017
Year: 2017

We provide a new estimator of integral operators with smooth kernels, obtained from a set of scattered and noisy impulse responses. The proposed approach relies on the formalism of smoothing in reproducing kernel Hilbert spaces and on the choice of an appropriate regularization term that takes the smoothness of the operator into account. It is numerically tractable in very large dimensions. We study the estimator's robustness to noise and analyze its approximation properties with respect to the size and the geometry of the dataset. In addition, we show minimax optimality of the proposed estimator.
Super-Resolution Delay-Doppler Estimation for OFDM Passive Radar
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider the problem of joint delay-Doppler estimation of moving targets in a passive radar that makes use of orthogonal frequency-division multiplexing (OFDM) communication signals. A compressed sensing algorithm is proposed to achieve supper-resolution and better accuracy, using both the atomic norm and the $\ell_1$-norm. The atomic norm is used to manifest the signal sparsity in the continuous domain. Unlike previous works which assume the demodulation to be error free, we explicitly introduce the demodulation error signal whose sparsity is imposed by the $\ell_1$-norm. On this basis, the delays and Doppler frequencies are estimated by solving a semidefinite program (SDP) which is convex. We also develop an iterative method for solving this SDP via the alternating direction method of multipliers (ADMM) where each iteration involves closed-form computation. Simulation results are presented to illustrate the high performance of the proposed algorithm.
The First-Order Logic of Hyperproperties
Venue: arXiv cs.LO 2017
Year: 2017

We investigate the logical foundations of hyperproperties. Hyperproperties generalize trace properties, which are sets of traces, to sets of sets of traces. The most prominent application of hyperproperties is information flow security: information flow policies characterize the secrecy and integrity of a system by comparing two or more execution traces, for example by comparing the observations made by an external observer on execution traces that result from different values of a secret variable. In this paper, we establish the first connection between temporal logics for hyperproperties and first-order logic. Kamp's seminal theorem (in the formulation due to Gabbay et al.) states that linear-time temporal logic (LTL) is expressively equivalent to first-order logic over the natural numbers with order. We introduce first-order logic over sets of traces and prove that HyperLTL, the extension of LTL to hyperproperties, is strictly subsumed by this logic. We furthermore exhibit a fragment that is expressively equivalent to HyperLTL, thereby establishing Kamp's theorem for hyperproperties.
Capacity of Clustered Distributed Storage
Venue: arXiv cs.IT 2017
Year: 2017

A new system model reflecting the clustered structure of distributed storage is suggested to investigate bandwidth requirements for repairing failed storage nodes. Large data centers with multiple racks/disks or local networks of storage devices (e.g. sensor network) are good applications of the suggested clustered model. In realistic scenarios involving clustered storage structures, repairing storage nodes using intact nodes residing in other clusters is more bandwidth-consuming than restoring nodes based on information from intra-cluster nodes. Therefore, it is important to differentiate between intra-cluster repair bandwidth and cross-cluster repair bandwidth in modeling distributed storage. Capacity of the suggested model is obtained as a function of fundamental resources of distributed storage systems, namely, storage capacity, intra-cluster repair bandwidth and cross-cluster repair bandwidth. Based on the capacity expression, feasible sets of required resources which enable reliable storage are analyzed. It is shown that the cross-cluster traffic can be minimized to zero (i.e., intra-cluster local repair becomes possible) by allowing extra resources on storage capacity and intra-cluster repair bandwidth, according to a law specified in a closed-form. Moreover, trade-off between cross-cluster traffic and intra-cluster traffic is observed for sufficiently large storage capacity.
Ten Simple Rules for Making Research Software More Robust
Venue: arXiv cs.SE 2017
Year: 2017

Software produced for research, published and otherwise, suffers from a number of common problems that make it difficult or impossible to run outside the original institution, or even off the primary developer's computer. We present ten simple rules to make such software robust enough to run anywhere, and inspire confidence in your reproducibility, and thereby delight your users and collaborators.
A Game-Theoretic Analysis of Adversarial Classification
Venue: arXiv cs.GT 2017
Year: 2017

Attack detection is usually approached as a classification problem. However, standard classification tools often perform poorly because an adaptive attacker can shape his attacks in response to the algorithm. This has led to the recent interest in developing methods for adversarial classification, but to the best of our knowledge, there have been very few prior studies that take into account the attacker's tradeoff between adapting to the classifier being used against him with his desire to maintain the efficacy of his attack. Including this effect is key to derive solutions that perform well in practice. In this investigation we model the interaction as a game between a defender who chooses a classifier to distinguish between attacks and normal behavior based on a set of observed features and an attacker who chooses his attack features (class 1 data). Normal behavior (class 0 data) is random and exogenous. The attacker's objective balances the benefit from attacks and the cost of being detected while the defender's objective balances the benefit of a correct attack detection and the cost of false alarm. We provide an efficient algorithm to compute all Nash equilibria and a compact characterization of the possible forms of a Nash equilibrium that reveals intuitive messages on how to perform classification in the presence of an attacker. We also explore qualitatively and quantitatively the impact of the non-attacker and underlying parameters on the equilibrium strategies.
Deep Learning Prototype Domains for Person Re-Identification
Venue: arXiv cs.CV 2017
Year: 2017

Person re-identification (re-id) is the task of matching multiple occurrences of the same person from different cameras, poses, lighting conditions, and a multitude of other factors which alter the visual appearance. Typically, this is achieved by learning either optimal features or matching metrics which are adapted to specific pairs of camera views dictated by the pairwise labelled training datasets. In this work, we formulate a deep learning based novel approach to automatic prototype-domain discovery for domain perceptive (adaptive) person re-id (rather than camera pair specific learning) for any camera views scalable to new unseen scenes without training data. We learn a separate re-id model for each of the discovered prototype-domains and during model deployment, use the person probe image to select automatically the model of the closest prototype domain. Our approach requires neither supervised nor unsupervised domain adaptation learning, i.e. no data available from the target domains. We evaluate extensively our model under realistic re-id conditions using automatically detected bounding boxes with low-resolution and partial occlusion. We show that our approach outperforms most of the state-of-the-art supervised and unsupervised methods on the latest CUHK-SYSU and PRW benchmarks.
Synthesis from Assume-Guarantee Contracts using Skolemized Proofs of Realizability
Venue: arXiv cs.SE 2017
Year: 2017

The realizability problem in requirements engineering is to determine the existence of an implementation that meets the given formal requirements. A step forward after realizability is proven, is to construct such an implementation automatically, and thus solve the problem of program synthesis. In this paper, we propose a novel approach to pro- gram synthesis guided by k-inductive proofs of realizability of assume- guarantee contracts constructed from safety properties. The proof of re- alizability is performed over a set of forall-exists formulas, and synthesis is per- formed by extracting Skolem functions witnessing the existential quan- tification. These Skolem functions can then be combined into an imple- mentation. Our approach is implemented in the JSyn tool which con- structs Skolem functions from a contract written in a variant of the Lus- tre programming language and then compiles the Skolem functions into a C language implementation. For a variety of benchmark models that already contained hand-written implementations, we are able to identify the usability and effectiveness of the synthesized counterparts, assuming a component-based verification framework.
Fully Dynamic Algorithm for Top-$k$ Densest Subgraphs
Venue: arXiv cs.DS 2017
Year: 2017

Given a large graph, the densest-subgraph problem asks to find a subgraph with maximum average degree. When considering the top-$k$ version of this problem, a naïve solution is to iteratively find the densest subgraph and remove it in each iteration. However, such a solution is impractical due to high processing cost. The problem is further complicated when dealing with dynamic graphs, since adding or removing an edge requires re-running the algorithm. In this paper, we study the top-$k$ densest-subgraph problem in the sliding-window model and propose an efficient fully-dynamic algorithm. The input of our algorithm consists of an edge stream, and the goal is to find the node-disjoint subgraphs that maximize the sum of their densities. In contrast to existing state-of-the-art solutions that require iterating over the entire graph upon any update, our algorithm profits from the observation that updates only affect a limited region of the graph. Therefore, the top-$k$ densest subgraphs are maintained by only applying local updates. We provide a theoretical analysis of the proposed algorithm and show empirically that the algorithm often generates denser subgraphs than state-of-the-art competitors. Experiments show an improvement in efficiency of up to five orders of magnitude compared to state-of-the-art solutions.
Leveraging Diversity and Sparsity in Blind Deconvolution
Venue: arXiv cs.IT 2017
Year: 2017

This paper considers recovering $L$-dimensional vectors $\boldsymbol{w}$, and $\boldsymbol{x}_1,\boldsymbol{x}_2, \ldots, \boldsymbol{x}_N$ from their circular convolutions $\boldsymbol{y}_n = \boldsymbol{w}*\boldsymbol{x}_n, \ n = 1,2,3, \ldots, N$. The vector $\boldsymbol{w}$ is assumed to be $S$-sparse in a known basis that is spread out in the Fourier domain, and each input $\boldsymbol{x}_n$ is a member of a known $K$-dimensional random subspace. We prove that whenever $K + S\log^2S \lesssim L /\log^4(LN)$, the problem can be solved effectively by using only the nuclear-norm minimization as the convex relaxation, as long as the inputs are sufficiently diverse and obey $N \gtrsim \log^2(LN)$. By "diverse inputs", we mean that the $\boldsymbol{x}_n$'s belong to different, generic subspaces. To our knowledge, this is the first theoretical result on blind deconvolution where the subspace to which $\boldsymbol{w}$ belongs is not fixed, but needs to be determined. We discuss the result in the context of multipath channel estimation in wireless communications. Both the fading coefficients, and the delays in the channel impulse response $\boldsymbol{w}$ are unknown. The encoder codes the $K$-dimensional message vectors randomly and then transmits coded messages $\boldsymbol{x}_n$'s over a fixed channel one after the other. The decoder then discovers all of the messages and the channel response when the number of samples taken for each received message are roughly greater than $(K+S\log^2S)\log^4(LN)$, and the number of messages is roughly at least $\log^2(LN)$.
Foundations of Modern Query Languages for Graph Databases
Venue: arXiv cs.DB 2017
Year: 2017

We survey foundational features underlying modern graph query languages. We first discuss two popular graph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges; and property graphs, where nodes and edges can further have attributes. Next we discuss the two most fundamental graph querying functionalities: graph patterns and navigational expressions. We start with graph patterns, in which a graph-structured query is matched against the data. Thereafter we discuss navigational expressions, in which patterns can be matched recursively against the graph to navigate paths of arbitrary length; we give an overview of what kinds of expressions have been proposed, and how they can be combined with graph patterns. We also discuss several semantics under which queries using the previous features can be evaluated, what effects the selection of features and semantics has on complexity, and offer examples of such features in three modern languages that are used to query graphs: SPARQL, Cypher and Gremlin. We conclude by discussing the importance of formalisation for graph query languages; a summary of what is known about SPARQL, Cypher and Gremlin in terms of expressivity and complexity; and an outline of possible future directions for the area.
Lexicon Integrated CNN Models with Attention for Sentiment Analysis
Venue: arXiv cs.CL 2017
Year: 2017

With the advent of word embeddings, lexicons are no longer fully utilized for sentiment analysis although they still provide important features in the traditional setting. This paper introduces a novel approach to sentiment analysis that integrates lexicon embeddings and an attention mechanism into Convolutional Neural Networks. Our approach performs separate convolutions for word and lexicon embeddings and provides a global view of the document using attention. Our models are experimented on both the SemEval'16 Task 4 dataset and the Stanford Sentiment Treebank, and show comparative or better results against the existing state-of-the-art systems. Our analysis shows that lexicon embeddings allow to build high-performing models with much smaller word embeddings, and the attention mechanism effectively dims out noisy words for sentiment analysis.