OpenRaiser/Intern-Atlas huggingface dataset:
Parity Games and Automata for Game Logic (Extended Version)
Venue: arXiv cs.LO 2017
Year: 2017

Parikh's game logic is a PDL-like fixpoint logic interpreted on monotone neighbourhood frames that represent the strategic power of players in determined two-player games. Game logic translates into a fragment of the monotone $μ$-calculus, which in turn is expressively equivalent to monotone modal automata. Parity games and automata are important tools for dealing with the combinatorial complexity of nested fixpoints in modal fixpoint logics, such as the modal $μ$-calculus. In this paper, we (1) discuss the semantics a of game logic over neighbourhood structures in terms of parity games, and (2) use these games to obtain an automata-theoretic characterisation of the fragment of the monotone $μ$-calculus that corresponds to game logic. Our proof makes extensive use of structures that we call syntax graphs that combine the ease-of-use of syntax trees of formulas with the flexibility and succinctness of automata. They are essentially a graph-based view of the alternating tree automata that were introduced by Wilke in the study of modal $μ$-calculus.
Lower bounds on the lifting degree of single-edge and multiple-edge QC-LDPC codes by difference matrices
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we define two matrices named as "difference matrices", denoted by $D$ and $DD$ which significantly contribute to achieve regular single-edge QC-LDPC codes with the shortest length and the certain girth as well as regular and irregular multiple-edge QC-LDPC codes. Making use of these matrices, we obtain necessary and sufficient conditions to have single-edge $(m,n)$-regular QC-LDPC codes with girth 6, 10 and 12. Additionally, for girth 6, we achieve all non-isomorphic codes with the minimum lifting degree, $N$, for $m=4$ and $5\leq n\leq 11$, and present an exponent matrix for each minimum distance. For girth 10, we provide a lower bound on the lifting degree which is tighter than the existing bound. More important, for an exponent matrix whose first row and first column are all-zero, we demonstrate that the non-existence of 8-cycles proves the non-existence of 6-cycles related to the first row of the exponent matrix too. All non-isomorphic QC-LDPC codes with girth 10 and $n=5,6$ whose numbers are more than those presented in the literature are provided. For $n=7,8$ we decrease the lifting degrees from 159 and 219 to 145 and 211, repectively. For girth 12, a lower bound on the lifting degree is achieved. For multiple-edge category, for the first time a lower bound on the lifting degree for both regular and irregular QC-LDPC codes with girth 6 is achieved. We also demonstrate that the achieved lower bounds on multiple-edge $(4,n)$-regular QC-LDPC codes with girth 6 are tight and the resultant codes have shorter length compared to their counterparts in single-edge codes. Additionally, difference matrices help to reduce the conditions of considering 6-cycles from seven states to five states. We obtain multiple-edge $(4,n)$-regular QC-LDPC codes with girth 8 and $n=4,6,8$ with the shortest length.
Bisimulation and Hennessy-Milner Logic for Generalized Synchronization Trees
Venue: arXiv cs.LO 2017
Year: 2017

In this work, we develop a generalization of Hennessy-Milner Logic (HML) for Generalized Synchronization Trees (GSTs) that we call Generalized Hennessy Milner Logic (GHML). Importantly, this logic suggests a strong relationship between (weak) bisimulation for GSTs and ordinary bisimulation for Synchronization Trees (STs). We demonstrate that this relationship can be used to define the GST analog for image-finiteness of STs. Furthermore, we demonstrate that certain maximal Hennessy-Milner classes of STs have counterparts in maximal Hennessy-Milner classes of GSTs with respect to GST weak bisimulation. We also exhibit some interesting characteristics of these maximal Hennessy-Milner classes of GSTs.
Neural Distributed Autoassociative Memories: A Survey
Venue: arXiv cs.NE 2017
Year: 2017

Introduction. Neural network models of autoassociative, distributed memory allow storage and retrieval of many items (vectors) where the number of stored items can exceed the vector dimension (the number of neurons in the network). This opens the possibility of a sublinear time search (in the number of stored items) for approximate nearest neighbors among vectors of high dimension. The purpose of this paper is to review models of autoassociative, distributed memory that can be naturally implemented by neural networks (mainly with local learning rules and iterative dynamics based on information locally available to neurons). Scope. The survey is focused mainly on the networks of Hopfield, Willshaw and Potts, that have connections between pairs of neurons and operate on sparse binary vectors. We discuss not only autoassociative memory, but also the generalization properties of these networks. We also consider neural networks with higher-order connections and networks with a bipartite graph structure for non-binary data with linear constraints. Conclusions. In conclusion we discuss the relations to similarity search, advantages and drawbacks of these techniques, and topics for further research. An interesting and still not completely resolved question is whether neural autoassociative memories can search for approximate nearest neighbors faster than other index structures for similarity search, in particular for the case of very high dimensional vectors.
Automation of Android Applications Testing Using Machine Learning Activities Classification
Venue: arXiv cs.SE 2017
Year: 2017

Mobile applications are being used every day by more than half of the world's population to perform a great variety of tasks. With the increasingly widespread usage of these applications, the need arises for efficient techniques to test them. Many frameworks allow automating the process of application testing, however existing frameworks mainly rely on the application developer for providing testing scripts for each developed application, thus preventing reuse of these tests for similar applications. In this paper, we present a novel approach for the automation of testing Android applications by leveraging machine learning techniques and reusing popular test scenarios. We discuss and demonstrate the potential benefits of our approach in an empirical study where we show that our developed testing tool, based on the proposed approach, outperforms standard methods in realistic settings.
Grasp selection analysis for two-step manipulation tasks
Venue: arXiv cs.RO 2017
Year: 2017

Manipulation tasks are sequential in nature. Grasp selection approaches that take into account the con- straints at each task step are critical, since they allow to both (1) Identify grasps that likely require simple arm motions through the whole task and (2) To discard grasps that, although feasible to achieve at earlier steps, might not be executable at later stages due to goal task constraints. In this paper, we study how to use our previously proposed manipulation metric for tasks in which 2 steps are required (pick-and-place and pouring tasks). Even for such simple tasks, it was not clear how to use the results of applying our metric (or any metric for that matter) to rank all the candidate grasps: Should only the start state be considered, or only the goal, or a combination of both? In order to find an answer, we evaluated the (best) grasps selected by our metric under each of these 3 considerations. Our main conclusion was that for tasks in which the goal state is more constrained (pick-and-place), using a combination of the metric measured at the start and goal states renders better performance when compared with choosing any other candidate grasp, whereas in tasks in which the goal constraints are less rigidly defined, the metric measured at the start state should be mainly considered. We present quantitative results in simulation and validate our approach's practicality with experimental results in our physical robot manipulator, Crichton.
Tor's Been KIST: A Case Study of Transitioning Tor Research to Practice
Venue: arXiv cs.CR 2017
Year: 2017

Most computer science research is aimed at solving difficult problems with a goal of sharing the developed solutions with the greater research community. For many researchers, a project ends when the paper is published even though a much broader impact could be achieved by spending additional effort to transition that research to real world usage. In this paper, we examine the opportunities and challenges in transitioning Tor research through a case study of deploying a previously proposed application layer socket scheduling policy called KIST into the Tor network. We implement KIST, simulate it in a 2,000-relay private Tor network using Shadow, deploy it on a Tor relay running in the public Tor network, and measure its performance impact. Confirming the results reported in prior research, we find that KIST reduces kernel outbound queuing times for relays and download times for low-volume or bursty clients. We also find that client and relay performance with KIST increases as network load and packet loss rates increase, although the effects of packet loss on KIST were overlooked in past work. Our implementation will be released as open-source software for inclusion in a future Tor release.
Fundamental Limits of Cache-Aided Private Information Retrieval with Unknown and Uncoded Prefetching
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of private information retrieval (PIR) from $N$ non-colluding and replicated databases when the user is equipped with a cache that holds an uncoded fraction $r$ from each of the $K$ stored messages in the databases. We assume that the databases are unaware of the cache content. We investigate $D^*(r)$ the optimal download cost normalized with the message size as a function of $K$, $N$, $r$. For a fixed $K$, $N$, we develop an inner bound (converse bound) for the $D^*(r)$ curve. The inner bound is a piece-wise linear function in $r$ that consists of $K$ line segments. For the achievability, we develop explicit schemes that exploit the cached bits as side information to achieve $K-1$ non-degenerate corner points. These corner points differ in the number of cached bits that are used to generate one side information equation. We obtain an outer bound (achievability) for any caching ratio by memory-sharing between these corner points. Thus, the outer bound is also a piece-wise linear function in $r$ that consists of $K$ line segments. The inner and the outer bounds match in general for the cases of very low caching ratio ($r \leq \frac{1}{1+N+N^2+\cdots+N^{K-1}}$) and very high caching ratio ($r \geq \frac{K-2}{(N+1)K+N^2-2N-2}$). As a corollary, we fully characterize the optimal download cost caching ratio tradeoff for $K=3$. For general $K$, $N$, and $r$, we show that the largest gap between the achievability and the converse bounds is $\frac{1}{6}$. Our results show that the download cost can be reduced beyond memory-sharing if the databases are unaware of the cached content.
Distributed circular formation flight of fixed-wing aircraft with Paparazzi autopilot
Venue: arXiv cs.RO 2017
Year: 2017

In this paper we introduce the usage of guidance vector fields for the coordination and formation flight of fixed-wing aircraft. In particular, we describe in detail the technological implementation of the formation flight control for a fully distributed execution of the algorithm by employing the open-source project Paparazzi. In this context, distributed means that each aircraft executes the algorithm on board, each aircraft only needs information about its neighbors, and the implementation is straightforwardly scalable to an arbitrary number of vehicles, i.e., the needed resources such as memory or computational power not necessarily scale with the number of total aircraft. The coordination is based on commanding the aircraft to track circumferences with different radii but sharing the same center. Consequently, the vehicles will travel different distances but with the same speeds in order to control their relative angles in the circumference, i.e., their orbital velocities. We show the effectiveness of the proposed design with actual formation flights during the drone parade in IMAV2017.
Optimal deep neural networks for sparse recovery via Laplace techniques
Venue: arXiv cs.IT 2017
Year: 2017

This paper introduces Laplace techniques for designing a neural network, with the goal of estimating simplex-constraint sparse vectors from compressed measurements. To this end, we recast the problem of MMSE estimation (w.r.t. a pre-defined uniform input distribution) as the problem of computing the centroid of some polytope that results from the intersection of the simplex and an affine subspace determined by the measurements. Owing to the specific structure, it is shown that the centroid can be computed analytically by extending a recent result that facilitates the volume computation of polytopes via Laplace transformations. A main insight of this paper is that the desired volume and centroid computations can be performed by a classical deep neural network comprising threshold functions, rectified linear (ReLU) and rectified polynomial (ReP) activation functions. The proposed construction of a deep neural network for sparse recovery is completely analytic so that time-consuming training procedures are not necessary. Furthermore, we show that the number of layers in our construction is equal to the number of measurements which might enable novel low-latency sparse recovery algorithms for a larger class of signals than that assumed in this paper. To assess the applicability of the proposed uniform input distribution, we showcase the recovery performance on samples that are soft-classification vectors generated by two standard datasets. As both volume and centroid computation are known to be computationally hard, the network width grows exponentially in the worst-case. It can be, however, decreased by inducing sparse connectivity in the neural network via a well-suited basis of the affine subspace. Finally, the presented analytical construction may serve as a viable initialization to be further optimized and trained using particular input datasets at hand.
Compositional Approaches for Representing Relations Between Words: A Comparative Study
Venue: arXiv cs.CL 2017
Year: 2017

Identifying the relations that exist between words (or entities) is important for various natural language processing tasks such as, relational search, noun-modifier classification and analogy detection. A popular approach to represent the relations between a pair of words is to extract the patterns in which the words co-occur with from a corpus, and assign each word-pair a vector of pattern frequencies. Despite the simplicity of this approach, it suffers from data sparseness, information scalability and linguistic creativity as the model is unable to handle previously unseen word pairs in a corpus. In contrast, a compositional approach for representing relations between words overcomes these issues by using the attributes of each individual word to indirectly compose a representation for the common relations that hold between the two words. This study aims to compare different operations for creating relation representations from word-level representations. We investigate the performance of the compositional methods by measuring the relational similarities using several benchmark datasets for word analogy. Moreover, we evaluate the different relation representations in a knowledge base completion task.
Sparse Data Driven Mesh Deformation
Venue: arXiv cs.GR 2017
Year: 2017

Example-based mesh deformation methods are powerful tools for realistic shape editing. However, existing techniques typically combine all the example deformation modes, which can lead to overfitting, i.e. using a overly complicated model to explain the user-specified deformation. This leads to implausible or unstable deformation results, including unexpected global changes outside the region of interest. To address this fundamental limitation, we propose a sparse blending method that automatically selects a smaller number of deformation modes to compactly describe the desired deformation. This along with a suitably chosen deformation basis including spatially localized deformation modes leads to significant advantages, including more meaningful, reliable, and efficient deformations because fewer and localized deformation modes are applied. To cope with large rotations, we develop a simple but effective representation based on polar decomposition of deformation gradients, which resolves the ambiguity of large global rotations using an as-consistent-as-possible global optimization. This simple representation has a closed form solution for derivatives, making it efficient for sparse localized representation and thus ensuring interactive performance. Experimental results show that our method outperforms state-of-the-art data-driven mesh deformation methods, for both quality of results and efficiency.
Optimal Power Allocation by Imperfect Hardware Analysis in Untrusted Relaying Networks
Venue: arXiv cs.CR 2017
Year: 2017

By taking a variety of realistic hardware imperfections into consideration, we propose an optimal power allocation (OPA) strategy to maximize the instantaneous secrecy rate of a cooperative wireless network comprised of a source, a destination and an untrusted amplify-and-forward (AF) relay. We assume that either the source or the destination is equipped with a large-scale multiple antennas (LSMA) system, while the rest are equipped with a single antenna. To prevent the untrusted relay from intercepting the source message, the destination sends an intended jamming noise to the relay, which is referred to as destination-based cooperative jamming (DBCJ). Given this system model, novel closed-form expressions are presented in the high signal-to-noise ratio (SNR) regime for the ergodic secrecy rate (ESR) and the secrecy outage probability (SOP). We further improve the secrecy performance of the system by optimizing the associated hardware design. The results reveal that by beneficially distributing the tolerable hardware imperfections across the transmission and reception radio-frequency (RF) front ends of each node, the system's secrecy rate may be improved. The engineering insight is that equally sharing the total imperfections at the relay between the transmitter and the receiver provides the best secrecy performance. Numerical results illustrate that the proposed OPA together with the most appropriate hardware design significantly increases the secrecy rate.
Distributed Data Stream Processing and Edge Computing: A Survey on Resource Elasticity and Future Directions
Venue: arXiv cs.DC 2017
Year: 2017

Under several emerging application scenarios, such as in smart cities, operational monitoring of large infrastructure, wearable assistance, and Internet of Things, continuous data streams must be processed under very short delays. Several solutions, including multiple software engines, have been developed for processing unbounded data streams in a scalable and efficient manner. More recently, architecture has been proposed to use edge computing for data stream processing. This paper surveys state of the art on stream processing engines and mechanisms for exploiting resource elasticity features of cloud computing in stream processing. Resource elasticity allows for an application or service to scale out/in according to fluctuating demands. Although such features have been extensively investigated for enterprise applications, stream processing poses challenges on achieving elastic systems that can make efficient resource management decisions based on current load. Elasticity becomes even more challenging in highly distributed environments comprising edge and cloud computing resources. This work examines some of these challenges and discusses solutions proposed in the literature to address them.
Did we learn from LLC Side Channel Attacks? A Cache Leakage Detection Tool for Crypto Libraries
Venue: arXiv cs.CR 2017
Year: 2017

This work presents a new tool to verify the correctness of cryptographic implementations with respect to cache attacks. Our methodology discovers vulnerabilities that are hard to find with other techniques, observed as exploitable leakage. The methodology works by identifying secret dependent memory and introducing forced evictions inside potentially vulnerable code to obtain cache traces that are analyzed using Mutual Information. If dependence is observed, the cryptographic implementation is classified as to leak information. We demonstrate the viability of our technique in the design of the three main cryptographic primitives, i.e., AES, RSA and ECC, in eight popular up to date cryptographic libraries, including OpenSSL, Libgcrypt, Intel IPP and NSS. Our results show that cryptographic code designers are far away from incorporating the appropriate countermeasures to avoid cache leakages, as we found that 50% of the default implementations analyzed leaked information that lead to key extraction. We responsibly notified the designers of all the leakages found and suggested patches to solve these vulnerabilities.
Ergodic Exploration using Binary Sensing for Non-Parametric Shape Estimation
Venue: arXiv cs.RO 2017
Year: 2017

Current methods to estimate object shape---using either vision or touch---generally depend on high-resolution sensing. Here, we exploit ergodic exploration to demonstrate successful shape estimation when using a low-resolution binary contact sensor. The measurement model is posed as a collision-based tactile measurement, and classification methods are used to discriminate between shape boundary regions in the search space. Posterior likelihood estimates of the measurement model help the system actively seek out regions where the binary sensor is most likely to return informative measurements. Results show successful shape estimation of various objects as well as the ability to identify multiple objects in an environment. Interestingly, it is shown that ergodic exploration utilizes non-contact motion to gather significant information about shape. The algorithm is extended in three dimensions in simulation and we present two dimensional experimental results using the Rethink Baxter robot.
Optimizing for Measure of Performance in Max-Margin Parsing
Venue: arXiv cs.CL 2017
Year: 2017

Many statistical learning problems in the area of natural language processing including sequence tagging, sequence segmentation and syntactic parsing has been successfully approached by means of structured prediction methods. An appealing property of the corresponding discriminative learning algorithms is their ability to integrate the loss function of interest directly into the optimization process, which potentially can increase the resulting performance accuracy. Here, we demonstrate on the example of constituency parsing how to optimize for F1-score in the max-margin framework of structural SVM. In particular, the optimization is with respect to the original (not binarized) trees.