OpenRaiser/Intern-Atlas huggingface dataset:
Human-in-the-Loop Synthesis for Partially Observable Markov Decision Processes
Venue: arXiv cs.AI 2018
Year: 2018

We study planning problems where autonomous agents operate inside environments that are subject to uncertainties and not fully observable. Partially observable Markov decision processes (POMDPs) are a natural formal model to capture such problems. Because of the potentially huge or even infinite belief space in POMDPs, synthesis with safety guarantees is, in general, computationally intractable. We propose an approach that aims to circumvent this difficulty: in scenarios that can be partially or fully simulated in a virtual environment, we actively integrate a human user to control an agent. While the user repeatedly tries to safely guide the agent in the simulation, we collect data from the human input. Via behavior cloning, we translate the data into a strategy for the POMDP. The strategy resolves all nondeterminism and non-observability of the POMDP, resulting in a discrete-time Markov chain (MC). The efficient verification of this MC gives quantitative insights into the quality of the inferred human strategy by proving or disproving given system specifications. For the case that the quality of the strategy is not sufficient, we propose a refinement method using counterexamples presented to the human. Experiments show that by including humans into the POMDP verification loop we improve the state of the art by orders of magnitude in terms of scalability.
Elmo: Source-Routed Multicast for Cloud Services
Venue: arXiv cs.NI 2018
Year: 2018

We present Elmo, a system that addresses the multicast scalability problem in multi-tenant data centers. Modern cloud applications frequently exhibit one-to-many communication patterns and, at the same time, require sub-millisecond latencies and high throughput. IP multicast can achieve these requirements but has control- and data-plane scalability limitations that make it challenging to offer it as a service for hundreds of thousands of tenants, typical of cloud environments. Tenants, therefore, must rely on unicast-based approaches (e.g., application-layer or overlay-based) to support multicast in their applications, imposing overhead on throughput and end host CPU utilization, with higher and unpredictable latencies. Elmo scales network multicast by taking advantage of emerging programmable switches and the unique characteristics of data-center networks; specifically, the symmetric topology and short paths in a data center. Elmo encodes multicast group information inside packets themselves, reducing the need to store the same information in network switches. In a three-tier data-center topology with 27K hosts, Elmo supports a million multicast groups using a 325-byte packet header, requiring as few as 1.1K multicast group-table entries on average in leaf switches, with a traffic overhead as low as 5% over ideal multicast.
Constructing graphs with limited resources
Venue: arXiv cs.DM 2018
Year: 2018

We discuss the amount of physical resources required to construct a given graph, where vertices are added sequentially. We naturally identify information -- distinct into instructions and memory -- and randomness as resources. Not surprisingly, we show that, in this framework, threshold graphs are the simplest possible graphs, since the construction of threshold graphs requires a single bit of instructions for each vertex and no use of memory. Large instructions without memory do not bring any advantage. With one bit of instructions and one bit of memory for each vertex, we can construct a family of perfect graphs that strictly includes threshold graphs. We consider the case in which memory lasts for a single time step, and show that as well as the standard threshold graphs, linear forests are also producible. We show further that the number of random bits (with no memory or instructions) needed to construct any graph is asymptotically the same as required for the Erdős-Rényi random graph. We also briefly consider constructing trees in this scheme. The problem of defining a hierarchy of graphs in the proposed framework is fully open.
Linear codes with few weights over $\mathbb{F}_2+u\mathbb{F}_2$
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we construct an infinite family of five-weight codes from trace codes over the ring $R=\mathbb{F}_2+u\mathbb{F}_2$, where $u^2=0.$ The trace codes have the algebraic structure of abelian codes. Their Lee weight is computed by using character sums. Combined with Pless power moments and Newton's Identities, the weight distribution of the Gray image of trace codes was present. Their support structure is determined. An application to secret sharing schemes is given.
Formal Semantics of the Language Cypher
Venue: arXiv cs.DB 2018
Year: 2018

Cypher is a query language for property graphs. It was originally designed and implemented as part of the Neo4j graph database, and it is currently used in a growing number of commercial systems, industrial applications and research projects. In this work, we provide denotational semantics of the core fragment of the read-only part of Cypher, which features in particular pattern matching, filtering, and most relational operations on tables.
Improving OCR Accuracy on Early Printed Books using Deep Convolutional Networks
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes a combination of a convolutional and a LSTM network to improve the accuracy of OCR on early printed books. While the standard model of line based OCR uses a single LSTM layer, we utilize a CNN- and Pooling-Layer combination in advance of an LSTM layer. Due to the higher amount of trainable parameters the performance of the network relies on a high amount of training examples to unleash its power. Hereby, the error is reduced by a factor of up to 44%, yielding a CER of 1% and below. To further improve the results we use a voting mechanism to achieve character error rates (CER) below $0.5%$. The runtime of the deep model for training and prediction of a book behaves very similar to a shallow network.
Coding Theory using Linear Complexity of Finite Sequences
Venue: arXiv cs.IT 2018
Year: 2018

We define a metric on $\mathbb{F}_q^n$ using the linear complexity of finite sequences. We will then develop a coding theory for this metric. We will give a Singleton-like bound and we will give constructions of subspaces of $\mathbb{F}_q^n$ achieving this bound. We will compute the size of balls with respect to this metric. In other words we will count how many finite sequences have linear complexity bounded by some integer $r$. The paper is motivated in part by the desire to design new code based cryptographic systems.
On Coded Caching with Heterogeneous Distortion Requirements
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers heterogeneous coded caching where the users have unequal distortion requirements. The server is connected to the users via an error-free multicast link and designs the users' cache sizes subject to a total memory budget. In particular, in the placement phase, the server jointly designs the users' cache sizes and the cache contents. To serve the users' requests, in the delivery phase, the server transmits signals that satisfy the users' distortion requirements. An optimization problem with the objective of minimizing the worst-case delivery load subject to the total cache memory budget and users' distortion requirements is formulated. The optimal solution for uncoded placement and linear delivery is characterized explicitly and is shown to exhibit a threshold policy with respect to the total cache memory budget. As a byproduct of the study, a caching scheme for systems with fixed cache sizes that outperforms the state-of-art is presented.
Microsoft Malware Classification Challenge
Venue: arXiv cs.CR 2018
Year: 2018

The Microsoft Malware Classification Challenge was announced in 2015 along with a publication of a huge dataset of nearly 0.5 terabytes, consisting of disassembly and bytecode of more than 20K malware samples. Apart from serving in the Kaggle competition, the dataset has become a standard benchmark for research on modeling malware behaviour. To date, the dataset has been cited in more than 50 research papers. Here we provide a high-level comparison of the publications citing the dataset. The comparison simplifies finding potential research directions in this field and future performance evaluation of the dataset.
Exploiting the Natural Dynamics of Series Elastic Robots by Actuator-Centered Sequential Linear Programming
Venue: arXiv cs.RO 2018
Year: 2018

Series elastic robots are best able to follow trajectories which obey the limitations of their actuators, since they cannot instantly change their joint forces. In fact, the performance of series elastic actuators can surpass that of ideal force source actuators by storing and releasing energy. In this paper, we formulate the trajectory optimization problem for series elastic robots in a novel way based on sequential linear programming. Our framework is unique in the separation of the actuator dynamics from the rest of the dynamics, and in the use of a tunable pseudo-mass parameter that improves the discretization accuracy of our approach. The actuator dynamics are truly linear, which allows them to be excluded from trust-region mechanics. This causes our algorithm to have similar run times with and without the actuator dynamics. We demonstrate our optimization algorithm by tuning high performance behaviors for a single-leg robot in simulation and on hardware for a single degree-of-freedom actuator testbed. The results show that compliance allows for faster motions and takes a similar amount of computation time.
Fractional Programming for Communication Systems--Part I: Power Control and Beamforming
Venue: arXiv cs.IT 2018
Year: 2018

This two-part paper explores the use of FP in the design and optimization of communication systems. Part I of this paper focuses on FP theory and on solving continuous problems. The main theoretical contribution is a novel quadratic transform technique for tackling the multiple-ratio concave-convex FP problem--in contrast to conventional FP techniques that mostly can only deal with the single-ratio or the max-min-ratio case. Multiple-ratio FP problems are important for the optimization of communication networks, because system-level design often involves multiple signal-to-interference-plus-noise ratio terms. This paper considers the applications of FP to solving continuous problems in communication system design, particularly for power control, beamforming, and energy efficiency maximization. These application cases illustrate that the proposed quadratic transform can greatly facilitate the optimization involving ratios by recasting the original nonconvex problem as a sequence of convex problems. This FP-based problem reformulation gives rise to an efficient iterative optimization algorithm with provable convergence to a stationary point. The paper further demonstrates close connections between the proposed FP approach and other well-known algorithms in the literature, such as the fixed-point iteration and the weighted minimum mean-square-error beamforming. The optimization of discrete problems is discussed in Part II of this paper.
Local Distributed Algorithms in Highly Dynamic Networks
Venue: arXiv cs.DS 2018
Year: 2018

The present paper studies local distributed graph problems in highly dynamic networks. Communication and changes of the graph happen in synchronous rounds and our algorithms always, i.e., in every round, satisfy non-trivial guarantees, no matter how dynamic the network is. We define a (in our view) natural generalization of static graph problems to the dynamic graph setting. Throughout the execution of an algorithm we consider a sliding window over the last $T$, e.g., polylogarithmic, rounds. Then, in some round, the feasibility of an output only depends on the topology of the graphs in the current sliding window and we call a feasible output a $T$-dynamic solution. The guarantees of a $T$-dynamic solution become stronger the more stable the graph is during this sliding window and, in particular, they coincide with the definition of the static graph problem if the graph is static throughout the window. We further present an abstract framework that allows to develop algorithms that output $T$-dynamic solutions in all rounds. The resulting algorithms have another desirable property: If a constant neighborhood around some part of the graph is stable during an interval $[t_1,t_2]$, the algorithms compute a static solution for this part of the graph throughout the interval $[t_1+T',t_2]$ for some (small) $T'>0$. We demonstrate our generic framework with two sample problems that abstract basic operations in dynamic networks, namely $\textit{(degree+1)-vertex coloring}$ and $\textit{maximal independent set (MIS)}$. To illustrate the given guarantees consider the vertex coloring problem: The sliding window of our (randomized) algorithm is of length $T=O(\log n)$ and any conflict between two nodes caused by a newly inserted edge is resolved within that time. During this conflict resolving both nodes always output colors that are not in conflict with their respective 'old' neighbors.
Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources
Venue: arXiv cs.DB 2018
Year: 2018

Apache Calcite is a foundational software framework that provides query processing, optimization, and query language support to many popular open-source data processing systems such as Apache Hive, Apache Storm, Apache Flink, Druid, and MapD. Calcite's architecture consists of a modular and extensible query optimizer with hundreds of built-in optimization rules, a query processor capable of processing a variety of query languages, an adapter architecture designed for extensibility, and support for heterogeneous data models and stores (relational, semi-structured, streaming, and geospatial). This flexible, embeddable, and extensible architecture is what makes Calcite an attractive choice for adoption in big-data frameworks. It is an active project that continues to introduce support for the new types of data sources, query languages, and approaches to query processing and optimization.
IM2HEIGHT: Height Estimation from Single Monocular Imagery via Fully Residual Convolutional-Deconvolutional Network
Venue: arXiv cs.CV 2018
Year: 2018

In this paper we tackle a very novel problem, namely height estimation from a single monocular remote sensing image, which is inherently ambiguous, and a technically ill-posed problem, with a large source of uncertainty coming from the overall scale. We propose a fully convolutional-deconvolutional network architecture being trained end-to-end, encompassing residual learning, to model the ambiguous mapping between monocular remote sensing images and height maps. Specifically, it is composed of two parts, i.e., convolutional sub-network and deconvolutional sub-network. The former corresponds to feature extractor that transforms the input remote sensing image to high-level multidimensional feature representation, whereas the latter plays the role of a height generator that produces height map from the feature extracted from the convolutional sub-network. Moreover, to preserve fine edge details of estimated height maps, we introduce a skip connection to the network, which is able to shuttle low-level visual information, e.g., object boundaries and edges, directly across the network. To demonstrate the usefulness of single-view height prediction, we show a practical example of instance segmentation of buildings using estimated height map. This paper, for the first time in the remote sensing community, attempts to estimate height from monocular vision. The proposed network is validated using a large-scale high resolution aerial image data set covered an area of Berlin. Both visual and quantitative analysis of the experimental results demonstrate the effectiveness of our approach.
Semi-MapReduce Meets Congested Clique
Venue: arXiv cs.DC 2018
Year: 2018

Graph problems are troublesome when it comes to MapReduce. Typically, to be able to design algorithms that make use of the advantages of MapReduce, assumptions beyond what the model imposes, such as the density of the input graph, are required. In a recent shift, a simple and robust model of MapReduce for graph problems, where the space per machine is set to be O(|V|), has attracted considerable attention. We term this model semi-MapReduce, or in short, semiMPC, and focus on its computational power. We show through a set of simulation methods that semiMPC is, perhaps surprisingly, equivalent to the congested clique model of distributed computing. However, semiMPC, in addition to round complexity, incorporates another practically important dimension to optimize: the number of machines. Furthermore, we show that algorithms in other distributed computing models, such as CONGEST, can be simulated to run in the same number of rounds of semiMPC while also using an optimal number of machines. We later show the implications of these simulation methods by obtaining improved algorithms for these models using the recent algorithms that have been developed.
Efficient Black-Box Reductions for Separable Cost Sharing
Venue: arXiv cs.GT 2018
Year: 2018

In cost sharing games with delays, a set of agents jointly allocates a finite subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a nonshareable player-specific delay for each resource. A prominent example is uncapacitated facility location (UFL), where facilities need to be opened (at a shareable cost) and clients want to connect to opened facilities. Each client pays a cost share and his non-shareable physical connection cost. Given any profile of subsets allocated by the agents, a separable cost sharing protocol determines cost shares that satisfy budget balance on every resource and separability over the resources. Moreover, a separable protocol guarantees existence of pure Nash equilibria in the induced strategic game for the agents. In this paper, we study separable cost sharing protocols in several general combinatorial domains. We provide black-box reductions to reduce the design of a separable cost-sharing protocol to the design of an approximation algorithm for the underlying cost minimization problem. In this way, we obtain new separable cost-sharing protocols in games based on arbitrary player-specific matroids, single-source connection games without delays, and connection games on $n$-series-parallel graphs with delays. All these reductions are efficiently computable - given an initial allocation profile, we obtain a cheaper profile and separable cost shares turning the profile into a pure Nash equilibrium. Hence, in these domains any approximation algorithm can be used to obtain a separable cost sharing protocol with a price of stability bounded by the approximation factor.
Deep-6DPose: Recovering 6D Object Pose from a Single RGB Image
Venue: arXiv cs.CV 2018
Year: 2018

Detecting objects and their 6D poses from only RGB images is an important task for many robotic applications. While deep learning methods have made significant progress in visual object detection and segmentation, the object pose estimation task is still challenging. In this paper, we introduce an end-toend deep learning framework, named Deep-6DPose, that jointly detects, segments, and most importantly recovers 6D poses of object instances from a single RGB image. In particular, we extend the recent state-of-the-art instance segmentation network Mask R-CNN with a novel pose estimation branch to directly regress 6D object poses without any post-refinements. Our key technical contribution is the decoupling of pose parameters into translation and rotation so that the rotation can be regressed via a Lie algebra representation. The resulting pose regression loss is differential and unconstrained, making the training tractable. The experiments on two standard pose benchmarking datasets show that our proposed approach compares favorably with the state-of-the-art RGB-based multi-stage pose estimation methods. Importantly, due to the end-to-end architecture, Deep-6DPose is considerably faster than competing multi-stage methods, offers an inference speed of 10 fps that is well suited for robotic applications.
A Bayesian Model for Activities Recommendation and Event Structure Optimization Using Visitors Tracking
Venue: arXiv cs.NE 2018
Year: 2018

In events that are composed by many activities, there is a problem that involves retrieve and management the information of visitors that are visiting the activities. This management is crucial to find some activities that are drawing attention of visitors; identify an ideal positioning for activities; which path is more frequented by visitors. In this work, these features are studied using Complex Network theory. For the beginning, an artificial database was generated to study the mentioned features. Secondly, this work shows a method to optimize the event structure that is better than a random method and a recommendation system that achieves ~95% of accuracy.
Low-Overhead Coordination in Sub-28 Millimeter-Wave Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we present some contributions from our recent investigation. We address the open issue of interference coordination for sub-28 GHz millimeter-wave communication, by proposing fast-converging coordination algorithms, for dense multi-user multi-cell networks. We propose to optimize a lower bound on the network sum-rate, after investigating its tightness. The bound in question results in distributed optimization, requiring local information at each base station and user. We derive the optimal solution to the transmit and receive filter updates, that we dub non-homogeneous waterfilling, and show its convergence to a stationary point of the bound. We also underline a built-in mechanism to turn-off data streams with low-SINR, and allocate power to high-SNR streams. This "stream control" is a at the root of the fast-converging nature of the algorithm. Our numerical result conclude that low-overhead coordination offers large gains, for dense sub-$28$ GHz systems. These findings bear direct relevance to the ongoing discussions around 5G New Radio.
Resource-Aware Min-Min (RAMM) Algorithm for Resource Allocation in Cloud Computing Environment
Venue: arXiv cs.DC 2018
Year: 2018

Resource allocation (RA) is a significant aspect in Cloud Computing which facilitates the Cloud resources to Cloud consumers as a metered service. The Cloud resource manager is responsible to assign available resources to the tasks for execution in an effective way that improves system performance, reduce response time, reduce makespan and utilize resources efficiently. To fulfil these objectives, an effective Tasks Scheduling algorithm is required. The standard Min-Min and Max-Min Task Scheduling Algorithms are available, but these algorithms are not able to produce better makespan and effective resource utilization. This paper proposed a Resource-Aware Min-Min (RAMM) Algorithm based on classic Min-Min Algorithm. The RAMM Algorithm selects shortest execution time task and assign it to the resource which takes shortest completion time. If minimum completion time resource is busy then the RAMM Algorithm selects next minimum completion time resource to reduce waiting time of task and better resource utilization. The experiment results show that the RAMM Algorithm produces better makespan and load balance than standard Min-Min, Max-Min and improved Max-Min Algorithms.