OpenRaiser/Intern-Atlas huggingface dataset:
Cooperative Handover Management in Dense Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Network densification has always been an important factor to cope with the ever increasing capacity demand. Deploying more base stations (BSs) improves the spatial frequency utilization, which increases the network capacity. However, such improvement comes at the expense of shrinking the BSs' footprints, which increases the handover (HO) rate and may diminish the foreseen capacity gains. In this paper, we propose a cooperative HO management scheme to mitigate the HO effect on throughput gains achieved via cellular network densification. The proposed HO scheme relies on skipping HO to the nearest BS at some instances along the user's trajectory while enabling cooperative BS service during HO execution at other instances. To this end, we develop a mathematical model, via stochastic geometry, to quantify the performance of the proposed HO scheme in terms of coverage probability and user throughput. The results show that the proposed cooperative HO scheme outperforms the always best connected based association at high mobility. Also, the value of BS cooperation along with handover skipping is quantified with respect to the HO skipping only that has recently appeared in the literature. Particularly, the proposed cooperative HO scheme shows throughput gains of 12% to 27% and 17% on average, when compared to the always best connected and HO skipping only schemes at user velocity ranging from 80 km/h to 160 Km/h, respectively.
Compiling Stateful Network Properties for Runtime Verification
Venue: arXiv cs.NI 2016
Year: 2016

Networks are difficult to configure correctly, and tricky to debug. These problems are accentuated by temporal and stateful behavior. Static verification, while useful, is ineffectual for detecting behavioral deviations induced by hardware faults, security failures, and so on, so dynamic property monitoring is also valuable. Unfortunately, existing monitoring and runtime verification for networks largely focuses on properties about individual packets (such as connectivity) or requires a digest of all network events be sent to a server, incurring enormous cost. We present a network monitoring system that avoids these problems. Because traces of network events correspond well to temporal logic, we use a subset of Metric First-Order Temporal Logic as the query language. These queries are compiled down to execute completely on the network switches. This vastly reduces network load, improves the precision of queries, and decreases detection latency. We show the practical feasibility of our work by extending a widely-used software switch and deploying it on networks. Our work also suggests improvements to network instruction sets to better support temporal monitoring.
Learning in Quantum Control: High-Dimensional Global Optimization for Noisy Quantum Dynamics
Venue: arXiv cs.LG 2016
Year: 2016

Quantum control is valuable for various quantum technologies such as high-fidelity gates for universal quantum computing, adaptive quantum-enhanced metrology, and ultra-cold atom manipulation. Although supervised machine learning and reinforcement learning are widely used for optimizing control parameters in classical systems, quantum control for parameter optimization is mainly pursued via gradient-based greedy algorithms. Although the quantum fitness landscape is often compatible with greedy algorithms, sometimes greedy algorithms yield poor results, especially for large-dimensional quantum systems. We employ differential evolution algorithms to circumvent the stagnation problem of non-convex optimization. We improve quantum control fidelity for noisy system by averaging over the objective function. To reduce computational cost, we introduce heuristics for early termination of runs and for adaptive selection of search subspaces. Our implementation is massively parallel and vectorized to reduce run time even further. We demonstrate our methods with two examples, namely quantum phase estimation and quantum gate design, for which we achieve superior fidelity and scalability than obtained using greedy algorithms.
Side-Channel Attack Resilience through Route Randomisation in Secure Real-Time Networks-on-Chip
Venue: arXiv cs.DC 2016
Year: 2016

Security can be seen as an optimisation objective in NoC resource management, and as such poses trade-offs against other objectives such as real-time schedulability. In this paper, we show how to increase NoC resilience against a concrete type of security attack, named side-channel attack, which exploit the correlation between specific non-functional properties (such as packet latencies and routes, in the case of NoCs) to infer the functional behaviour of secure applications. For instance, the transmission of a packet over a given link of the NoC may hint on a cache miss, which can be used by an attacker to guess specific parts of a secret cryptographic key, effectively weakening it. We therefore propose packet route randomisation as a mechanism to increase NoC resilience against side-channel attacks, focusing specifically on the potential impact of such an approach upon hard real-time systems, where schedulability is a vital design requirement. Using an evolutionary optimisation approach, we show how to effectively apply route randomisation in such a way that it can increase NoC security while controlling its impact on hard real-time performance guarantees. Extensive experimental evidence based on analytical and simulation models supports our findings.
The Lax-Milgram Theorem. A detailed proof to be formalized in Coq
Venue: arXiv cs.LO 2016
Year: 2016

To obtain the highest confidence on the correction of numerical simulation programs implementing the finite element method, one has to formalize the mathematical notions and results that allow to establish the soundness of the method. The Lax-Milgram theorem may be seen as one of those theoretical cornerstones: under some completeness and coercivity assumptions, it states existence and uniqueness of the solution to the weak formulation of some boundary value problems. The purpose of this document is to provide the formal proof community with a very detailed pen-and-paper proof of the Lax-Milgram theorem.
San Francisco Crime Classification
Venue: arXiv cs.LG 2016
Year: 2016

San Francisco Crime Classification is an online competition administered by Kaggle Inc. The competition aims at predicting the future crimes based on a given set of geographical and time-based features. In this paper, I achieved a an accuracy that ranks at top %18, as of May 19th, 2016. I will explore the data, and explain in details the tools I used to achieve that result.
LTL-based Verification of Reconfigurable Workflows
Venue: arXiv cs.SE 2016
Year: 2016

Logics and model-checking have been successfully used in the last decades for modeling and verification of various types of hardware (and software) systems. While most languages and techniques emerged in a context of monolithic systems with a limited self-adaptability, modern systems require approaches able to cope with dynamically changing requirements and emergent behaviors. The emphasis on system reconfigurability has not been followed by an adequate research effort, and the current state of the art lacks logics and model checking paradigms that can describe and analyze complex modern systems in a comprehensive way. This paper describes a case study involving the dynamic reconfiguration of an office workflow. We state the requirements on a system implementing the workflow and its reconfiguration and we prove workflow reconfiguration termination by providing a compilation of generic workflows into LTL, using the Bound model checker Zot. The objective of this paper is demonstrating how temporal logics and model checking are effective in proving properties of dynamic, reconfigurable and adaptable systems. This simple case study is just a "proof of concept" to demonstrate the feasibility of our ideas.
Open, privacy-preserving protocols for lawful surveillance
Venue: arXiv cs.CR 2016
Year: 2016

The question of how government agencies can acquire actionable, useful information about legitimate but unknown targets without intruding upon the electronic activity of innocent parties is extremely important. We address this question by providing experimental evidence that actionable, useful information can indeed be obtained in a manner that preserves the privacy of innocent parties and that holds government agencies accountable. In particular, we present practical, privacy-preserving protocols for two operations that law-enforcement and intelligence agencies have used effectively: set intersection and contact chaining. Experiments with our protocols suggest that privacy-preserving contact chaining can perform a 3-hop privacy-preserving graph traversal producing 27,000 ciphertexts in under two minutes. These ciphertexts are usable in turn via privacy-preserving set intersection to pinpoint potential unknown targets within a body of 150,000 total ciphertexts within 10 minutes, without exposing personal information about non-targets.
Breaking the Economic Barrier of Caching in Cellular Networks: Incentives and Contracts
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, a novel approach for providing incentives for caching in small cell networks (SCNs) is proposed based on the economics framework of contract theory. In this model, a mobile network operator (MNO) designs contracts that will be offered to a number of content providers (CPs) to motivate them to cache their content at the MNO's small base stations (SBSs). A practical model in which information about the traffic generated by the CPs' users is not known to the MNO is considered. Under such asymmetric information, the incentive contract between the MNO and each CP is properly designed so as to determine the amount of allocated storage to the CP and the charged price by the MNO. The contracts are derived by the MNO in a way to maximize the global benefit of the CPs and prevent them from using their private information to manipulate the outcome of the caching process. For this interdependent contract model, the closed-form expressions of the price and the allocated storage space to each CP are derived. This proposed mechanism is shown to satisfy the sufficient and necessary conditions for the feasibility of a contract. Moreover, it is shown that the proposed pricing model is budget balanced, enabling the MNO to cover all the caching expenses via the prices charged to the CPs. Simulation results show that none of the CPs will have an incentive to choose a contract designed for CPs with different traffic loads.
Streaming Algorithms For Computing Edit Distance Without Exploiting Suffix Trees
Venue: arXiv cs.DS 2016
Year: 2016

The edit distance is a way of quantifying how similar two strings are to one another by counting the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. In this paper we study the computational problem of computing the edit distance between a pair of strings where their distance is bounded by a parameter $k\ll n$. We present two streaming algorithms for computing edit distance: One runs in time $O(n+k^2)$ and the other $n+O(k^3)$. By writing $n+O(k^3)$ we want to emphasize that the number of operations per an input symbol is a small constant. In particular, the running time does not depend on the alphabet size, and the algorithm should be easy to implement. Previously a streaming algorithm with running time $O(n+k^4)$ was given in the paper by the current authors (STOC'16). The best off-line algorithm runs in time $O(n+k^2)$ (Landau et al., 1998) which is known to be optimal under the Strong Exponential Time Hypothesis.
A simple multiforce layout for multiplex networks
Venue: arXiv cs.SI 2016
Year: 2016

We introduce multiforce, a force-directed layout for multiplex networks, where the nodes of the network are organized into multiple layers and both in-layer and inter-layer relationships among nodes are used to compute node coordinates. The proposed approach generalizes existing work, providing a range of intermediate layouts in-between the ones produced by known methods. Our experiments on real data show that multiforce can keep nodes well aligned across different layers without significantly affecting their internal layouts when the layers have similar or compatible topologies. As a consequence, multiforce enriches the benefits of force-directed layouts by also supporting the identification of topological correspondences between layers.
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
Venue: arXiv cs.DS 2016
Year: 2016

A function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $ε$-close to some $k$-junta and reject any function that is $ε'$-far from every $k'$-junta for some $ε'= O(ε)$ and $k' = O(k)$. Our first result is an algorithm that solves this problem with query complexity polynomial in $k$ and $1/ε$. This result is obtained via a new polynomial-time approximation algorithm for submodular function minimization (SFM) under large cardinality constraints, which holds even when only given an approximate oracle access to the function. Our second result considers the case where $k'=k$. We show how to obtain a smooth tradeoff between the amount of tolerance and the query complexity in this setting. Specifically, we design an algorithm that given $ρ\in(0,1/2)$ accepts any function that is $\frac{ερ}{16}$-close to some $k$-junta and rejects any function that is $ε$-far from every $k$-junta. The query complexity of the algorithm is $O\big( \frac{k\log k}{ερ(1-ρ)^k} \big)$. Finally, we show how to apply the second result to the problem of tolerant isomorphism testing between two unknown Boolean functions $f$ and $g$. We give an algorithm for this problem whose query complexity only depends on the (unknown) smallest $k$ such that either $f$ or $g$ is close to being a $k$-junta.
Generalized Sampling in Julia
Venue: arXiv cs.MS 2016
Year: 2016

Generalized sampling is a numerically stable framework for obtaining reconstructions of signals in different bases and frames from their samples. In this paper, we will introduce a carefully documented toolbox for performing generalized sampling in Julia. Julia is a new language for technical computing with focus on performance, which is ideally suited to handle the large size problems often encountered in generalized sampling. The toolbox provides specialized solutions for the setup of Fourier bases and wavelets. The performance of the toolbox is compared to existing implementations of generalized sampling in MATLAB.
Using Recurrent Neural Network for Learning Expressive Ontologies
Venue: arXiv cs.CL 2016
Year: 2016

Recently, Neural Networks have been proven extremely effective in many natural language processing tasks such as sentiment analysis, question answering, or machine translation. Aiming to exploit such advantages in the Ontology Learning process, in this technical report we present a detailed description of a Recurrent Neural Network based system to be used to pursue such goal.
Design of an intermediate representation for query languages
Venue: arXiv cs.PL 2016
Year: 2016

Data oriented applications, usually written in a high-level, general-purpose programming language (such as Java) interact with database through a coarse interface. Informally, the text of a query is built on the application side (either via plain string concatenation or through an abstract notion of statement) and shipped to the database over the wire where it is executed. The results are then serialized and sent back to the "client-code" where they are translated in the language's native datatypes. This round trip is detrimental to performances but, worse, such a programming model prevents one from having richer queries, namely queries containing user-defined functions (that is functions defined by the programmer and used e.g. in the filter condition of a SQL query). While some databases also possess a "server-side" language (e.g. PL/SQL in Oracle database), its integration with the very-optimized query execution engine is still minimal and queries containing (PL/SQL) user-defined functions remain notoriously inefficient. In this setting, we reviewed existing language-integrated query frameworks, highlighting that existing database query languages (including SQL) share high-level querying primitives (e.g., filtering, joins, aggregation) that can be represented by operators, but differ widely regarding the semantics of their expression language. In order to represent queries in an application language- and database-agnostic manner, we designed a small calculus, dubbed "QIR" for Query Intermediate Representation. QIR contains expressions, corresponding to a small extension of the pure lambda-calculus, and operators to represent usual querying primitives. In the effort to send efficient queries to the database, we abstracted the idea of "good" query representations in a measure on QIR terms. Then, we designed an evaluation strategy rewriting QIR query representations into "better" ones.
Computational Complexity of Arranging Music
Venue: arXiv cs.CC 2016
Year: 2016

This paper proves that arrangement of music is NP-hard when subject to various constraints: avoiding musical dissonance, limiting how many notes can be played simultaneously, and limiting transition speed between chords. These results imply the computational complexity of related musical problems, including musical choreography and rhythm games.
Fifty Shades of Ratings: How to Benefit from a Negative Feedback in Top-N Recommendations Tasks
Venue: arXiv cs.LG 2016
Year: 2016

Conventional collaborative filtering techniques treat a top-n recommendations problem as a task of generating a list of the most relevant items. This formulation, however, disregards an opposite - avoiding recommendations with completely irrelevant items. Due to that bias, standard algorithms, as well as commonly used evaluation metrics, become insensitive to negative feedback. In order to resolve this problem we propose to treat user feedback as a categorical variable and model it with users and items in a ternary way. We employ a third-order tensor factorization technique and implement a higher order folding-in method to support online recommendations. The method is equally sensitive to entire spectrum of user ratings and is able to accurately predict relevant items even from a negative only feedback. Our method may partially eliminate the need for complicated rating elicitation process as it provides means for personalized recommendations from the very beginning of an interaction with a recommender system. We also propose a modification of standard metrics which helps to reveal unwanted biases and account for sensitivity to a negative feedback. Our model achieves state-of-the-art quality in standard recommendation tasks while significantly outperforming other methods in the cold-start "no-positive-feedback" scenarios.
A real-time analysis of rock fragmentation using UAV technology
Venue: arXiv cs.RO 2016
Year: 2016

Accurate measurement of blast-induced rock fragmentation is of great importance for many mining operations. The post-blast rock size distribution can significantly influence the efficiency of all the downstream mining and comminution processes. Image analysis methods are one of the most common methods used to measure rock fragment size distribution in mines regardless of criticism for lack of accuracy to measure fine particles and other perceived deficiencies. The current practice of collecting rock fragmentation data for image analysis is highly manual and provides data with low temporal and spatial resolution. Using UAVs for collecting images of rock fragments can not only improve the quality of the image data but also automate the data collection process. Ultimately, real-time acquisition of high temporal- and spatial-resolution data based on UAV technology will provide a broad range of opportunities for both improving blast design without interrupting the production process and reducing the cost of the human operator. This paper presents the results of a series of laboratory-scale rock fragment measurements using a quadrotor UAV equipped with a camera. The goal of this work is to highlight the benefits of aerial fragmentation analysis in terms of both prediction accuracy and time effort. A pile of rock fragments with different fragment sizes was placed in a lab that is equipped with a motion capture camera system for precise UAV localization and control. Such an environment presents optimal conditions for UAV flight and thus, is well-suited for conducting proof-of-concept experiments before testing them in large-scale field experiments. The pile was photographed by a camera attached to the UAV, and the particle size distribution curves were generated in almost real-time. The pile was also manually photographed and the results of the manual method were compared to the UAV method.
Defensive Distillation is Not Robust to Adversarial Examples
Venue: arXiv cs.CR 2016
Year: 2016

We show that defensive distillation is not secure: it is no more resistant to targeted misclassification attacks than unprotected neural networks.
Predicting the Popularity of GitHub Repositories
Venue: arXiv cs.SE 2016
Year: 2016

GitHub is the largest source code repository in the world. It provides a git-based source code management platform and also many features inspired by social networks. For example, GitHub users can show appreciation to projects by adding stars to them. Therefore, the number of stars of a repository is a direct measure of its popularity. In this paper, we use multiple linear regressions to predict the number of stars of GitHub repositories. These predictions are useful both to repository owners and clients, who usually want to know how their projects are performing in a competitive open source development market. In a large-scale analysis, we show that the proposed models start to provide accurate predictions after being trained with the number of stars received in the last six months. Furthermore, specific models---generated using data from repositories that share the same growth trends---are recommended for repositories with slow growth and/or for repositories with less stars. Finally, we evaluate the ability to predict not the number of stars of a repository but its rank among the GitHub repositories. We found a very strong correlation between predicted and real rankings (Spearman's rho greater than 0.95).
Modeling the Evolution of Line-of-Sight Blockage for V2V Channels
Venue: arXiv cs.NI 2016
Year: 2016

We investigate the evolution of line of sight (LOS) blockage over both time and space for vehicle-to-vehicle (V2V) channels. Using realistic vehicular mobility and building and foliage locations from maps, we first perform LOS blockage analysis to extract LOS probabilities in real cities and on highways for varying vehicular densities. Next, to model the time evolution of LOS blockage for V2V links, we employ a three-state discrete-time Markov chain comprised of the following states: i) LOS; ii) non-LOS due to static objects (e.g., buildings, trees, etc.); and iii) non-LOS due to mobile objects (vehicles). We obtain state transition probabilities based on the evolution of LOS blockage. Finally, we perform curve fitting and obtain a set of distance-dependent equations for both LOS and transition probabilities. These equations can be used to generate time-evolved V2V channel realizations for representative urban and highway environments. Our results can be used to perform highly efficient and accurate simulations without the need to employ complex geometry-based models for link evolution.