OpenRaiser/Intern-Atlas huggingface dataset:
Jamming in Fixed-Rate Wireless Systems with Power Constraints - Part I: Fast Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

This is the first part of a two-part paper that studies the problem of jamming in a fixed-rate transmission system with fading. Both transmitter and jammer are subject to power constraints which can be enforced over each codeword short-term / peak) or over all codewords (long-term / average), hence generating different scenarios. All our jamming problems are formulated as zero-sum games, having the probability of outage as pay-off function and power control functions as strategies. The paper aims at providing a comprehensive coverage of these problems, under fast and slow fading, peak and average power constraints, pure and mixed strategies, with and without channel state information (CSI) feedback. In this first part we study the fast fading scenario. We first assume full CSI to be available to all parties. For peak power constraints, a Nash equilibrium of pure strategies is found. For average power constraints, both pure and mixed strategies are investigated. With pure strategies, we derive the optimal power control functions for both intra-frame and inter-frame power allocation. Maximin and minimax solutions are found and shown to be different, which implies the non-existence of a saddle point. In addition we provide alternative perspectives in obtaining the optimal intra-frame power control functions under the long-term power constraints. With mixed strategies, the Nash equilibrium is found by solving the generalized form of an older problem dating back to Bell and Cover \cite{bell}. Finally, we derive a Nash equilibrium of the game in which no CSI is fed back from the receiver. We show that full channel state information brings only a very slight improvement in the system's performance.
Data Diffusion: Dynamic Resource Provision and Data-Aware Scheduling for Data Intensive Applications
Venue: arXiv cs.DC 2008
Year: 2008

Data intensive applications often involve the analysis of large datasets that require large amounts of compute and storage resources. While dedicated compute and/or storage farms offer good task/data throughput, they suffer low resource utilization problem under varying workloads conditions. If we instead move such data to distributed computing resources, then we incur expensive data transfer cost. In this paper, we propose a data diffusion approach that combines dynamic resource provisioning, on-demand data replication and caching, and data locality-aware scheduling to achieve improved resource efficiency under varying workloads. We define an abstract "data diffusion model" that takes into consideration the workload characteristics, data accessing cost, application throughput and resource utilization; we validate the model using a real-world large-scale astronomy application. Our results show that data diffusion can increase the performance index by as much as 34X, and improve application response time by over 506X, while achieving near-optimal throughputs and execution times.
Optimal Power Allocation for Fading Channels in Cognitive Radio Networks: Ergodic Capacity and Outage Capacity
Venue: arXiv cs.IT 2008
Year: 2008

A cognitive radio network (CRN) is formed by either allowing the secondary users (SUs) in a secondary communication network (SCN) to opportunistically operate in the frequency bands originally allocated to a primary communication network (PCN) or by allowing SCN to coexist with the primary users (PUs) in PCN as long as the interference caused by SCN to each PU is properly regulated. In this paper, we consider the latter case, known as spectrum sharing, and study the optimal power allocation strategies to achieve the ergodic capacity and the outage capacity of the SU fading channel under different types of power constraints and fading channel models. In particular, besides the interference power constraint at PU, the transmit power constraint of SU is also considered. Since the transmit power and the interference power can be limited either by a peak or an average constraint, various combinations of power constraints are studied. It is shown that there is a capacity gain for SU under the average over the peak transmit/interference power constraint. It is also shown that fading for the channel between SU transmitter and PU receiver is usually a beneficial factor for enhancing the SU channel capacities.
Providing Virtual Execution Environments: A Twofold Illustration
Venue: arXiv cs.DC 2008
Year: 2008

Platform virtualization helps solving major grid computing challenges: share resource with flexible, user-controlled and custom execution environments and in the meanwhile, isolate failures and malicious code. Grid resource management tools will evolve to embrace support for virtual resource. We present two open source projects that transparently supply virtual execution environments. Tycoon has been developed at HP Labs to optimise resource usage in creating an economy where users bid to access virtual machines and compete for CPU cycles. SmartDomains provides a peer-to-peer layer that automates virtual machines deployment using a description language and deployment engine from HP Labs. These projects demonstrate both client-server and peer-to-peer approaches to virtual resource management. The first case makes extensive use of virtual machines features for dynamic resource allocation. The second translates virtual machines capabilities into a sophisticated language where resource management components can be plugged in configurations and architectures defined at deployment time. We propose to share our experience at CERN openlab developing SmartDomains and deploying Tycoon to give an illustrative introduction to emerging research in virtual resource management.
Open architecture for multilingual parallel texts
Venue: arXiv cs.CL 2008
Year: 2008

Multilingual parallel texts (abbreviated to parallel texts) are linguistic versions of the same content ("translations"); e.g., the Maastricht Treaty in English and Spanish are parallel texts. This document is about creating an open architecture for the whole Authoring, Translation and Publishing Chain (ATP-chain) for the processing of parallel texts.
Game Theory with Costly Computation
Venue: arXiv cs.GT 2008
Year: 2008

We develop a general game-theoretic framework for reasoning about strategic agents performing possibly costly computation. In this framework, many traditional game-theoretic results (such as the existence of a Nash equilibrium) no longer hold. Nevertheless, we can use the framework to provide psychologically appealing explanations to observed behavior in well-studied games (such as finitely repeated prisoner's dilemma and rock-paper-scissors). Furthermore, we provide natural conditions on games sufficient to guarantee that equilibria exist. As an application of this framework, we consider a notion of game-theoretic implementation of mediators in computational games. We show that a special case of this notion is equivalent to a variant of the traditional cryptographic definition of protocol security; this result shows that, when taking computation into account, the two approaches used for dealing with "deviating" players in two different communities -- Nash equilibrium in game theory and zero-knowledge "simulation" in cryptography -- are intimately related.
Model Checking Probabilistic Timed Automata with One or Two Clocks
Venue: arXiv cs.LO 2008
Year: 2008

Probabilistic timed automata are an extension of timed automata with discrete probability distributions. We consider model-checking algorithms for the subclasses of probabilistic timed automata which have one or two clocks. Firstly, we show that PCTL probabilistic model-checking problems (such as determining whether a set of target states can be reached with probability at least 0.99 regardless of how nondeterminism is resolved) are PTIME-complete for one-clock probabilistic timed automata, and are EXPTIME-complete for probabilistic timed automata with two clocks. Secondly, we show that, for one-clock probabilistic timed automata, the model-checking problem for the probabilistic timed temporal logic PCTL is EXPTIME-complete. However, the model-checking problem for the subclass of PCTL which does not permit both punctual timing bounds, which require the occurrence of an event at an exact time point, and comparisons with probability bounds other than 0 or 1, is PTIME-complete for one-clock probabilistic timed automata.
Toward Expressive and Scalable Sponsored Search Auctions
Venue: arXiv cs.DB 2008
Year: 2008

Internet search results are a growing and highly profitable advertising platform. Search providers auction advertising slots to advertisers on their search result pages. Due to the high volume of searches and the users' low tolerance for search result latency, it is imperative to resolve these auctions fast. Current approaches restrict the expressiveness of bids in order to achieve fast winner determination, which is the problem of allocating slots to advertisers so as to maximize the expected revenue given the advertisers' bids. The goal of our work is to permit more expressive bidding, thus allowing advertisers to achieve complex advertising goals, while still providing fast and scalable techniques for winner determination.
Improved Approximations for Guarding 1.5-Dimensional Terrains
Venue: arXiv cs.CG 2008
Year: 2008

We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5. Our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.
Dense Error Correction via L1-Minimization
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the problem of recovering a non-negative sparse signal $\x \in \Re^n$ from highly corrupted linear measurements $\y = A\x + \e \in \Re^m$, where $\e$ is an unknown error vector whose nonzero entries may be unbounded. Motivated by an observation from face recognition in computer vision, this paper proves that for highly correlated (and possibly overcomplete) dictionaries $A$, any non-negative, sufficiently sparse signal $\x$ can be recovered by solving an $\ell^1$-minimization problem: $\min \|\x\|_1 + \|\e\|_1 \quad {subject to} \quad \y = A\x + \e.$ More precisely, if the fraction $ρ$ of errors is bounded away from one and the support of $\x$ grows sublinearly in the dimension $m$ of the observation, then as $m$ goes to infinity, the above $\ell^1$-minimization succeeds for all signals $\x$ and almost all sign-and-support patterns of $\e$. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with nearly 100% of the observations corrupted. The proof relies on a careful characterization of the faces of a convex polytope spanned together by the standard crosspolytope and a set of iid Gaussian vectors with nonzero mean and small variance, which we call the ``cross-and-bouquet'' model. Simulations and experimental results corroborate the findings, and suggest extensions to the result.
Linear Kernelizations for Restricted 3-Hitting Set Problems
Venue: arXiv cs.CC 2008
Year: 2008

The 3-\textsc{Hitting Set} problem is also called the \textsc{Vertex Cover} problem on 3-uniform hypergraphs. In this paper, we address kernelizations of the \textsc{Vertex Cover} problem on 3-uniform hypergraphs. We show that this problem admits a linear kernel in three classes of 3-uniform hypergraphs. We also obtain lower and upper bounds on the kernel size for them by the parametric duality.
Interaction Grammars
Venue: arXiv cs.LO 2008
Year: 2008

Interaction Grammar (IG) is a grammatical formalism based on the notion of polarity. Polarities express the resource sensitivity of natural languages by modelling the distinction between saturated and unsaturated syntactic structures. Syntactic composition is represented as a chemical reaction guided by the saturation of polarities. It is expressed in a model-theoretic framework where grammars are constraint systems using the notion of tree description and parsing appears as a process of building tree description models satisfying criteria of saturation and minimality.
Computer Art in the Former Soviet Bloc
Venue: arXiv cs.MM 2008
Year: 2008

Documents early computer art in the Soviet bloc and describes Marxist art theory.
Between the Information Economy and Student Recruitment: Present Conjuncture and Future Prospects
Venue: arXiv cs.CY 2008
Year: 2008

In university programs and curricula, in general we react to the need to meet market needs. We respond to market stimulus, or at least try to do so. Consider now an inverted view. Consider our data and perspectives in university programs as reflecting and indeed presaging economic trends. In this article I pursue this line of thinking. I show how various past events fit very well into this new view. I provide explanation for why some technology trends happened as they did, and why some current developments are important now.
On the role of metaphor in information visualization
Venue: arXiv cs.HC 2008
Year: 2008

The concept of metaphor, in particular graphical (or visual) metaphor, is central to the field of information visualization. Information graphics and interactive information visualization systems employ a variety of metaphorical devices to make abstract, complex, voluminous, or otherwise difficult-to-comprehend information understandable in graphical terms. This paper explores the use of metaphor in information visualization, advancing the theory previously argued by Johnson, Lakoff, Tversky et al. that many information graphics are metaphorically understood in terms of cognitively entrenched spatial patterns known as image schemas. These patterns serve to structure and constrain abstract reasoning processes via metaphorical projection operations that are grounded in everyday perceptual experiences with phenomena such as containment, movement, and force dynamics. Building on previous research, I argue that information graphics promote comprehension of their target information through the use of graphical patterns that invoke these preexisting schematic structures. I further theorize that the degree of structural alignment of a particular graphic with one or more corresponding image schemas accounts for its perceived degree of intuitiveness. Accordingly, image schema theory can provide a powerful explanatory and predictive framework for visualization research. I review relevant theories of analogy and metaphor, and discuss the image schematic properties of several common types of information graphic. I conclude with the proposal that the inventory of image schemas culled from linguistic studies can serve as the basis for an inventory of design elements suitable for developing intuitive and effective new information visualization techniques.
Moving and resizing of the screen objects
Venue: arXiv cs.HC 2008
Year: 2008

The shape and size of the objects, which we see on the screen, when the application is running, are defined at the design time. By using some sort of adaptive interface, developers give users a chance to resize these objects or on rare occasion even change, but all these changes are predetermined by a developer; user can't go out of the designer's scenario. Making each and all elements moveable / resizable and giving users the full control of these processes, changes the whole idea of applications; programs become user-driven and significantly increase the effectiveness of users' work. This article is about the instrument to turn any screen object into moveable / resizable.
High-SNR Analysis of Outage-Limited Communications with Bursty and Delay-Limited Information
Venue: arXiv cs.IT 2008
Year: 2008

This work analyzes the high-SNR asymptotic error performance of outage-limited communications with fading, where the number of bits that arrive at the transmitter during any time slot is random but the delivery of bits at the receiver must adhere to a strict delay limitation. Specifically, bit errors are caused by erroneous decoding at the receiver or violation of the strict delay constraint. Under certain scaling of the statistics of the bit-arrival process with SNR, this paper shows that the optimal decay behavior of the asymptotic total probability of bit error depends on how fast the burstiness of the source scales down with SNR. If the source burstiness scales down too slowly, the total probability of error is asymptotically dominated by delay-violation events. On the other hand, if the source burstiness scales down too quickly, the total probability of error is asymptotically dominated by channel-error events. However, at the proper scaling, where the burstiness scales linearly with 1/sqrt(log SNR) and at the optimal coding duration and transmission rate, the occurrences of channel errors and delay-violation errors are asymptotically balanced. In this latter case, the optimal exponent of the total probability of error reveals a tradeoff that addresses the question of how much of the allowable time and rate should be used for gaining reliability over the channel and how much for accommodating the burstiness with delay constraints.
Applications of Universal Source Coding to Statistical Analysis of Time Series
Venue: arXiv cs.IT 2008
Year: 2008

We show how universal codes can be used for solving some of the most important statistical problems for time series. By definition, a universal code (or a universal lossless data compressor) can compress any sequence generated by a stationary and ergodic source asymptotically to the Shannon entropy, which, in turn, is the best achievable ratio for lossless data compressors. We consider finite-alphabet and real-valued time series and the following problems: estimation of the limiting probabilities for finite-alphabet time series and estimation of the density for real-valued time series, the on-line prediction, regression, classification (or problems with side information) for both types of the time series and the following problems of hypothesis testing: goodness-of-fit testing, or identity testing, and testing of serial independence. It is important to note that all problems are considered in the framework of classical mathematical statistics and, on the other hand, everyday methods of data compression (or archivers) can be used as a tool for the estimation and testing. It turns out, that quite often the suggested methods and tests are more powerful than known ones when they are applied in practice.
A Fuzzy Commitment Scheme
Venue: arXiv cs.CR 2008
Year: 2008

This paper attempt has been made to explain a fuzzy commitment scheme. In the conventional Commitment schemes, both committed string m and valid opening key are required to enable the sender to prove the commitment. However there could be many instances where the transmission involves noise or minor errors arising purely because of the factors over which neither the sender nor the receiver have any control. The fuzzy commitment scheme presented in this paper is to accept the opening key that is close to the original one in suitable distance metric, but not necessarily identical. The concept itself is illustrated with the help of simple situation.
MBBP for improved iterative channel decoding in 802.16e WiMAX systems
Venue: arXiv cs.IT 2008
Year: 2008

We propose the application of multiple-bases belief-propagation, an optimized iterative decoding method, to a set of rate-1/2 LDPC codes from the IEEE 802.16e WiMAX standard. The presented approach allows for improved decoding performance when signaling over the AWGN channel. As all required operations for this method can be run in parallel, the decoding delay of this method and standard belief-propagation decoding are equal. The obtained results are compared to the performance of LDPC codes optimized with the progressive edge-growth algorithm and to bounds from information theory. It will be shown that the discussed method mitigates the gap to the well-known random coding bound by about 20 percent.
Computing with Classical Real Numbers
Venue: arXiv cs.LO 2008
Year: 2008

There are two incompatible Coq libraries that have a theory of the real numbers; the Coq standard library gives an axiomatic treatment of classical real numbers, while the CoRN library from Nijmegen defines constructively valid real numbers. Unfortunately, this means results about one structure cannot easily be used in the other structure. We present a way interfacing these two libraries by showing that their real number structures are isomorphic assuming the classical axioms already present in the standard library reals. This allows us to use O'Connor's decision procedure for solving ground inequalities present in CoRN to solve inequalities about the reals from the Coq standard library, and it allows theorems from the Coq standard library to apply to problem about the CoRN reals.
Agent-based Ecological Model Calibration - on the Edge of a New Approach
Venue: arXiv cs.AI 2008
Year: 2008

The purpose of this paper is to present a new approach to ecological model calibration -- an agent-based software. This agent works on three stages: 1- It builds a matrix that synthesizes the inter-variable relationships; 2- It analyses the steady-state sensitivity of different variables to different parameters; 3- It runs the model iteratively and measures model lack of fit, adequacy and reliability. Stage 3 continues until some convergence criteria are attained. At each iteration, the agent knows from stages 1 and 2, which parameters are most likely to produce the desired shift on predicted results.
Automatic Identification and Data Extraction from 2-Dimensional Plots in Digital Documents
Venue: arXiv cs.CV 2008
Year: 2008

Most search engines index the textual content of documents in digital libraries. However, scholarly articles frequently report important findings in figures for visual impact and the contents of these figures are not indexed. These contents are often invaluable to the researcher in various fields, for the purposes of direct comparison with their own work. Therefore, searching for figures and extracting figure data are important problems. To the best of our knowledge, there exists no tool to automatically extract data from figures in digital documents. If we can extract data from these images automatically and store them in a database, an end-user can query and combine data from multiple digital documents simultaneously and efficiently. We propose a framework based on image analysis and machine learning to extract information from 2-D plot images and store them in a database. The proposed algorithm identifies a 2-D plot and extracts the axis labels, legend and the data points from the 2-D plot. We also segregate overlapping shapes that correspond to different data points. We demonstrate performance of individual algorithms, using a combination of generated and real-life images.