OpenRaiser/Intern-Atlas huggingface dataset:
An ${\cal O}(n\sqrt{m})$ algorithm for the weighted stable set problem in {claw, net}-free graphs with $α(G) \ge 4$
Venue: arXiv cs.DM 2015
Year: 2015

In this paper we show that a connected {claw, net}-free graph $G(V, E)$ with $α(G) \ge 4$ is the union of a strongly bisimplicial clique $Q$ and at most two clique-strips. A clique is strongly bisimplicial if its neighborhood is partitioned into two cliques which are mutually non-adjacent and a clique-strip is a sequence of cliques $\{H_0, \dots, H_p\}$ with the property that $H_i$ is adjacent only to $H_{i-1}$ and $H_{i+1}$. By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem in such a graph in time ${\cal O}(|V|\sqrt{|E|})$.
Unsupervised Segmentation of Multispectral Images with Cellular Automata
Venue: arXiv cs.CV 2015
Year: 2015

Multispectral images acquired by satellites are used to study phenomena on the Earth's surface. Unsupervised classification techniques analyze multispectral image content without considering prior knowledge of the observed terrain; this is done using techniques which group pixels that have similar statistics of digital level distribution in the various image channels. In this paper, we propose a methodology for unsupervised classification based on a deterministic cellular automaton. The automaton is initialized in an unsupervised manner by setting seed cells, selected according to two criteria: to be representative of the spatial distribution of the dominant elements in the image, and to take into account the diversity of spectral signatures in the image. The automaton's evolution is based on an attack rule that is applied simultaneously to all its cells. Among the noteworthy advantages of deterministic cellular automata for multispectral processing of satellite imagery is the consideration of topological information in the image via seed positioning, and the ability to modify the scale of the study.
Sliding window-based Contention Resolution Diversity Slotted ALOHA
Venue: arXiv cs.IT 2015
Year: 2015

Contention Resolution Diversity Slotted ALOHA (CRDSA) and its burst degree optimizations (CRDSA++, IRSA) make use of MAC burst repetitions and Interference Cancellation (IC) making possible to reach throughput values as high as $T \simeq 0.8$ in practical implementations, whereas for the traditional slotted ALOHA $T \simeq 0.37$. However, these new techniques introduce a frame-based access to the channel that limits the performance in terms of throughput and packet delivery delay. In this paper, a new technique named Sliding Window CRDSA (SW-CRDSA) and its counterpart for irregular repetitions (SW-IRSA) are introduced in order to exploit the advantages of MAC burst repetition and Interference Cancellation (IC) with an unframed access scheme. Numerical results are also provided in order to validate the statement of better performance.
Automatic Objects Removal for Scene Completion
Venue: arXiv cs.CV 2015
Year: 2015

With the explosive growth of web-based cameras and mobile devices, billions of photographs are uploaded to the internet. We can trivially collect a huge number of photo streams for various goals, such as 3D scene reconstruction and other big data applications. However, this is not an easy task due to the fact the retrieved photos are neither aligned nor calibrated. Furthermore, with the occlusion of unexpected foreground objects like people, vehicles, it is even more challenging to find feature correspondences and reconstruct realistic scenes. In this paper, we propose a structure based image completion algorithm for object removal that produces visually plausible content with consistent structure and scene texture. We use an edge matching technique to infer the potential structure of the unknown region. Driven by the estimated structure, texture synthesis is performed automatically along the estimated curves. We evaluate the proposed method on different types of images: from highly structured indoor environment to the natural scenes. Our experimental results demonstrate satisfactory performance that can be potentially used for subsequent big data processing: 3D scene reconstruction and location recognition.
On the Effect of I/Q Imbalance on Energy Detection and a Novel Four-Level Hypothesis Spectrum Sensing
Venue: arXiv cs.IT 2015
Year: 2015

Direct-conversion transceivers are in demand, due to low implementation cost of analog front-ends. However, these transmitters or receivers introduce imperfections such as in-phase and quadrature-phase (I/Q) imbalances. In this paper, we first investigate the effect of I/Q imbalance on the performance of primary system, and show that these impairments can severely degrade the performance of cognitive radio system that are based on orthogonal frequency division multiplexing (OFDM) multiple access scheme. Next, we design a new four-level hypothesis blind detector for spectrum sensing in such cognitive radio system, and show that the proposed detector is less vulnerable to I/Q imbalance than conventional two-level detectors.
Are Effective Leaders Creative?
Venue: arXiv cs.MA 2015
Year: 2015

This paper explains in layperson's terms how an agent-based model was used to investigate the widely held belief that creativity is an important component of effective leadership. Creative leadership was found to increase the mean fitness of cultural outputs across an artificial society, but the more creative the followers were, the greater the extent to which the beneficial effect of creative leadership was washed out. Early in a run when the fitness of ideas was low, a form of leadership that entails the highest possible degree of creativity was best for the mean fitness of outputs across the society. As the mean fitness of outputs increased a transition inevitably occurs after which point a less creative style of leadership proved most effective. Implications of these findings are discussed.
Gain-scheduled Leader-follower Tracking Control for Interconnected Parameter Varying Systems
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers the gain-scheduled leader-follower tracking control problem for a parameter varying complex interconnected system with directed communication topology and uncertain norm-bounded coupling between the agents. A gain-scheduled consensus-type control protocol is proposed and a sufficient condition is obtained which guarantees a suboptimal bound on the system tracking performance under this protocol. An interpolation technique is used to obtain a protocol schedule which is continuous in the scheduling parameter. The effectiveness of the proposed method is demonstrated using a simulation example.
!-Graphs with Trivial Overlap are Context-Free
Venue: arXiv cs.LO 2015
Year: 2015

String diagrams are a powerful tool for reasoning about composite structures in symmetric monoidal categories. By representing string diagrams as graphs, equational reasoning can be done automatically by double-pushout rewriting. !-graphs give us the means of expressing and proving properties about whole families of these graphs simultaneously. While !-graphs provide elegant proofs of surprisingly powerful theorems, little is known about the formal properties of the graph languages they define. This paper takes the first step in characterising these languages by showing that an important subclass of !-graphs--those whose repeated structures only overlap trivially--can be encoded using a (context-free) vertex replacement grammar.
Numerical Investigation of Graph Spectra and Information Interpretability of Eigenvalues
Venue: arXiv cs.IT 2015
Year: 2015

We undertake an extensive numerical investigation of the graph spectra of thousands regular graphs, a set of random Erdös-Rényi graphs, the two most popular types of complex networks and an evolving genetic network by using novel conceptual and experimental tools. Our objective in so doing is to contribute to an understanding of the meaning of the Eigenvalues of a graph relative to its topological and information-theoretic properties. We introduce a technique for identifying the most informative Eigenvalues of evolving networks by comparing graph spectra behavior to their algorithmic complexity. We suggest that extending techniques can be used to further investigate the behavior of evolving biological networks. In the extended version of this paper we apply these techniques to seven tissue specific regulatory networks as static example and network of a naïve pluripotent immune cell in the process of differentiating towards a Th17 cell as evolving example, finding the most and least informative Eigenvalues at every stage.
Better Online Deterministic Packet Routing on Grids
Venue: arXiv cs.DS 2015
Year: 2015

We consider the following fundamental routing problem. An adversary inputs packets arbitrarily at sources, each packet with an arbitrary destination. Traffic is constrained by link capacities and buffer sizes, and packets may be dropped at any time. The goal of the routing algorithm is to maximize throughput, i.e., route as many packets as possible to their destination. Our main result is an $O\left(\log n\right)$-competitive deterministic algorithm for an $n$-node line network (i.e., $1$-dimensional grid), requiring only that buffers can store at least $5$ packets, and that links can deliver at least $5$ packets per step. We note that $O(\log n)$ is the best ratio known, even for randomized algorithms, even when allowed large buffers and wide links. The best previous deterministic algorithm for this problem with constant-size buffers and constant-capacity links was $O(\log^5 n)$-competitive. Our algorithm works like admission-control algorithms in the sense that if a packet is not dropped immediately upon arrival, then it is "accepted" and guaranteed to be delivered. We also show how to extend our algorithm to a polylog-competitive algorithm for any constant-dimension grid.
3D Human Activity Recognition with Reconfigurable Convolutional Neural Networks
Venue: arXiv cs.CV 2015
Year: 2015

Human activity understanding with 3D/depth sensors has received increasing attention in multimedia processing and interactions. This work targets on developing a novel deep model for automatic activity recognition from RGB-D videos. We represent each human activity as an ensemble of cubic-like video segments, and learn to discover the temporal structures for a category of activities, i.e. how the activities to be decomposed in terms of classification. Our model can be regarded as a structured deep architecture, as it extends the convolutional neural networks (CNNs) by incorporating structure alternatives. Specifically, we build the network consisting of 3D convolutions and max-pooling operators over the video segments, and introduce the latent variables in each convolutional layer manipulating the activation of neurons. Our model thus advances existing approaches in two aspects: (i) it acts directly on the raw inputs (grayscale-depth data) to conduct recognition instead of relying on hand-crafted features, and (ii) the model structure can be dynamically adjusted accounting for the temporal variations of human activities, i.e. the network configuration is allowed to be partially activated during inference. For model training, we propose an EM-type optimization method that iteratively (i) discovers the latent structure by determining the decomposed actions for each training example, and (ii) learns the network parameters by using the back-propagation algorithm. Our approach is validated in challenging scenarios, and outperforms state-of-the-art methods. A large human activity database of RGB-D videos is presented in addition.
Random access congestion control in DVB-RCS2 interactive satellite terminals
Venue: arXiv cs.IT 2015
Year: 2015

The next generation of interactive satellite terminals is going to play a crucial role in the future of DVB standards. As a matter of fact in the current standard, satellite terminals are expected to be interactive thus offering apart from the possibility of logon signalling and control signalling also data transmission in the return channel with satisfying quality. Considering the nature of the traffic from terminals that is by nature bursty and with big periods of inactivity, the use of a Random Access technique could be preferred. In this paper Random Access congestion control in DVB-RCS2 is considered with particular regard to the recently introduced Contention Resolution Diversity Slotted Aloha technique, able to boost the performance compared to Slotted Aloha. The paper analyzes the stability of such a channel with particular emphasis on the design and on limit control procedures that can be applied in order to ensure stability of the channel even in presence of possible instability due to statistical fluctuations.
Matching or Crashing? Personality-based Team Formation in Crowdsourcing Environments
Venue: arXiv cs.HC 2015
Year: 2015

"Does placing workers together based on their personality give better performance results in cooperative crowdsourcing settings, compared to non-personality based crowd team formation?" In this work we examine the impact of personality compatibility on the effectiveness of crowdsourced team work. Using a personality-based group dynamics approach, we examine two main types of personality combinations (matching and crashing) on two main types of tasks (collaborative and competitive). Our experimental results show that personality compatibility significantly affects the quality of the team's final outcome, the quality of interactions and the emotions experienced by the team members. The present study is the first to examine the effect of personality over team result in crowdsourcing settings, and it has practical implications for the better design of crowdsourced team work.
D-Iteration: diffusion approach for solving PageRank
Venue: arXiv cs.DS 2015
Year: 2015

In this paper we present a new method that can accelerate the computation of the PageRank importance vector. Our method, called D-Iteration (DI), is based on the decomposition of the matrix-vector product that can be seen as a fluid diffusion model and is potentially adapted to asynchronous implementation. We give theoretical results about the convergence of our algorithm and we show through experimentations on a real Web graph that DI can improve the computation efficiency compared to other classical algorithm like Power Iteration, Gauss-Seidel or OPIC.
On the Achievable Rates of Multihop Virtual Full-Duplex Relay Channels
Venue: arXiv cs.IT 2015
Year: 2015

We study a multihop "virtual" full-duplex relay channel as a special case of a general multiple multicast relay network. For such channel, quantize-map-and-forward (QMF) (or noisy network coding (NNC)) achieves the cut-set upper bound within a constant gap where the gap grows {\em linearly} with the number of relay stages $K$. However, this gap may not be negligible for the systems with multihop transmissions (i.e., a wireless backhaul operating at higher frequencies). We have recently attained an improved result to the capacity scaling where the gap grows {\em logarithmically} as $\log{K}$, by using an optimal quantization at relays and by exploiting relays' messages (decoded in the previous time slot) as side-information. In this paper, we further improve the performance of this network by presenting a mixed scheme where each relay can perform either decode-and-forward (DF) or QMF with possibly rate-splitting. We derive the achievable rate and show that the proposed scheme outperforms the QMF-optimized scheme. Furthermore, we demonstrate that this performance improvement increases with $K$.
Optimal Base Station Deployment for Small Cell Networks with Energy-Efficient Power Control
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, how to optimally deploy base station density in a small cell network with energy-efficient power control was investigated. Base stations (BSs) and users form two independent Poisson point processes (PPPs) in the network. Since user-centric cell association may lead to void cells that do not have any users, the power of each BS is controlled in either all-on or on-off mode depending on whether its cell is void or not. The average cell rates for each power control mode are first found and their corresponding energy efficiency is also characterized. The optimal BS density that maximizes the energy efficiency under a given user density is theoretically proved to exist and its value can be found numerically. Both analytical and simulated results indicate that on-off power control is significantly superior to all-on power control in terms of energy efficiency if BSs are deployed based on their optimal energy-efficient density.
High-Girth Matrices and Polarization
Venue: arXiv cs.IT 2015
Year: 2015

The girth of a matrix is the least number of linearly dependent columns, in contrast to the rank which is the largest number of linearly independent columns. This paper considers the construction of {\it high-girth} matrices, whose probabilistic girth is close to its rank. Random matrices can be used to show the existence of high-girth matrices with constant relative rank, but the construction is non-explicit. This paper uses a polar-like construction to obtain a deterministic and efficient construction of high-girth matrices for arbitrary fields and relative ranks. Applications to coding and sparse recovery are discussed.
Improved Practical Matrix Sketching with Guarantees
Venue: arXiv cs.DS 2015
Year: 2015

Matrices have become essential data representations for many large-scale problems in data analytics, and hence matrix sketching is a critical task. Although much research has focused on improving the error/size tradeoff under various sketching paradigms, the many forms of error bounds make these approaches hard to compare in theory and in practice. This paper attempts to categorize and compare most known methods under row-wise streaming updates with provable guarantees, and then to tweak some of these methods to gain practical improvements while retaining guarantees. For instance, we observe that a simple heuristic iSVD, with no guarantees, tends to outperform all known approaches in terms of size/error trade-off. We modify the best performing method with guarantees FrequentDirections under the size/error trade-off to match the performance of iSVD and retain its guarantees. We also demonstrate some adversarial datasets where iSVD performs quite poorly. In comparing techniques in the time/error trade-off, techniques based on hashing or sampling tend to perform better. In this setting we modify the most studied sampling regime to retain error guarantee but obtain dramatic improvements in the time/error trade-off. Finally, we provide easy replication of our studies on APT, a new testbed which makes available not only code and datasets, but also a computing platform with fixed environmental settings.
User Clustering in Online Advertising via Topic Models
Venue: arXiv cs.AI 2015
Year: 2015

In the domain of online advertising, our aim is to serve the best ad to a user who visits a certain webpage, to maximize the chance of a desired action to be performed by this user after seeing the ad. While it is possible to generate a different prediction model for each user to tell if he/she will act on a given ad, the prediction result typically will be quite unreliable with huge variance, since the desired actions are extremely sparse, and the set of users is huge (hundreds of millions) and extremely volatile, i.e., a lot of new users are introduced everyday, or are no longer valid. In this paper we aim to improve the accuracy in finding users who will perform the desired action, by assigning each user to a cluster, where the number of clusters is much smaller than the number of users (in the order of hundreds). Each user will fall into the same cluster with another user if their event history are similar. For this purpose, we modify the probabilistic latent semantic analysis (pLSA) model by assuming the independence of the user and the cluster id, given the history of events. This assumption helps us to identify a cluster of a new user without re-clustering all the users. We present the details of the algorithm we employed as well as the distributed implementation on Hadoop, and some initial results on the clusters that were generated by the algorithm.
Energy Efficient Broadcast in Mobile Networks Subject to Channel Randomness
Venue: arXiv cs.NI 2015
Year: 2015

Wireless communication in a network of mobile devices is a challenging and resource demanding task, due to the highly dynamic network topology and the wireless channel randomness. This paper investigates information broadcast schemes in 2D mobile ad-hoc networks where nodes are initially randomly distributed and then move following a random direction mobility model. Based on an in-depth analysis of the popular Susceptible-Infectious-Recovered epidemic broadcast scheme, this paper proposes a novel energy and bandwidth efficient broadcast scheme, named the energy-efficient broadcast scheme, which is able to adapt to fast-changing network topology and channel randomness. Analytical results are provided to characterize the performance of the proposed scheme, including the fraction of nodes that can receive the information and the delay of the information dissemination process. The accuracy of analytical results is verified using simulations driven by both the random direction mobility model and a real world trace.
On Error Correction for Physical Unclonable Functions
Venue: arXiv cs.IT 2015
Year: 2015

Physical Unclonable Functions evaluate manufacturing variations to generate secure cryptographic keys for embedded systems without secure key storage. It is explained how methods from coding theory are applied in order to ensure reliable key reproduction. We show how better results can be obtained using code classes and decoding principles not used for this scenario before. These methods are exemplified by specific code constructions which improve existing codes with respect to error probability, decoding complexity and codeword length.
A General Preprocessing Method for Improved Performance of Epipolar Geometry Estimation Algorithms
Venue: arXiv cs.CV 2015
Year: 2015

In this paper a deterministic preprocessing algorithm is presented, whose output can be given as input to most state-of-the-art epipolar geometry estimation algorithms, improving their results considerably. They are now able to succeed on hard cases for which they failed before. The algorithm consists of three steps, whose scope changes from local to global. In the local step it extracts from a pair of images local features (e.g. SIFT). Similar features from each image are clustered and the clusters are matched yielding a large number of putative matches. In the second step pairs of spatially close features (called 2keypoints) are matched and ranked by a classifier. The 2keypoint matches with the highest ranks are selected. In the global step, from each two 2keypoint matches a fundamental matrix is computed. As quite a few of the matrices are generated from correct matches they are used to rank the putative matches found in the first step. For each match the number of fundamental matrices, for which it approximately satisfies the epipolar constraint, is calculated. This set of matches is combined with the putative matches generated by standard methods and their probabilities to be correct are estimated by a classifier. These are then given as input to state-of-the-art epipolar geometry estimation algorithms such as BEEM, BLOGS and USAC yielding much better results than the original algorithms. This was shown in extensive testing performed on almost 900 image pairs from six publicly available data-sets.