OpenRaiser/Intern-Atlas huggingface dataset:
On the Packing Chromatic Number on Hamming Graphs and General Graphs
Venue: arXiv cs.DM 2015
Year: 2015

The packing chromatic number $χ_ρ(G)$ of a graph $G$ is the smallest integer $k$ needed to proper color the vertices of $G$ in such a way the distance between any two vertices having color $i$ be at least $i+1$. We obtain $χ_ρ(H_{q,m})$ for $m=3$, where $H_{q,m}$ is the Hamming graph of words of length $m$ and alphabet with $q$ symbols, and tabulate bounds of them for $m \geq 4$ up to 10000 vertices. We also give a polynomial reduction from the problem of finding $χ_ρ(G)$ to the Maximum Stable Set problem.
Sparse + Low Rank Decomposition of Annihilating Filter-based Hankel Matrix for Impulse Noise Removal
Venue: arXiv cs.CV 2015
Year: 2015

Recently, so called annihilating filer-based low rank Hankel matrix (ALOHA) approach was proposed as a powerful image inpainting method. Based on the observation that smoothness or textures within an image patch corresponds to sparse spectral components in the frequency domain, ALOHA exploits the existence of annihilating filters and the associated rank-deficient Hankel matrices in the image domain to estimate the missing pixels. By extending this idea, here we propose a novel impulse noise removal algorithm using sparse + low rank decomposition of an annihilating filter-based Hankel matrix. The new approach, what we call the robust ALOHA, is motivated by the observation that an image corrupted with impulse noises has intact pixels; so the impulse noises can be modeled as sparse components, whereas the underlying image can be still modeled using a low-rank Hankel structured matrix. To solve the sparse + low rank decomposition problem, we propose an alternating direction method of multiplier (ADMM) method with initial factorized matrices coming from low rank matrix fitting (LMaFit) algorithm. To adapt the local image statistics that have distinct spectral distributions, the robust ALOHA is applied patch by patch. Experimental results from two types of impulse noises - random valued impulse noises and salt/pepper noises - for both single channel and multi-channel color images demonstrate that the robust ALOHA outperforms the existing algorithms up to 8dB in terms of the peak signal to noise ratio (PSNR).
Server Placement with Shared Backups for Disaster-Resilient Clouds
Venue: arXiv cs.NI 2015
Year: 2015

A key strategy to build disaster-resilient clouds is to employ backups of virtual machines in a geo-distributed infrastructure. Today, the continuous and acknowledged replication of virtual machines in different servers is a service provided by different hypervisors. This strategy guarantees that the virtual machines will have no loss of disk and memory content if a disaster occurs, at a cost of strict bandwidth and latency requirements. Considering this kind of service, in this work, we propose an optimization problem to place servers in a wide area network. The goal is to guarantee that backup machines do not fail at the same time as their primary counterparts. In addition, by using virtualization, we also aim to reduce the amount of backup servers required. The optimal results, achieved in real topologies, reduce the number of backup servers by at least 40%. Moreover, this work highlights several characteristics of the backup service according to the employed network, such as the fulfillment of latency requirements.
Protein Structure Prediction by Protein Alignments
Venue: arXiv cs.CE 2015
Year: 2015

Proteins are the basic building blocks of life. They usually perform functions by folding to a particular structure. Understanding the folding process could help the researchers to understand the functions of proteins and could also help to develop supplemental proteins for people with deficiencies and gain more insight into diseases associated with troublesome folding proteins. Experimental methods are both expensive and time consuming. In this thesis I introduce a new machine learning based method to predict the protein structure. The new method improves the performance from two directions: creating accurate protein alignments and predicting accurate protein contacts. First, I present an alignment framework MRFalign which goes beyond state-of-the-art methods and uses Markov Random Fields to model a protein family and align two proteins by aligning two MRFs together. Compared to other methods, that can only model local-range residue correlation, MRFs can model long-range residue interactions and thus, encodes global information in a protein. Secondly, I present a Group Graphical Lasso method for contact prediction that integrates joint multi-family Evolutionary Coupling analysis and supervised learning to improve accuracy on proteins without many sequence homologs. Different from single-family EC analysis that uses residue co-evolution information in only the target protein family, our joint EC analysis uses residue co-evolution in both the target family and its related families, which may have divergent sequences but similar folds. Our method can also integrate supervised learning methods to further improve accuracy. We evaluate the performance of both methods including each of its components on large public benchmarks. Experiments show that our methods can achieve better accuracy than existing state-of-the-art methods under all the measurements on most of the protein classes.
Joint Deployment of Small Cells and Wireless Backhaul Links in Next-Generation Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a novel approach for optimizing the joint deployment of small cell base stations and wireless backhaul links is proposed. This joint deployment scenario is cast as a multi-objective optimization problem under the constraints of limited backhaul capacity and outage probability. To address the problem,a novel adaptive algorithm that integrates $ε$-method, Lagrangian relaxation and tabu search is proposed to obtain the Pareto optimal solution set. Simulation results show that the proposed algorithm is quite effective in finding the optimal solutions. The proposed joint deployment model can be used for planning small cell networks.
Distributed Surrounding Design of Target Region with Complex Adjacency Matrices
Venue: arXiv cs.SY 2015
Year: 2015

This is a complete version of the 6-page IEEE TAC technical note [1]. In this paper, we consider the distributed surrounding of a convex target set by a group of agents with switching communication graphs. We propose a distributed controller to surround a given set with the same distance and desired projection angles specified by a complex-value adjacency matrix. Under mild connectivity assumptions, we give results in both consistent and inconsistent cases for the set surrounding in a plane. Also, we provide sufficient conditions for the multi-agent coordination when the convex set contains only the origin.
A Blind-Mixing Scheme for Bitcoin based on an Elliptic Curve Cryptography Blind Digital Signature Algorithm
Venue: arXiv cs.CR 2015
Year: 2015

To strengthen the anonymity of Bitcoin, several centralized coin-mixing providers (mixers) such as BitcoinFog.com, BitLaundry.com, and Blockchain.info assist users to mix Bitcoins through CoinJoin transactions with multiple inputs and multiple outputs to uncover the relationship between them. However, these mixers know the output address of each user, such that they cannot provide true anonymity. This paper proposes a centralized coin-mixing algorithm based on an elliptic curve blind signature scheme (denoted as Blind-Mixing) that obstructs mixers from linking an input address with an output address. Comparisons among three blind signature based algorithms, Blind-Mixing, BlindCoin, and RSA Coin-Mixing, are conducted. It is determined that BlindCoin may be deanonymized because of its use of a public log. In RSA Coin-Mixing, a user's Bitcoins may be falsely claimed by another. In addition, the blind signature scheme of Blind-Mixing executes 10.5 times faster than that of RSA Coin-Mixing.
When is a network epidemic hard to eliminate?
Venue: arXiv cs.SI 2015
Year: 2015

We consider the propagation of a contagion process (epidemic) on a network and study the problem of dynamically allocating a fixed curing budget to the nodes of the graph, at each time instant. For bounded degree graphs, we provide a lower bound on the expected time to extinction under any such dynamic allocation policy, in terms of a combinatorial quantity that we call the resistance of the set of initially infected nodes, the available budget, and the number of nodes n. Specifically, we consider the case of bounded degree graphs, with the resistance growing linearly in n. We show that if the curing budget is less than a certain multiple of the resistance, then the expected time to extinction grows exponentially with n. As a corollary, if all nodes are initially infected and the CutWidth of the graph grows linearly, while the curing budget is less than a certain multiple of the CutWidth, then the expected time to extinction grows exponentially in n. The combination of the latter with our prior work establishes a fairly sharp phase transition on the expected time to extinction (sub-linear versus exponential) based on the relation between the CutWidth and the curing budget.
Data retrieval time for energy harvesting wireless sensor networks
Venue: arXiv cs.SY 2015
Year: 2015

We consider the problem of retrieving a reliable estimate of an attribute monitored by a wireless sensor network, where the sensors harvest energy from the environment independently, at random. Each sensor stores the harvested energy in batteries of limited capacity. Moreover, provided they have sufficient energy, the sensors broadcast their measurements in a decentralized fashion. Clients arrive at the sensor network according to a Poisson process and are interested in retrieving a fixed number of sensor measurements, based on which a reliable estimate is computed. We show that the time until an arbitrary sensor broadcasts has a phase-type distribution. Based on this result and the theory of order statistics of phase-type distributions, we determine the probability distribution of the time needed for a client to retrieve a reliable estimate of an attribute monitored by the sensor network. We also provide closed-form expression for the retrieval time of a reliable estimate when the capacity of the sensor battery or the rate at which energy is harvested is asymptotically large. In addition, we analyze numerically the retrieval time of a reliable estimate for various sizes of the sensor network, maximum capacity of the sensor batteries and rate at which energy is harvested. These results show that the energy harvesting rate and the broadcasting rate are the main parameters that influence the retrieval time of a reliable estimate, while deploying sensors with large batteries does not significantly reduce the retrieval time.
Massive MIMO and Millimeter Wave for 5G Wireless HetNet: Potentials and Challenges
Venue: arXiv cs.IT 2015
Year: 2015

There have been active research activities worldwide in developing the next-generation 5G wireless network. The 5G network is expected to support significantly large amount of mobile data traffic and huge number of wireless connections, achieve better cost- and energy-efficiency as well as quality of service (QoS) in terms of communication delay, reliability and security. To this end, the 5G wireless network should exploit potential gains in different network dimensions including super dense and heterogeneous deployment of cells and massive antenna arrays (i.e., massive multiple input multiple output (MIMO) technologies) and utilization of higher frequencies, in particular millimeter wave (mmWave) frequencies. This article discusses potentials and challenges of the 5G heterogeneous wireless network (HetNet) which incorporates massive MIMO and mmWave technologies. We will first provide the typical requirements of the 5G wireless network. Then, the significance of massive MIMO and mmWave in engineering the future 5G HetNet is discussed in detail. Potential challenges associated with the design of such 5G HetNet are discussed. Finally, we provide some case studies, which illustrate the potential benefits of the considered technologies.
Generalized Shortest Path Kernel on Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We consider the problem of classifying graphs using graph kernels. We define a new graph kernel, called the generalized shortest path kernel, based on the number and length of shortest paths between nodes. For our example classification problem, we consider the task of classifying random graphs from two well-known families, by the number of clusters they contain. We verify empirically that the generalized shortest path kernel outperforms the original shortest path kernel on a number of datasets. We give a theoretical analysis for explaining our experimental results. In particular, we estimate distributions of the expected feature vectors for the shortest path kernel and the generalized shortest path kernel, and we show some evidence explaining why our graph kernel outperforms the shortest path kernel for our graph classification problem.
Coordinating Truck Platooning by Clustering Pairwise Fuel-Optimal Plans
Venue: arXiv cs.SY 2015
Year: 2015

We consider the fuel-optimal coordination of trucks into platoons. Truck platooning is a promising technology that enables trucks to save significant amounts of fuel by driving close together and thus reducing air drag. We study how fuel-optimal speed profiles for platooning can be computed. A first-order fuel model is considered and pairwise optimal plans are derived. We formulate an optimization problem that combines these pairwise plans into an overall plan for a large number of trucks. The problem resembles a medoids clustering problem. We propose an approximation algorithm similar to the partitioning around medoids algorithm and discuss its convergence. The method is evaluated with Monte Carlo simulations. We demonstrate that the proposed algorithm can compute a plan for thousands of trucks and that significant fuel savings can be achieved.
Generalized conditional gradient: analysis of convergence and applications
Venue: arXiv cs.LG 2015
Year: 2015

The objectives of this technical report is to provide additional results on the generalized conditional gradient methods introduced by Bredies et al. [BLM05]. Indeed , when the objective function is smooth, we provide a novel certificate of optimality and we show that the algorithm has a linear convergence rate. Applications of this algorithm are also discussed.
Fuel-Optimal Centralized Coordination of Truck Platooning Based on Shortest Paths
Venue: arXiv cs.SY 2015
Year: 2015

Platooning is a way to significantly reduce fuel consumption of trucks. Vehicles that drive at close inter-vehicle distance assisted by automatic controllers experience substantially lower air-drag. In this paper, we deal with the problem of coordinating the formation and the breakup of platoons in a fuel-optimal way. We formulate an optimization problem which accounts for routing, speed-dependent fuel consumption, and platooning decisions. An algorithm to obtain an approximate solution to the problem is presented. It first determines the shortest path for each truck. Then, possible platoon configurations are identified. For a certain platoon configuration the optimal speed profile is the solution to a convex program. The algorithm is illustrated by a realistic example.
Content-Aware Delivery of Scalable Video in Network Coding Enabled Named Data Networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose a novel network coding enabled NDN architecture for the delivery of scalable video. Our scheme utilizes network coding in order to address the problem that arises in the original NDN protocol, where optimal use of the bandwidth and caching resources necessitates the coordination of the forwarding decisions. To optimize the performance of the proposed network coding based NDN protocol and render it appropriate for transmission of scalable video, we devise a novel rate allocation algorithm that decides on the optimal rates of Interest messages sent by clients and intermediate nodes. This algorithm guarantees that the achieved flow of Data objects will maximize the average quality of the video delivered to the client population. To support the handling of Interest messages and Data objects when intermediate nodes perform network coding, we modify the standard NDN protocol and introduce the use of Bloom filters, which store efficiently additional information about the Interest messages and Data objects. The proposed architecture is evaluated for transmission of scalable video over PlanetLab topologies. The evaluation shows that the proposed scheme performs very close to the optimal performance.
ZNN - A Fast and Scalable Algorithm for Training 3D Convolutional Networks on Multi-Core and Many-Core Shared Memory Machines
Venue: arXiv cs.NE 2015
Year: 2015

Convolutional networks (ConvNets) have become a popular approach to computer vision. It is important to accelerate ConvNet training, which is computationally costly. We propose a novel parallel algorithm based on decomposition into a set of tasks, most of which are convolutions or FFTs. Applying Brent's theorem to the task dependency graph implies that linear speedup with the number of processors is attainable within the PRAM model of parallel computation, for wide network architectures. To attain such performance on real shared-memory machines, our algorithm computes convolutions converging on the same node of the network with temporal locality to reduce cache misses, and sums the convergent convolution outputs via an almost wait-free concurrent method to reduce time spent in critical sections. We implement the algorithm with a publicly available software package called ZNN. Benchmarking with multi-core CPUs shows that ZNN can attain speedup roughly equal to the number of physical cores. We also show that ZNN can attain over 90x speedup on a many-core CPU (Xeon Phi Knights Corner). These speedups are achieved for network architectures with widths that are in common use. The task parallelism of the ZNN algorithm is suited to CPUs, while the SIMD parallelism of previous algorithms is compatible with GPUs. Through examples, we show that ZNN can be either faster or slower than certain GPU implementations depending on specifics of the network architecture, kernel sizes, and density and size of the output patch. ZNN may be less costly to develop and maintain, due to the relative ease of general-purpose CPU programming.
Prominent but Less Productive: The Impact of Interdisciplinarity on Scientists' Research
Venue: arXiv cs.DL 2015
Year: 2015

Inter-disciplinary research (IDR) is being promoted by federal agencies and universities nationwide because it presumably spurs transformative, innovative science. In this paper we bring empirical data to assess whether IDR is indeed beneficial, and whether costs accompany potential benefits.
Multi-user Cognitive Interference Channels: A Survey and New Capacity Results
Venue: arXiv cs.IT 2015
Year: 2015

This paper provides a survey of the state-of-the-art information theoretic analysis for overlay multi-user (more than two pairs) cognitive networks and reports new capacity results. In an overlay scenario, cognitive / secondary users share the same frequency band with licensed / primary users to efficiently exploit the spectrum. They do so without degrading the performance of the incumbent users, and may possibly even aid in transmitting their messages as cognitive users are assumed to possess the message(s) of primary user(s) and possibly other cognitive user(s). The survey begins with a short overview of the two-user overlay cognitive interference channel. The evolution from two-user to three-user overlay cognitive interference channels is described next, followed by generalizations to multi-user (arbitrary number of users) cognitive networks. The rest of the paper considers K-user cognitive interference channels with different message knowledge structures at the transmitters. Novel capacity inner and outer bounds are proposed. Channel conditions under which the bounds meet, thus characterizing the information theoretic capacity of the channel, for both Linear Deterministic and Gaussian channel models, are derived. The results show that for certain channel conditions distributed cognition, or having a cumulative message knowledge structure at the nodes, may not be worth the overhead as (approximately) the same capacity can be achieved by having only one global cognitive user whose role is to manage all the interference in the network. The paper concludes with future research directions.
Construction of Near-Capacity Protograph LDPC Code Sequences with Block-Error Thresholds
Venue: arXiv cs.IT 2015
Year: 2015

Density evolution for protograph Low-Density Parity-Check (LDPC) codes is considered, and it is shown that the message-error rate falls double-exponentially with iterations whenever the degree-2 subgraph of the protograph is cycle-free and noise level is below threshold. Conditions for stability of protograph density evolution are established and related to the structure of the protograph. Using large-girth graphs, sequences of protograph LDPC codes with block-error threshold equal to bit-error threshold and block-error rate falling near-exponentially with blocklength are constructed deterministically. Small-sized protographs are optimized to obtain thresholds near capacity for binary erasure and binary-input Gaussian channels.
Economics of Internet of Things (IoT): An Information Market Approach
Venue: arXiv cs.NI 2015
Year: 2015

Internet of things (IoT) has been proposed to be a new paradigm of connecting devices and providing services to various applications, e.g., transportation, energy, smart city, and healthcare. In this paper, we focus on an important issue, i.e., economics of IoT, that can have a great impact to the success of IoT applications. In particular, we adopt and present the information economics approach with its applications in IoT. We first review existing economic models developed for IoT services. Then, we outline two important topics of information economics which are pertinent to IoT, i.e., the value of information and information good pricing. Finally, we propose a game theoretic model to study the price competition of IoT sensing services. Some outlooks on future research directions of applying information economics to IoT are discussed.
Grey-box Modelling of a Household Refrigeration Unit Using Time Series Data in Application to Demand Side Management
Venue: arXiv cs.SY 2015
Year: 2015

This paper describes the application of stochastic grey-box modeling to identify electrical power consumption-to-temperature models of a domestic freezer using experimental measurements. The models are formulated using stochastic differential equations (SDEs), estimated by maximum likelihood estimation (MLE), validated through the model residuals analysis and cross-validated to detect model over-fitting. A nonlinear model based on the reversed Carnot cycle is also presented and included in the modeling performance analysis. As an application of the models, we apply model predictive control (MPC) to shift the electricity consumption of a freezer in demand response experiments, thereby addressing the model selection problem also from the application point of view and showing in an experimental context the ability of MPC to exploit the freezer as a demand side resource (DSR).