OpenRaiser/Intern-Atlas huggingface dataset:
Cost Sharing in the Aspnes Inoculation Model
Venue: arXiv cs.GT 2011
Year: 2011

We consider the use of cost sharing in the Aspnes model of network inoculation, showing that this can improve the cost of the optimal equilibrium by a factor of $O(\sqrt{n})$ in a network of $n$ nodes.
A Comparison of Two Human Brain Tumor Segmentation Methods for MRI Data
Venue: arXiv cs.CV 2011
Year: 2011

The most common primary brain tumors are gliomas, evolving from the cerebral supportive cells. For clinical follow-up, the evaluation of the preoperative tumor volume is essential. Volumetric assessment of tumor volume with manual segmentation of its outlines is a time-consuming process that can be overcome with the help of computerized segmentation methods. In this contribution, two methods for World Health Organization (WHO) grade IV glioma segmentation in the human brain are compared using magnetic resonance imaging (MRI) patient data from the clinical routine. One method uses balloon inflation forces, and relies on detection of high intensity tumor boundaries that are coupled with the use of contrast agent gadolinium. The other method sets up a directed and weighted graph and performs a min-cut for optimal segmentation results. The ground truth of the tumor boundaries - for evaluating the methods on 27 cases - is manually extracted by neurosurgeons with several years of experience in the resection of gliomas. A comparison is performed using the Dice Similarity Coefficient (DSC), a measure for the spatial overlap of different segmentation results.
Cognitive Multiple Access Network with Outage Margin in the Primary System
Venue: arXiv cs.IT 2011
Year: 2011

This paper investigates the problem of spectrally efficient operation of a multiuser uplink cognitive radio system in the presence of a single primary link. The secondary system applies opportunistic interference cancelation (OIC) and decode the primary signal when such an opportunity is created. We derive the achievable rate in the secondary system when OIC is used. This scheme has a practical significance, since it enables rate adaptation without requiring any action from the primary system. The \emph{exact} expressions for outage probability of the primary user are derived, when the primary system is exposed to interference from secondary users. Moreover, approximated formulas and tight lower and upper bounds for the ergodic sum-rate capacity of the secondary network are found. Next, the power allocation is investigated in the secondary system for maximizing the sum-rate under an outage constraint at the primary system. We formulate the power optimization problem in various scenarios depending on the availability of channel state information and the type of power constraints, and propose a set of simple solutions. Finally, the analytical results are confirmed by simulations, indicating both the accuracy of the analysis, and the fact that the spectral-efficient, low-complexity, flexible, and high-performing cognitive radio can be designed based on the proposed schemes.
Power Efficient Resource Allocation for Clouds Using Ant Colony Framework
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing is one of the rapidly improving technologies. It provides scalable resources needed for the ap- plications hosted on it. As cloud-based services become more dynamic, resource provisioning becomes more challenging. The QoS constrained resource allocation problem is considered in this paper, in which customers are willing to host their applications on the provider's cloud with a given SLA requirements for performance such as throughput and response time. Since, the data centers hosting the applications consume huge amounts of energy and cause huge operational costs, solutions that reduce energy consumption as well as operational costs are gaining importance. In this work, we propose an energy efficient mechanism that allocates the cloud resources to the applications without violating the given service level agreements(SLA) using Ant colony framework.
Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems
Venue: arXiv cs.AI 2011
Year: 2011

The analysis of online least squares estimation is at the heart of many stochastic sequential decision making problems. We employ tools from the self-normalized processes to provide a simple and self-contained proof of a tail bound of a vector-valued martingale. We use the bound to construct a new tighter confidence sets for the least squares estimate. We apply the confidence sets to several online decision problems, such as the multi-armed and the linearly parametrized bandit problems. The confidence sets are potentially applicable to other problems such as sleeping bandits, generalized linear bandits, and other linear control problems. We improve the regret bound of the Upper Confidence Bound (UCB) algorithm of Auer et al. (2002) and show that its regret is with high-probability a problem dependent constant. In the case of linear bandits (Dani et al., 2008), we improve the problem dependent bound in the dimension and number of time steps. Furthermore, as opposed to the previous result, we prove that our bound holds for small sample sizes, and at the same time the worst case bound is improved by a logarithmic factor and the constant is improved.
On (Partial) Unit Memory Codes Based on Gabidulin Codes
Venue: arXiv cs.IT 2011
Year: 2011

(Partial) Unit Memory ((P)UM) codes provide a powerful possibility to construct convolutional codes based on block codes in order to achieve a high decoding performance. In this contribution, a construction based on Gabidulin codes is considered. This construction requires a modified rank metric, the so-called sum rank metric. For the sum rank metric, the free rank distance, the extended row rank distance and its slope are defined analogous to the extended row distance in Hamming metric. Upper bounds for the free rank distance and the slope of (P)UM codes in the sum rank metric are derived and an explicit construction of (P)UM codes based on Gabidulin codes is given, achieving the upper bound for the free rank distance.
On the Labeling Problem of Permutation Group Codes under the Infinity Metric
Venue: arXiv cs.IT 2011
Year: 2011

Codes over permutations under the infinity norm have been recently suggested as a coding scheme for correcting limited-magnitude errors in the rank modulation scheme. Given such a code, we show that a simple relabeling operation, which produces an isomorphic code, may drastically change the minimal distance of the code. Thus, we may choose a code structure for efficient encoding/decoding procedures, and then optimize the code's minimal distance via relabeling. We formally define the relabeling problem, and show that all codes may be relabeled to get a minimal distance at most 2. The decision problem of whether a code may be relabeled to distance 1 is shown to be NP-complete, and calculating the best achievable minimal distance after relabeling is proved hard to approximate. Finally, we consider general bounds on the relabeling problem. We specifically show the optimal relabeling distance of cyclic groups. A specific case of a general probabilistic argument is used to show $\agl(p)$ may be relabeled to a minimal distance of $p-O(\sqrt{p\ln p})$.
Spectrum Sensing Based on Blindly Learned Signal Feature
Venue: arXiv cs.IT 2011
Year: 2011

Spectrum sensing is the major challenge in the cognitive radio (CR). We propose to learn local feature and use it as the prior knowledge to improve the detection performance. We define the local feature as the leading eigenvector derived from the received signal samples. A feature learning algorithm (FLA) is proposed to learn the feature blindly. Then, with local feature as the prior knowledge, we propose the feature template matching algorithm (FTM) for spectrum sensing. We use the discrete Karhunen--Lo{è}ve transform (DKLT) to show that such a feature is robust against noise and has maximum effective signal-to-noise ratio (SNR). Captured real-world data shows that the learned feature is very stable over time. It is almost unchanged in 25 seconds. Then, we test the detection performance of the FTM in very low SNR. Simulation results show that the FTM is about 2 dB better than the blind algorithms, and the FTM does not have the noise uncertainty problem.
Usage Bibliometrics
Venue: arXiv cs.DL 2011
Year: 2011

Scholarly usage data provides unique opportunities to address the known shortcomings of citation analysis. However, the collection, processing and analysis of usage data remains an area of active research. This article provides a review of the state-of-the-art in usage-based informetric, i.e. the use of usage data to study the scholarly process.
A FEniCS-Based Programming Framework for Modeling Turbulent Flow by the Reynolds-Averaged Navier-Stokes Equations
Venue: arXiv cs.CE 2011
Year: 2011

Finding an appropriate turbulence model for a given flow case usually calls for extensive experimentation with both models and numerical solution methods. This work presents the design and implementation of a flexible, programmable software framework for assisting with numerical experiments in computational turbulence. The framework targets Reynolds-averaged Navier-Stokes models, discretized by finite element methods. The novel implementation makes use of Python and the FEniCS package, the combination of which leads to compact and reusable code, where model- and solver-specific code resemble closely the mathematical formulation of equations and algorithms. The presented ideas and programming techniques are also applicable to other fields that involve systems of nonlinear partial differential equations. We demonstrate the framework in two applications and investigate the impact of various linearizations on the convergence properties of nonlinear solvers for a Reynolds-averaged Navier-Stokes model.
On the Decoding Complexity of Cyclic Codes Up to the BCH Bound
Venue: arXiv cs.IT 2011
Year: 2011

The standard algebraic decoding algorithm of cyclic codes $[n,k,d]$ up to the BCH bound $t$ is very efficient and practical for relatively small $n$ while it becomes unpractical for large $n$ as its computational complexity is $O(nt)$. Aim of this paper is to show how to make this algebraic decoding computationally more efficient: in the case of binary codes, for example, the complexity of the syndrome computation drops from $O(nt)$ to $O(t\sqrt n)$, and that of the error location from $O(nt)$ to at most $\max \{O(t\sqrt n), O(t^2\log(t)\log(n))\}$.
Establishing Applicability of SSDs to LHC Tier-2 Hardware Configuration
Venue: arXiv cs.DC 2011
Year: 2011

Solid State Disk technologies are increasingly replacing high-speed hard disks as the storage technology in high-random-I/O environments. There are several potentially I/O bound services within the typical LHC Tier-2 - in the back-end, with the trend towards many-core architectures continuing, worker nodes running many single-threaded jobs and storage nodes delivering many simultaneous files can both exhibit I/O limited efficiency. We estimate the effectiveness of affordable SSDs in the context of worker nodes, on a large Tier-2 production setup using both low level tools and real LHC I/O intensive data analysis jobs comparing and contrasting with high performance spinning disk based solutions. We consider the applicability of each solution in the context of its price/performance metrics, with an eye on the pragmatic issues facing Tier-2 provision and upgrades
Reduced-Complexity Collaborative Decoding of Interleaved Reed-Solomon and Gabidulin Codes
Venue: arXiv cs.IT 2011
Year: 2011

An alternative method for collaborative decoding of interleaved Reed-Solomon codes as well as Gabidulin codes for the case of high interleaving degree is proposed. As an example of application, simulation results are presented for a concatenated coding scheme using polar codes as inner codes.
Selecting the rank of truncated SVD by Maximum Approximation Capacity
Venue: arXiv cs.IT 2011
Year: 2011

Truncated Singular Value Decomposition (SVD) calculates the closest rank-$k$ approximation of a given input matrix. Selecting the appropriate rank $k$ defines a critical model order choice in most applications of SVD. To obtain a principled cut-off criterion for the spectrum, we convert the underlying optimization problem into a noisy channel coding problem. The optimal approximation capacity of this channel controls the appropriate strength of regularization to suppress noise. In simulation experiments, this information theoretic method to determine the optimal rank competes with state-of-the art model selection techniques.
Some limits to nonparametric estimation for ergodic processes
Venue: arXiv cs.IT 2011
Year: 2011

A new negative result for nonparametric distribution estimation of binary ergodic processes is shown. The problem of estimation of distribution with any degree of accuracy is studied. Then it is shown that for any countable class of estimators there is a zero-entropy binary ergodic process that is inconsistent with the class of estimators. Our result is different from other negative results for universal forecasting scheme of ergodic processes. We also introduce a related result by B. Weiss.
On Allocation Policies for Power and Performance
Venue: arXiv cs.DC 2011
Year: 2011

With the increasing popularity of Internet-based services and applications, power efficiency is becoming a major concern for data center operators, as high electricity consumption not only increases greenhouse gas emissions, but also increases the cost of running the server farm itself. In this paper we address the problem of maximizing the revenue of a service provider by means of dynamic allocation policies that run the minimum amount of servers necessary to meet user's requirements in terms of performance. The results of several experiments executed using Wikipedia traces are described, showing that the proposed schemes work well, even if the workload is non-stationary. Since any resource allocation policy requires the use of forecasting mechanisms, various schemes allowing compensating errors in the load forecasts are presented and evaluated.
Büchi Automata can have Smaller Quotients
Venue: arXiv cs.FL 2011
Year: 2011

We study novel simulation-like preorders for quotienting nondeterministic Büchi automata. We define fixed-word delayed simulation, a new preorder coarser than delayed simulation. We argue that fixed-word simulation is the coarsest forward simulation-like preorder which can be used for quotienting Büchi automata, thus improving our understanding of the limits of quotienting. Also, we show that computing fixed-word simulation is PSPACE-complete. On the practical side, we introduce proxy simulations, which are novel polynomial-time computable preorders sound for quotienting. In particular, delayed proxy simulation induce quotients that can be smaller by an arbitrarily large factor than direct backward simulation. We derive proxy simulations as the product of a theory of refinement transformers: A refinement transformer maps preorders non-decreasingly, preserving certain properties. We study under which general conditions refinement transformers are sound for quotienting.
An Efficient and Integrated Algorithm for Video Enhancement in Challenging Lighting Conditions
Venue: arXiv cs.GR 2011
Year: 2011

We describe a novel integrated algorithm for real-time enhancement of video acquired under challenging lighting conditions. Such conditions include low lighting, haze, and high dynamic range situations. The algorithm automatically detects the dominate source of impairment, then depending on whether it is low lighting, haze or others, a corresponding pre-processing is applied to the input video, followed by the core enhancement algorithm. Temporal and spatial redundancies in the video input are utilized to facilitate real-time processing and to improve temporal and spatial consistency of the output. The proposed algorithm can be used as an independent module, or be integrated in either a video encoder or a video decoder for further optimizations.
Homology and Robustness of Level and Interlevel Sets
Venue: arXiv cs.CG 2011
Year: 2011

Given a function $f: \Xspace \to \Rspace$ on a topological space, we consider the preimages of intervals and their homology groups and show how to read the ranks of these groups from the extended persistence diagram of $f$. In addition, we quantify the robustness of the homology classes under perturbations of $f$ using well groups, and we show how to read the ranks of these groups from the same extended persistence diagram. The special case $\Xspace = \Rspace^3$ has ramifications in the fields of medical imaging and scientific visualization.
Space-Time Coding over Fading Channels with Stable Noise
Venue: arXiv cs.IT 2011
Year: 2011

This paper addresses the performance of space-time coding over fading channels with impulsive noise which is known to accurately capture network interference. We use the symmetric alpha stable noise distribution and adopt two models which assume dependent and independent noise components across receive antennas. We derive pairwise error probability (PEP) of orthogonal space-time block codes (STBC) with a benchmark genie-aided receiver (GAR), or the minimum distance receiver (MDR) which is optimal in the Gaussian case. For general space-time codes we propose a maximum-likelihood (ML) receiver, and its approximation at high signal-to-noise ratio (SNR). The resulting asymptotically optimal receiver (AOR) does not depend on noise parameters and is computationally simple. Monte-Carlo simulations are used to supplement our analytical results and compare the performance of the receivers.
Scalable constructions of fractional repetition codes in distributed storage systems
Venue: arXiv cs.IT 2011
Year: 2011

In distributed storage systems built using commodity hardware, it is necessary to have data redundancy in order to ensure system reliability. In such systems, it is also often desirable to be able to quickly repair storage nodes that fail. We consider a scheme--introduced by El Rouayheb and Ramchandran--which uses combinatorial block design in order to design storage systems that enable efficient (and exact) node repair. In this work, we investigate systems where node sizes may be much larger than replication degrees, and explicitly provide algorithms for constructing these storage designs. Our designs, which are related to projective geometries, are based on the construction of bipartite cage graphs (with girth 6) and the concept of mutually-orthogonal Latin squares. Via these constructions, we can guarantee that the resulting designs require the fewest number of storage nodes for the given parameters, and can further show that these systems can be easily expanded without need for frequent reconfiguration.
A Graph Theoretical Approach for Network Coding in Wireless Body Area Networks
Venue: arXiv cs.IT 2011
Year: 2011

Modern medical wireless systems, such as wireless body area networks (WBANs), are applications of wireless networks that can be used as a tool of data transmission between patients and doctors. Accuracy of data transmission is an important requirement for such systems. In this paper, we will propose a WBAN which is robust against erasures and describe its properties using graph theoretic techniques.
Orphan-Free Anisotropic Voronoi Diagrams
Venue: arXiv cs.CG 2011
Year: 2011

We describe conditions under which an appropriately-defined anisotropic Voronoi diagram of a set of sites in Euclidean space is guaranteed to be composed of connected cells in any number of dimensions. These conditions are natural for problems in optimization and approximation, and algorithms already exist to produce sets of sites that satisfy them.
A linear framework for region-based image segmentation and inpainting involving curvature penalization
Venue: arXiv cs.CV 2011
Year: 2011

We present the first method to handle curvature regularity in region-based image segmentation and inpainting that is independent of initialization. To this end we start from a new formulation of length-based optimization schemes, based on surface continuation constraints, and discuss the connections to existing schemes. The formulation is based on a \emph{cell complex} and considers basic regions and boundary elements. The corresponding optimization problem is cast as an integer linear program. We then show how the method can be extended to include curvature regularity, again cast as an integer linear program. Here, we are considering pairs of boundary elements to reflect curvature. Moreover, a constraint set is derived to ensure that the boundary variables indeed reflect the boundary of the regions described by the region variables. We show that by solving the linear programming relaxation one gets quite close to the global optimum, and that curvature regularity is indeed much better suited in the presence of long and thin objects compared to standard length regularity.
The detection of "hot regions" in the geography of science: A visualization approach by using density maps
Venue: arXiv cs.DL 2011
Year: 2011

Spatial scientometrics has attracted a lot of attention in the very recent past. The visualization methods (density maps) presented in this paper allow for an analysis revealing regions of excellence around the world using computer programs that are freely available. Based on Scopus and Web of Science data, field-specific and field-overlapping scientific excellence can be identified in broader regions (worldwide or for a specific continent) where high quality papers (highly cited papers or papers published in Nature or Science) were published. We used a geographic information system to produce our density maps. We also briefly discuss the use of Google Earth.
Evolved preambles for MAX-SAT heuristics
Venue: arXiv cs.AI 2011
Year: 2011

MAX-SAT heuristics normally operate from random initial truth assignments to the variables. We consider the use of what we call preambles, which are sequences of variables with corresponding single-variable assignment actions intended to be used to determine a more suitable initial truth assignment for a given problem instance and a given heuristic. For a number of well established MAX-SAT heuristics and benchmark instances, we demonstrate that preambles can be evolved by a genetic algorithm such that the heuristics are outperformed in a significant fraction of the cases.
Subspace Expanders and Matrix Rank Minimization
Venue: arXiv cs.IT 2011
Year: 2011

Matrix rank minimization (RM) problems recently gained extensive attention due to numerous applications in machine learning, system identification and graphical models. In RM problem, one aims to find the matrix with the lowest rank that satisfies a set of linear constraints. The existing algorithms include nuclear norm minimization (NNM) and singular value thresholding. Thus far, most of the attention has been on i.i.d. Gaussian measurement operators. In this work, we introduce a new class of measurement operators, and a novel recovery algorithm, which is notably faster than NNM. The proposed operators are based on what we refer to as subspace expanders, which are inspired by the well known expander graphs based measurement matrices in compressed sensing. We show that given an $n\times n$ PSD matrix of rank $r$, it can be uniquely recovered from a minimal sampling of $O(nr)$ measurements using the proposed structures, and the recovery algorithm can be cast as matrix inversion after a few initial processing steps.