OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Cross-Layer Beamforming in Hybrid Powered Communication Systems With Harvest-Use-Trade Strategy
Venue: arXiv cs.IT 2017
Year: 2017

The application of renewable energy is a promising solution to realize the Green Communications. However, if the cellular systems are solely powered by the renewable energy, the weather dependence of the renewable energy arrival makes the systems unstable. On the other hand, the proliferation of the smart grid facilitates the loads with two-way energy trading capability. Hence, a hybrid powered cellular system, which combines the smart grid with the base stations, can reduce the grid energy expenditure and improve the utilization efficiency of the renewable energy. In this paper, the long-term grid energy expenditure minimization problem is formulated as a stochastic optimization model. By leveraging the stochastic optimization theory, we reformulate the stochastic optimization problem as a \mbox{per-frame} grid energy plus weighted penalized packet rate minimization problem, which is NP-hard. As a result, two suboptimal algorithms, which jointly consider the effects of the channel quality and the packet reception failure, are proposed based on the successive approximation beamforming (SABF) technique and the \mbox{zero-forcing} beamforming (ZFBF) technique. The convergence properties of the proposed suboptimal algorithms are established, and the corresponding computational complexities are analyzed. Simulation results show that the proposed SABF algorithm outperforms the ZFBF algorithm in both grid energy expenditure and packet delay. By tuning a control parameter, the grid energy expenditure can be traded for the packet delay under the proposed stochastic optimization model.
Construction C*: an inter-level coded version of Construction C
Venue: arXiv cs.IT 2017
Year: 2017

Besides all the attention given to lattice constructions, it is common to find some very interesting nonlattice constellations, as Construction C, for example, which also has relevant applications in communication problems (multi-level coding, multi-stage decoding, good quantization efficieny). In this work we present a constellation which is a subset of Construction C, based on inter-level coding, which we call Construction C*. This construction may have better immunity to noise and it also provides a simple way of describing the Leech lattice $Λ_{24}.$ A condition under which Construction C* is a lattice constellation is given.
On Graphs and the Gotsman-Linial Conjecture for d = 2
Venue: arXiv cs.DM 2017
Year: 2017

We give an infinite class of counterexamples to the Gotsman-Linial conjecture when d = 2. On the other hand, we establish an asymptotic form of the conjecture for quadratic threshold functions whose non-zero quadratic terms define a graph with either low fractional chromatic number or few edges. Our techniques are elementary and our exposition is self-contained, if you're into that.
Simulation-based reachability analysis for nonlinear systems using componentwise contraction properties
Venue: arXiv cs.SY 2017
Year: 2017

A shortcoming of existing reachability approaches for nonlinear systems is the poor scalability with the number of continuous state variables. To mitigate this problem we present a simulation-based approach where we first sample a number of trajectories of the system and next establish bounds on the convergence or divergence between the samples and neighboring trajectories. We compute these bounds using contraction theory and reduce the conservatism by partitioning the state vector into several components and analyzing contraction properties separately in each direction. Among other benefits this allows us to analyze the effect of constant but uncertain parameters by treating them as state variables and partitioning them into a separate direction. We next present a numerical procedure to search for weighted norms that yield a prescribed contraction rate, which can be incorporated in the reachability algorithm to adjust the weights to minimize the growth of the reachable set.
A new adaptive method for hiding data in images
Venue: arXiv cs.MM 2017
Year: 2017

LSB method is one of the well-known steganography methods which hides the message bits into the least significant bit of pixel values. This method changes the statistical information of images, which causes to have an unsecured channel. To increase the security of this method against the steganalysis methods, in this paper an adaptive method for hiding data into images will be proposed. So, the amount of data and the method which is used for hiding data in each area of image will be different. Experimental results show that the security of the proposed method is higher than general LSB method and in some cases the capacity of the carrier signal is increased.
Discovery of the Twitter Bursty Botnet
Venue: arXiv cs.SI 2017
Year: 2017

Many Twitter users are bots. They can be used for spamming, opinion manipulation and online fraud. Recently we discovered the Star Wars botnet, consisting of more than 350,000 bots tweeting random quotations exclusively from Star Wars novels. The bots were exposed because they tweeted uniformly from any location within two rectangle-shaped geographic zones covering Europe and the USA, including sea and desert areas in the zones. In this paper, we report another unusual behaviour of the Star Wars bots, that the bots were created in bursts or batches, and they only tweeted in their first few minutes since creation. Inspired by this observation, we discovered an even larger Twitter botnet, the Bursty botnet with more than 500,000 bots. Our preliminary study showed that the Bursty botnet was directly responsible for a large-scale online spamming attack in 2012. Most bot detection algorithms have been based on assumptions of `common' features that were supposedly shared by all bots. Our discovered botnets, however, do not show many of those features; instead, they were detected by their distinct, unusual tweeting behaviours that were unknown until now.
Complexity of Finding Perfect Bipartite Matchings Minimizing the Number of Intersecting Edges
Venue: arXiv cs.CC 2017
Year: 2017

Consider a problem where we are given a bipartite graph H with vertices arranged on two horizontal lines in the plane, such that the two sets of vertices placed on the two lines form a bipartition of H. We additionally require that H admits a perfect matching and assume that edges of H are embedded in the plane as segments. The goal is to compute the minimal number of intersecting edges in a perfect matching in H. The problem stems from so-called token swapping problems, introduced by Yamanaka et al. [3] and generalized by Bonnet, Miltzow and Rzazewski [1]. We show that our problem, equivalent to one of the special cases of one of the token swapping problems, is NP-complete.
Efficient Graph Edit Distance Computation and Verification via Anchor-aware Lower Bound Estimation
Venue: arXiv cs.DB 2017
Year: 2017

Graph edit distance (GED) is an important similarity measure adopted in a similarity-based analysis between two graphs, and computing GED is a primitive operator in graph database analysis. Partially due to the NP-hardness, the existing techniques for computing GED are only able to process very small graphs with less than 30 vertices. Motivated by this, in this paper we systematically study the problems of both GED computation, and GED verification (i.e., verify whether the GED between two graphs is no larger than a user-given threshold). Firstly, we develop a unified framework that can be instantiated into either a best-first search approach AStar+ or a depth-first search approach DFS+. Secondly, we design anchor-aware lower bound estimation techniques to compute tighter lower bounds for intermediate search states, which significantly reduce the search spaces of both AStar+ and DFS+. We also propose efficient techniques to compute the lower bounds. Thirdly, based on our unified framework, we contrast AStar+ with DFS+ regarding their time and space complexities, and recommend that AStar+ is better than DFS+ by having a much smaller search space. Extensive empirical studies validate that AStar+ performs better than DFS+, and show that our AStar+-BMa approach outperforms the state-of-the-art technique by more than four orders of magnitude.
Affordable and Energy-Efficient Cloud Computing Clusters: The Bolzano Raspberry Pi Cloud Cluster Experiment
Venue: arXiv cs.DC 2017
Year: 2017

We present our ongoing work building a Raspberry Pi cluster consisting of 300 nodes. The unique characteristics of this single board computer pose several challenges, but also offer a number of interesting opportunities. On the one hand, a single Raspberry Pi can be purchased cheaply and has a low power consumption, which makes it possible to create an affordable and energy-efficient cluster. On the other hand, it lacks in computing power, which makes it difficult to run computationally intensive software on it. Nevertheless, by combining a large number of Raspberries into a cluster, this drawback can be (partially) offset. Here we report on the first important steps of creating our cluster: how to set up and configure the hardware and the system software, and how to monitor and maintain the system. We also discuss potential use cases for our cluster, the two most important being an inexpensive and green test bed for cloud computing research and a robust and mobile data center for operating in adverse environments.
Distributed Lance-William Clustering Algorithm
Venue: arXiv cs.DC 2017
Year: 2017

One important tool is the optimal clustering of data into useful categories. Dividing similar objects into a smaller number of clusters is of importance in many applications. These include search engines, monitoring of academic performance, biology and wireless networks. We first discuss a number of clustering methods. We present a parallel algorithm for the efficient clustering of objects into groups based on their similarity to each other. The input consists of an n by n distance matrix. This matrix would have a distance ranking for each pair of objects. The smaller the number, the more similar the two objects are to each other. We utilize parallel processors to calculate a hierarchal cluster of these n items based on this matrix. Another advantage of our method is distribution of the large n by n matrix. We have implemented our algorithm and have found it to be scalable both in terms of processing speed and storage.
Miscorrection-free Decoding of Staircase Codes
Venue: arXiv cs.IT 2017
Year: 2017

We propose a novel decoding algorithm for staircase codes which reduces the effect of undetected component code miscorrections. The algorithm significantly improves performance, while retaining a low-complexity implementation suitable for high-speed optical transport networks.
Open Source Dataset and Deep Learning Models for Online Digit Gesture Recognition on Touchscreens
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents an evaluation of deep neural networks for recognition of digits entered by users on a smartphone touchscreen. A new large dataset of Arabic numerals was collected for training and evaluation of the network. The dataset consists of spatial and temporal touch data recorded for 80 digits entered by 260 users. Two neural network models were investigated. The first model was a 2D convolutional neural (ConvNet) network applied to bitmaps of the glpyhs created by interpolation of the sensed screen touches and its topology is similar to that of previously published models for offline handwriting recognition from scanned images. The second model used a 1D ConvNet architecture but was applied to the sequence of polar vectors connecting the touch points. The models were found to provide accuracies of 98.50% and 95.86%, respectively. The second model was much simpler, providing a reduction in the number of parameters from 1,663,370 to 287,690. The dataset has been made available to the community as an open source resource.
Opposition based Ensemble Micro Differential Evolution
Venue: arXiv cs.NE 2017
Year: 2017

Differential evolution (DE) algorithm with a small population size is called Micro-DE (MDE). A small population size decreases the computational complexity but also reduces the exploration ability of DE by limiting the population diversity. In this paper, we propose the idea of combining ensemble mutation scheme selection and opposition-based learning concepts to enhance the diversity of population in MDE at mutation and selection stages. The proposed algorithm enhances the diversity of population by generating a random mutation scale factor per individual and per dimension, randomly assigning a mutation scheme to each individual in each generation, and diversifying individuals selection using opposition-based learning. This approach is easy to implement and does not require the setting of mutation scheme selection and mutation scale factor. Experimental results are conducted for a variety of objective functions with low and high dimensionality on the CEC Black- Box Optimization Benchmarking 2015 (CEC-BBOB 2015). The results show superior performance of the proposed algorithm compared to the other micro-DE algorithms.
Deep Reinforcement Learning for Dexterous Manipulation with Concept Networks
Venue: arXiv cs.AI 2017
Year: 2017

Deep reinforcement learning yields great results for a large array of problems, but models are generally retrained anew for each new problem to be solved. Prior learning and knowledge are difficult to incorporate when training new models, requiring increasingly longer training as problems become more complex. This is especially problematic for problems with sparse rewards. We provide a solution to these problems by introducing Concept Network Reinforcement Learning (CNRL), a framework which allows us to decompose problems using a multi-level hierarchy. Concepts in a concept network are reusable, and flexible enough to encapsulate feature extractors, skills, or other concept networks. With this hierarchical learning approach, deep reinforcement learning can be used to solve complex tasks in a modular way, through problem decomposition. We demonstrate the strength of CNRL by training a model to grasp a rectangular prism and precisely stack it on top of a cube using a gripper on a Kinova JACO arm, simulated in MuJoCo. Our experiments show that our use of hierarchy results in a 45x reduction in environment interactions compared to the state-of-the-art on this task.
Data-Driven Model Predictive Control of Autonomous Mobility-on-Demand Systems
Venue: arXiv cs.RO 2017
Year: 2017

The goal of this paper is to present an end-to-end, data-driven framework to control Autonomous Mobility-on-Demand systems (AMoD, i.e. fleets of self-driving vehicles). We first model the AMoD system using a time-expanded network, and present a formulation that computes the optimal rebalancing strategy (i.e., preemptive repositioning) and the minimum feasible fleet size for a given travel demand. Then, we adapt this formulation to devise a Model Predictive Control (MPC) algorithm that leverages short-term demand forecasts based on historical data to compute rebalancing strategies. We test the end-to-end performance of this controller with a state-of-the-art LSTM neural network to predict customer demand and real customer data from DiDi Chuxing: we show that this approach scales very well for large systems (indeed, the computational complexity of the MPC algorithm does not depend on the number of customers and of vehicles in the system) and outperforms state-of-the-art rebalancing strategies by reducing the mean customer wait time by up to to 89.6%.
Distributed Camouflage for Swarm Robotics and Smart Materials
Venue: arXiv cs.RO 2017
Year: 2017

We present a distributed algorithm for a swarm of active particles to camouflage in an environment. Each particle is equipped with sensing, computation and communication, allowing the system to take color and gradient information from the environment and self-organize into an appropriate pattern. Current artificial camouflage systems are either limited to static patterns, which are adapted for specific environments, or rely on back-projection, which depend on the viewer's point of view. Inspired by the camouflage abilities of the cuttlefish, we propose a distributed estimation and pattern formation algorithm that allows to quickly adapt to different environments. We present convergence results both in simulation as well as on a swarm of miniature robots "Droplets" for a variety of patterns.
On the Design of LQR Kernels for Efficient Controller Learning
Venue: arXiv cs.SY 2017
Year: 2017

Finding optimal feedback controllers for nonlinear dynamic systems from data is hard. Recently, Bayesian optimization (BO) has been proposed as a powerful framework for direct controller tuning from experimental trials. For selecting the next query point and finding the global optimum, BO relies on a probabilistic description of the latent objective function, typically a Gaussian process (GP). As is shown herein, GPs with a common kernel choice can, however, lead to poor learning outcomes on standard quadratic control problems. For a first-order system, we construct two kernels that specifically leverage the structure of the well-known Linear Quadratic Regulator (LQR), yet retain the flexibility of Bayesian nonparametric learning. Simulations of uncertain linear and nonlinear systems demonstrate that the LQR kernels yield superior learning performance.
Decomposing GR(1) Games with Singleton Liveness Guarantees for Efficient Synthesis
Venue: arXiv cs.LO 2017
Year: 2017

Temporal logic based synthesis approaches are often used to find trajectories that are correct-by-construction for tasks in systems with complex behavior. Some examples of such tasks include synchronization for multi-agent hybrid systems, reactive motion planning for robots. However, the scalability of such approaches is of concern and at times a bottleneck when transitioning from theory to practice. In this paper, we identify a class of problems in the GR(1) fragment of linear-time temporal logic (LTL) where the synthesis problem allows for a decomposition that enables easy parallelization. This decomposition also reduces the alternation depth, resulting in more efficient synthesis. A multi-agent robot gridworld example with coordination tasks is presented to demonstrate the application of the developed ideas and also to perform empirical analysis for benchmarking the decomposition-based synthesis approach.
FairFuzz: Targeting Rare Branches to Rapidly Increase Greybox Fuzz Testing Coverage
Venue: arXiv cs.SE 2017
Year: 2017

In recent years, fuzz testing has proven itself to be one of the most effective techniques for finding correctness bugs and security vulnerabilities in practice. One particular fuzz testing tool, American Fuzzy Lop or AFL, has become popular thanks to its ease-of-use and bug-finding power. However, AFL remains limited in the depth of program coverage it achieves, in particular because it does not consider which parts of program inputs should not be mutated in order to maintain deep program coverage. We propose an approach, FairFuzz, that helps alleviate this limitation in two key steps. First, FairFuzz automatically prioritizes inputs exercising rare parts of the program under test. Second, it automatically adjusts the mutation of inputs so that the mutated inputs are more likely to exercise these same rare parts of the program. We conduct evaluation on real-world programs against state-of-the-art versions of AFL, thoroughly repeating experiments to get good measures of variability. We find that on certain benchmarks FairFuzz shows significant coverage increases after 24 hours compared to state-of-the-art versions of AFL, while on others it achieves high program coverage at a significantly faster rate.
Visual Question Generation as Dual Task of Visual Question Answering
Venue: arXiv cs.CV 2017
Year: 2017

Recently visual question answering (VQA) and visual question generation (VQG) are two trending topics in the computer vision, which have been explored separately. In this work, we propose an end-to-end unified framework, the Invertible Question Answering Network (iQAN), to leverage the complementary relations between questions and answers in images by jointly training the model on VQA and VQG tasks. Corresponding parameter sharing scheme and regular terms are proposed as constraints to explicitly leverage Q,A's dependencies to guide the training process. After training, iQAN can take either question or answer as input, then output the counterpart. Evaluated on the large-scale visual question answering datasets CLEVR and VQA2, our iQAN improves the VQA accuracy over the baselines. We also show the dual learning framework of iQAN can be generalized to other VQA architectures and consistently improve the results over both the VQA and VQG tasks.
Satisfiability Modulo Theory based Methodology for Floorplanning in VLSI Circuits
Venue: arXiv cs.AR 2017
Year: 2017

This paper proposes a Satisfiability Modulo Theory based formulation for floorplanning in VLSI circuits. The proposed approach allows a number of fixed blocks to be placed within a layout region without overlapping and at the same time minimizing the area of the layout region. The proposed approach is extended to allow a number of fixed blocks with ability to rotate and flexible blocks (with variable width and height) to be placed within a layout without overlap. Our target in all cases is reduction in area occupied on a chip which is of vital importance in obtaining a good circuit design. Satisfiability Modulo Theory combines the problem of Boolean satisfiability with domains such as convex optimization. Satisfiability Modulo Theory provides a richer modeling language than is possible with pure Boolean SAT formulas. We have conducted our experiments on MCNC and GSRC benchmark circuits to calculate the total area occupied, amount of deadspace and the total CPU time consumed while placing the blocks without overlapping. The results obtained shows clearly that the amount of dead space or wasted space is reduced if rotation is applied to the blocks.
A Communication-Efficient Distributed Data Structure for Top-k and k-Select Queries
Venue: arXiv cs.DS 2017
Year: 2017

We consider the scenario of $n$ sensor nodes observing streams of data. The nodes are connected to a central server whose task it is to compute some function over all data items observed by the nodes. In our case, there exists a total order on the data items observed by the nodes. Our goal is to compute the $k$ currently lowest observed values or a value with rank in $[(1-\varepsilon)k,(1+\varepsilon)k]$ with probability $(1-δ)$. We propose solutions for these problems in an extension of the distributed monitoring model where the server can send broadcast messages to all nodes for unit cost. We want to minimize communication over multiple time steps where there are $m$ updates to a node's value in between queries. The result is composed of two main parts, which each may be of independent interest: (1) Protocols which answer Top-k and k-Select queries. These protocols are memoryless in the sense that they gather all information at the time of the request. (2) A dynamic data structure which tracks for every $k$ an element close to $k$. We describe how to combine the two parts to receive a protocol answering the stated queries over multiple time steps. Overall, for Top-$k$ queries we use $O(k + \log m + \log \log n)$ and for $k$-Select queries $O(\frac{1}{\varepsilon^2} \log \frac{1}δ + \log m + \log^2 \log n)$ messages in expectation. These results are shown to be asymptotically tight if $m$ is not too small.