OpenRaiser/Intern-Atlas huggingface dataset:
The Sampling-and-Learning Framework: A Statistical View of Evolutionary Algorithms
Venue: arXiv cs.NE 2014
Year: 2014

Evolutionary algorithms (EAs), a large class of general purpose optimization algorithms inspired from the natural phenomena, are widely used in various industrial optimizations and often show excellent performance. This paper presents an attempt towards revealing their general power from a statistical view of EAs. By summarizing a large range of EAs into the sampling-and-learning framework, we show that the framework directly admits a general analysis on the probable-absolute-approximate (PAA) query complexity. We particularly focus on the framework with the learning subroutine being restricted as a binary classification, which results in the sampling-and-classification (SAC) algorithms. With the help of the learning theory, we obtain a general upper bound on the PAA query complexity of SAC algorithms. We further compare SAC algorithms with the uniform search in different situations. Under the error-target independence condition, we show that SAC algorithms can achieve polynomial speedup to the uniform search, but not super-polynomial speedup. Under the one-side-error condition, we show that super-polynomial speedup can be achieved. This work only touches the surface of the framework. Its power under other conditions is still open.
Encoding Tasks and Rényi Entropy
Venue: arXiv cs.IT 2014
Year: 2014

A task is randomly drawn from a finite set of tasks and is described using a fixed number of bits. All the tasks that share its description must be performed. Upper and lower bounds on the minimum $ρ$-th moment of the number of performed tasks are derived. The case where a sequence of tasks is produced by a source and $n$ tasks are jointly described using $nR$ bits is considered. If $R$ is larger than the Rényi entropy rate of the source of order $1/(1+ρ)$ (provided it exists), then the $ρ$-th moment of the ratio of performed tasks to $n$ can be driven to one as $n$ tends to infinity. If $R$ is smaller than the Rényi entropy rate, this moment tends to infinity. The results are generalized to account for the presence of side-information. In this more general setting, the key quantity is a conditional version of Rényi entropy that was introduced by Arimoto. For IID sources two additional extensions are solved, one of a rate-distortion flavor and the other where different tasks may have different nonnegative costs. Finally, a divergence that was identified by Sundaresan as a mismatch penalty in the Massey-Arikan guessing problem is shown to play a similar role here.
The Capacity of Known Interference Channel (updated)
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate the capacity of known interference channel, where the receiver knows the interference data but not the channel gain of the interference data. We first derive a tight upper bound for the capacity of this known-interference channel. After that, we obtain an achievable rate of the channel with a blind known interference cancellation (BKIC) scheme in closed form. We prove that the aforementioned upper bound in the high SNR regime can be approached by our achievable rate. Moreover, the achievable rate of our BKIC scheme is much larger than that of the traditional interference cancellation scheme. In particular, the achievable rate of BKIC continues to increase with SNR in the high SNR regime (non-zero degree of freedom), while that of the traditional scheme approaches a fixed bound that does not improve with SNR (zero degree of freedom).
Automatic Detection of Calibration Grids in Time-of-Flight Images
Venue: arXiv cs.CV 2014
Year: 2014

It is convenient to calibrate time-of-flight cameras by established methods, using images of a chequerboard pattern. The low resolution of the amplitude image, however, makes it difficult to detect the board reliably. Heuristic detection methods, based on connected image-components, perform very poorly on this data. An alternative, geometrically-principled method is introduced here, based on the Hough transform. The projection of a chequerboard is represented by two pencils of lines, which are identified as oriented clusters in the gradient-data of the image. A projective Hough transform is applied to each of the two clusters, in axis-aligned coordinates. The range of each transform is properly bounded, because the corresponding gradient vectors are approximately parallel. Each of the two transforms contains a series of collinear peaks; one for every line in the given pencil. This pattern is easily detected, by sweeping a dual line through the transform. The proposed Hough-based method is compared to the standard OpenCV detection routine, by application to several hundred time-of-flight images. It is shown that the new method detects significantly more calibration boards, over a greater variety of poses, without any overall loss of accuracy. This conclusion is based on an analysis of both geometric and photometric error.
On Phase Noise Suppression in Full-Duplex Systems
Venue: arXiv cs.IT 2014
Year: 2014

Oscillator phase noise has been shown to be one of the main performance limiting factors in full-duplex systems. In this paper, we consider the problem of self-interference cancellation with phase noise suppression in full-duplex systems. The feasibility of performing phase noise suppression in full-duplex systems in terms of both complexity and achieved gain is analytically and experimentally investigated. First, the effect of phase noise on full-duplex systems and the possibility of performing phase noise suppression are studied. Two different phase noise suppression techniques with a detailed complexity analysis are then proposed. For each suppression technique, both free-running and phase locked loop based oscillators are considered. Due to the fact that full-duplex system performance highly depends on hardware impairments, experimental analysis is essential for reliable results. In this paper, the performance of the proposed techniques is experimentally investigated in a typical indoor environment. The experimental results are shown to confirm the results obtained from numerical simulations on two different experimental research platforms. At the end, the tradeoff between the required complexity and the gain achieved using phase noise suppression is discussed.
The Effect of Network and Infrastructural Variables on SPDY's Performance
Venue: arXiv cs.NI 2014
Year: 2014

HTTP is a successful Internet technology on top of which a lot of the web resides. However, limitations with its current specification, i.e. HTTP/1.1, have encouraged some to look for the next generation of HTTP. In SPDY, Google has come up with such a proposal that has growing community acceptance, especially after being adopted by the IETF HTTPbis-WG as the basis for HTTP/2.0. SPDY has the potential to greatly improve web experience with little deployment overhead. However, we still lack an understanding of its true potential in different environments. This paper seeks to resolve these issues, offering a comprehensive evaluation of SPDY's performance using extensive experiments. We identify the impact of network characteristics and website infrastructure on SPDY's potential page loading benefits, finding that these factors are decisive for SPDY and its optimal deployment strategy. Through this, we feed into the wider debate regarding HTTP/2.0, exploring the key aspects that impact the performance of this future protocol.
Strategic aspects of the probabilistic serial rule for the allocation of goods
Venue: arXiv cs.GT 2014
Year: 2014

The probabilistic serial (PS) rule is one of the most prominent randomized rules for the assignment problem. It is well-known for its superior fairness and welfare properties. However, PS is not immune to manipulative behaviour by the agents. We examine computational and non-computational aspects of strategising under the PS rule. Firstly, we study the computational complexity of an agent manipulating the PS rule. We present polynomial-time algorithms for optimal manipulation. Secondly, we show that expected utility best responses can cycle. Thirdly, we examine the existence and computation of Nash equilibrium profiles under the PS rule. We show that a pure Nash equilibrium is guaranteed to exist under the PS rule. For two agents, we identify two different types of preference profiles that are not only in Nash equilibrium but can also be computed in linear time. Finally, we conduct experiments to check the frequency of manipulability of the PS rule under different combinations of the number of agents, objects, and utility functions.
Anception: Application Virtualization For Android
Venue: arXiv cs.CR 2014
Year: 2014

The problem of malware has become significant on Android devices. Library operating systems and application virtualization are both possible solutions for confining malware. Unfortunately, such solutions do not exist for Android. Designing mechanisms for application virtualization is a significant chal- lenge for several reasons: (1) graphics performance is important due to popularity of games and (2) applications with the same UID can share state. This paper presents Anception, the first flexible application virtualization framework for Android. It is imple- mented as a modification to the Android kernel and supports application virtualization that addresses the above requirements. Anception is able to confine many types of malware while supporting unmodified Android applications. Our Anception- based system exhibits up to 3.9% overhead on various 2D/3D benchmarks, and 1.8% overhead on the SunSpider benchmark.
A Linear-Time Algorithm for Trust Region Problems
Venue: arXiv cs.DS 2014
Year: 2014

We consider the fundamental problem of maximizing a general quadratic function over an ellipsoidal domain, also known as the trust region problem. We give the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving this problem. Specifically, our algorithm returns an $ε$-approximate solution in time $\tilde{O}(N/\sqrtε)$, where $N$ is the number of non-zero entries in the input. This matches the runtime of Nesterov's accelerated gradient descent, suitable for the special case in which the quadratic function is concave, and the runtime of the Lanczos method which is applicable when the problem is purely quadratic.
Optimal Power Allocation in Block Fading Gaussian Channels with Causal CSI and Secrecy Constraints
Venue: arXiv cs.IT 2014
Year: 2014

The optimal power allocation that maximizes the secrecy capacity of block fading Gaussian (BF-Gaussian) networks with causal channel state information (CSI), M-block delay tolerance and a frame based power constraint is examined. In particular, we formulate the secrecy capacity maximization as a dynamic program. We propose suitable linear approximations of the secrecy capacity density in the low SNR, the high SNR and the intermediate SNR regimes, according to the overall available power budget. Our findings indicate that when the available power resources are very low (low SNR case) the optimal strategy is a threshold policy. On the other hand when the available power budget is infinite (high SNR case) a constant power policy maximizes the frame secrecy capacity. Finally, when the power budget is finite (medium SNR case), an approximate tractable power allocation policy is derived.
Zero-Reachability in Probabilistic Multi-Counter Automata
Venue: arXiv cs.FL 2014
Year: 2014

We study the qualitative and quantitative zero-reachability problem in probabilistic multi-counter systems. We identify the undecidable variants of the problems, and then we concentrate on the remaining two cases. In the first case, when we are interested in the probability of all runs that visit zero in some counter, we show that the qualitative zero-reachability is decidable in time which is polynomial in the size of a given pMC and doubly exponential in the number of counters. Further, we show that the probability of all zero-reaching runs can be effectively approximated up to an arbitrarily small given error epsilon > 0 in time which is polynomial in log(epsilon), exponential in the size of a given pMC, and doubly exponential in the number of counters. In the second case, we are interested in the probability of all runs that visit zero in some counter different from the last counter. Here we show that the qualitative zero-reachability is decidable and SquareRootSum-hard, and the probability of all zero-reaching runs can be effectively approximated up to an arbitrarily small given error epsilon > 0 (these result applies to pMC satisfying a suitable technical condition that can be verified in polynomial time). The proof techniques invented in the second case allow to construct counterexamples for some classical results about ergodicity in stochastic Petri nets.
OLAP on Structurally Significant Data in Graphs
Venue: arXiv cs.DB 2014
Year: 2014

Summarized data analysis of graphs using OLAP (Online Analytical Processing) is very popular these days. However due to high dimensionality and large size, it is not easy to decide which data should be aggregated for OLAP analysis. Though iceberg cubing is useful, but it is unaware of the significance of dimensional values with respect to the structure of the graph. In this paper, we propose a Structural Significance, SS, measure to identify the structurally significant dimensional values in each dimension. This leads to structure aware pruning. We then propose an algorithm, iGraphCubing, to compute the graph cube to analyze the structurally significant data using the proposed measure. We evaluated the proposed ideas on real and synthetic data sets and observed very encouraging results.
Co-Evolution of Friendship and Publishing in Online Blogging Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

In the past decade, blogging web sites have become more sophisticated and influential than ever. Much of this sophistication and influence follows from their network organization. Blogging social networks (BSNs) allow individual bloggers to form contact lists, subscribe to other blogs, comment on blog posts, declare interests, and participate in collective blogs. Thus, a BSN is a bimodal venue, where users can engage in publishing (post) as well as in social (make friends) activities. In this paper, we study the co-evolution of both activities. We observed a significant positive correlation between blogging and socializing. In addition, we identified a number of user archetypes that correspond to "mainly bloggers," "mainly socializers," etc. We analyzed a BSN at the level of individual posts and changes in contact lists and at the level of trajectories in the friendship-publishing space. Both approaches produced consistent results: the majority of BSN users are passive readers; publishing is the dominant active behavior in a BSN; and social activities complement blogging, rather than compete with it.
TARVOS - an Event-Based Simulator for Performance Analysis, Supporting MPLS, RSVP-TE, and Fast Recovery
Venue: arXiv cs.NI 2014
Year: 2014

This paper presents a new discrete event-based network simulator named TARVOS - Computer Networks Simulator, being designed as part of the first Author's Masters research and will provide support to simulating MPLS architecture, several RSVP-TE protocol functionalities and fast recovery in case of link failure. The tool is used in a case study, where the impact of a link failure on a VoIP application, within an MPLS domain network, is analyzed. The paper displays a preliminary research of six already available simulators and reasons why they were not adopted as tools for the Masters research. Then, it follows to describe the basics of TARVOS implementation and exhibits the case study simulated by this new tool.
Adaptive Power Management for Wireless Base Station in Smart Grid Environment
Venue: arXiv cs.NI 2014
Year: 2014

The growing concerns of a global environmental change raises a revolution on the way of utilizing energy. In wireless industry, green wireless communications has recently gained increasing attention and is expected to play a major role in reduction of electrical power consumption. In particular, actions to promote energy saving of wireless communications with regard to environmental protection are becoming imperative. To this purpose, we study a green communication system model where wireless base station is provisioned with a combination of renewable power source and electrical grid to minimize power consumption as well as meeting the users' demand. More specifically, we focus on an adaptive power management for wireless base station to minimize power consumption under various uncertainties including renewable power generation, power price, and wireless traffic load. We believe that demand side power management solution based on the studied communication architecture is a major step towards green wireless communications.
Network Connectivity: Stochastic vs. Deterministic Wireless Channels
Venue: arXiv cs.NI 2014
Year: 2014

We study the effect of stochastic wireless channel models on the connectivity of ad hoc networks. Unlike in the deterministic geometric disk model where nodes connect if they are within a certain distance from each other, stochastic models attempt to capture small-scale fading effects due to shadowing and multipath received signals. Through analysis of local and global network observables, we present conclusive evidence suggesting that network behaviour is highly dependent upon whether a stochastic or deterministic connection model is employed. Specifically we show that the network mean degree is lower (higher) for stochastic wireless channels than for deterministic ones, if the path loss exponent is greater (lesser) than the spatial dimension. Similarly, the probability of forming isolated pairs of nodes in an otherwise dense random network is much less for stochastic wireless channels than for deterministic ones. The latter realisation explains why the upper bound of $k$-connectivity is tighter for stochastic wireless channels. We obtain closed form analytic results and compare to extensive numerical simulations.
Reconfigurable Structures for Direct Equalisation in Mobile Receivers
Venue: arXiv cs.IT 2014
Year: 2014

Any communication channel will usually distort the transmitted signal. This is especially true in the case of mobile systems, where multipath propagation causes the received signal to be seriously degraded. Over the years, many techniques have been proposed to combat channel effects. Two of the most popular are linear equalisation (LE) and decision feedback equalisation (DFE). These methods offer a good compromise between performance and computational complexity. LE and DFE are implemented using finite impulse response (FIR) filters whose frequency spectrum approximates the inverse of the channel spectrum plus noise. In mobile systems, the equaliser is made adaptable in order to be able to respond to the channel variations. Adaptability is achieved using adaptive FIR filters whose coefficients are iteratively updated. In principle, an infinite number of filter coefficients would be needed to achieve perfect channel inversion. In practice, the number of taps must be finite. Simulations show that, in realistic scenarios, making the equaliser longer than a certain (undetermined) number of taps will not yield any benefit. Moreover, computation and power will be wasted. In battery powered devices, like mobile terminals, it would be desirable to have the equaliser properly dimensioned. The equaliser's optimum length strongly depends on the particular scenario, and as channel conditions vary, this optimum is likely to vary. This thesis presents novel techniques to perform equaliser length adjustment. Methods for the LE and the DFE have been developed. Simulations in many different scenarios show that the proposed schemes optimise the number of taps to be used. Moreover, these techniques are able to detect changes in the channel and re-adjust the equaliser length appropriately.
Propositional dynamic logic for searching games with errors
Venue: arXiv cs.LO 2014
Year: 2014

We investigate some finitely-valued generalizations of propositional dynamic logic with tests. We start by introducing the (n+1)-valued Kripke models and a corresponding language based on a modal extension of Łukasiewicz many-valued logic. We illustrate the definitions by providing a framework for an analysis of the Rényi - Ulam searching game with errors. Our main result is the axiomatization of the theory of the (n+1)-valued Kripke models. This result is obtained through filtration of the canonical model of the smallest (n+1)-valued propositional dynamic logic.
Contexts of diffusion: Adoption of research synthesis in Social Work and Women's Studies
Venue: arXiv cs.SI 2014
Year: 2014

Texts reveal the subjects of interest in research fields, and the values, beliefs, and practices of researchers. In this study, texts are examined through bibliometric mapping and topic modeling to provide a birds eye view of the social dynamics associated with the diffusion of research synthesis methods in the contexts of Social Work and Women's Studies. Research synthesis texts are especially revealing because the methods, which include meta-analysis and systematic review, are reliant on the availability of past research and data, sometimes idealized as objective, egalitarian approaches to research evaluation, fundamentally tied to past research practices, and performed with the goal informing future research and practice. This study highlights the co-influence of past and subsequent research within research fields; illustrates dynamics of the diffusion process; and provides insight into the cultural contexts of research in Social Work and Women's Studies. This study suggests the potential to further develop bibliometric mapping and topic modeling techniques to inform research problem selection and resource allocation.
Community Detection in Networks with Node Attributes
Venue: arXiv cs.SI 2014
Year: 2014

Community detection algorithms are fundamental tools that allow us to uncover organizational principles in networks. When detecting communities, there are two possible sources of information one can use: the network structure, and the features and attributes of nodes. Even though communities form around nodes that have common edges and common attributes, typically, algorithms have only focused on one of these two data modalities: community detection algorithms traditionally focus only on the network structure, while clustering algorithms mostly consider only node attributes. In this paper, we develop Communities from Edge Structure and Node Attributes (CESNA), an accurate and scalable algorithm for detecting overlapping communities in networks with node attributes. CESNA statistically models the interaction between the network structure and the node attributes, which leads to more accurate community detection as well as improved robustness in the presence of noise in the network structure. CESNA has a linear runtime in the network size and is able to process networks an order of magnitude larger than comparable approaches. Last, CESNA also helps with the interpretation of detected communities by finding relevant node attributes for each community.
Non-Binary LDPC Codes with Large Alphabet Size
Venue: arXiv cs.IT 2014
Year: 2014

We study LDPC codes for the channel with input ${x}\in \mathbb{F}_q^m$ and output ${y}={x}+{z}\in \mathbb{F}_q^m$. The aim of this paper is to evaluate decoding performance of $q^m$-ary non-binary LDPC codes for large $m$. We give density evolution and decoding performance evaluation for regular non-binary LDPC codes and spatially-coupled (SC) codes. We show the regular codes do not achieve the capacity of the channel while SC codes do.