OpenRaiser/Intern-Atlas huggingface dataset:
Heterogeneous Learning in Zero-Sum Stochastic Games with Incomplete Information
Venue: arXiv cs.LG 2011
Year: 2011

Learning algorithms are essential for the applications of game theory in a networking environment. In dynamic and decentralized settings where the traffic, topology and channel states may vary over time and the communication between agents is impractical, it is important to formulate and study games of incomplete information and fully distributed learning algorithms which for each agent requires a minimal amount of information regarding the remaining agents. In this paper, we address this major challenge and introduce heterogeneous learning schemes in which each agent adopts a distinct learning pattern in the context of games with incomplete information. We use stochastic approximation techniques to show that the heterogeneous learning schemes can be studied in terms of their deterministic ordinary differential equation (ODE) counterparts. Depending on the learning rates of the players, these ODEs could be different from the standard replicator dynamics, (myopic) best response (BR) dynamics, logit dynamics, and fictitious play dynamics. We apply the results to a class of security games in which the attacker and the defender adopt different learning schemes due to differences in their rationality levels and the information they acquire.
On Gaussian Multiple Access Channels with Interference: Achievable Rates and Upper Bounds
Venue: arXiv cs.IT 2011
Year: 2011

We study the interaction between two interfering Gaussian 2-user multiple access channels. The capacity region is characterized under mixed strong--extremely strong interference and individually very strong interference. Furthermore, the sum capacity is derived under a less restricting definition of very strong interference. Finally, a general upper bound on the sum capacity is provided, which is nearly tight for weak cross links.
Mechanism design with uncertain inputs (to err is human, to forgive divine)
Venue: arXiv cs.GT 2011
Year: 2011

We consider a task of scheduling with a common deadline on a single machine. Every player reports to a scheduler the length of his job and the scheduler needs to finish as many jobs as possible by the deadline. For this simple problem, there is a truthful mechanism that achieves maximum welfare in dominant strategies. The new aspect of our work is that in our setting players are uncertain about their own job lengths, and hence are incapable of providing truthful reports (in the strict sense of the word). For a probabilistic model for uncertainty our main results are as follows. 1) Even with relatively little uncertainty, no mechanism can guarantee a constant fraction of the maximum welfare. 2) To remedy this situation, we introduce a new measure of economic efficiency, based on a notion of a {\em fair share} of a player, and design mechanisms that are $Ω(1)$-fair. In addition to its intrinsic appeal, our notion of fairness implies good approximation of maximum welfare in several cases of interest. 3) In our mechanisms the machine is sometimes left idle even though there are jobs that want to use it. We show that this unfavorable aspect is unavoidable, unless one gives up other favorable aspects (e.g., give up $Ω(1)$-fairness). We also consider a qualitative approach to uncertainty as an alternative to the probabilistic quantitative model. In the qualitative approach we break away from solution concepts such as dominant strategies (they are no longer well defined), and instead suggest an axiomatic approach, which amounts to listing desirable properties for mechanisms. We provide a mechanism that satisfies these properties.
Aneka Cloud Application Platform and Its Integration with Windows Azure
Venue: arXiv cs.DC 2011
Year: 2011

Aneka is an Application Platform-as-a-Service (Aneka PaaS) for Cloud Computing. It acts as a framework for building customized applications and deploying them on either public or private Clouds. One of the key features of Aneka is its support for provisioning resources on different public Cloud providers such as Amazon EC2, Windows Azure and GoGrid. In this chapter, we will present Aneka platform and its integration with one of the public Cloud infrastructures, Windows Azure, which enables the usage of Windows Azure Compute Service as a resource provider of Aneka PaaS. The integration of the two platforms will allow users to leverage the power of Windows Azure Platform for Aneka Cloud Computing, employing a large number of compute instances to run their applications in parallel. Furthermore, customers of the Windows Azure platform can benefit from the integration with Aneka PaaS by embracing the advanced features of Aneka in terms of multiple programming models, scheduling and management services, application execution services, accounting and pricing services and dynamic provisioning services. Finally, in addition to the Windows Azure Platform we will illustrate in this chapter the integration of Aneka PaaS with other public Cloud platforms such as Amazon EC2 and GoGrid, and virtual machine management platforms such as Xen Server. The new support of provisioning resources on Windows Azure once again proves the adaptability, extensibility and flexibility of Aneka.
Extended Non-Binary Low-Density Parity-Check Codes over Erasure Channels
Venue: arXiv cs.IT 2011
Year: 2011

Based on the extended binary image of non-binary LDPC codes, we propose a method for generating extra redundant bits, such as to decreases the coding rate of a mother code. The proposed method allows for using the same decoder, regardless of how many extra redundant bits have been produced, which considerably increases the flexibility of the system without significantly increasing its complexity. Extended codes are also optimized for the binary erasure channel, by using density evolution methods. Nevertheless, the results presented in this paper can easily be extrapolated to more general channel models.
Smart Finite State Devices: A Modeling Framework for Demand Response Technologies
Venue: arXiv cs.SY 2011
Year: 2011

We introduce and analyze Markov Decision Process (MDP) machines to model individual devices which are expected to participate in future demand-response markets on distribution grids. We differentiate devices into the following four types: (a) optional loads that can be shed, e.g. light dimming; (b) deferrable loads that can be delayed, e.g. dishwashers; (c) controllable loads with inertia, e.g. thermostatically-controlled loads, whose task is to maintain an auxiliary characteristic (temperature) within pre-defined margins; and (d) storage devices that can alternate between charging and generating. Our analysis of the devices seeks to find their optimal price-taking control strategy under a given stochastic model of the distribution market.
Constructing test instances for Basis Pursuit Denoising
Venue: arXiv cs.IT 2011
Year: 2011

The number of available algorithms for the so-called Basis Pursuit Denoising problem (or the related LASSO-problem) is large and keeps growing. Similarly, the number of experiments to evaluate and compare these algorithms on different instances is growing. In this note, we present a method to produce instances with exact solutions which is based on a simple observation which is related to the so called source condition from sparse regularization.
A note on active learning for smooth problems
Venue: arXiv cs.LG 2011
Year: 2011

We show that the disagreement coefficient of certain smooth hypothesis classes is $O(m)$, where $m$ is the dimension of the hypothesis space, thereby answering a question posed in \cite{friedman09}.
High-Throughput Transaction Executions on Graphics Processors
Venue: arXiv cs.DB 2011
Year: 2011

OLTP (On-Line Transaction Processing) is an important business system sector in various traditional and emerging online services. Due to the increasing number of users, OLTP systems require high throughput for executing tens of thousands of transactions in a short time period. Encouraged by the recent success of GPGPU (General-Purpose computation on Graphics Processors), we propose GPUTx, an OLTP engine performing high-throughput transaction executions on the GPU for in-memory databases. Compared with existing GPGPU studies usually optimizing a single task, transaction executions require handling many small tasks concurrently. Specifically, we propose the bulk execution model to group multiple transactions into a bulk and to execute the bulk on the GPU as a single task. The transactions within the bulk are executed concurrently on the GPU. We study three basic execution strategies (one with locks and the other two lock-free), and optimize them with the GPU features including the hardware support of atomic operations, the massive thread parallelism and the SPMD (Single Program Multiple Data) execution. We evaluate GPUTx on a recent NVIDIA GPU in comparison with its counterpart on a quad-core CPU. Our experimental results show that optimizations on GPUTx significantly improve the throughput, and the optimized GPUTx achieves 4-10 times higher throughput than its CPU-based counterpart on public transaction processing benchmarks.
Reduced Ordered Binary Decision Diagram with Implied Literals: A New knowledge Compilation Approach
Venue: arXiv cs.AI 2011
Year: 2011

Knowledge compilation is an approach to tackle the computational intractability of general reasoning problems. According to this approach, knowledge bases are converted off-line into a target compilation language which is tractable for on-line querying. Reduced ordered binary decision diagram (ROBDD) is one of the most influential target languages. We generalize ROBDD by associating some implied literals in each node and the new language is called reduced ordered binary decision diagram with implied literals (ROBDD-L). Then we discuss a kind of subsets of ROBDD-L called ROBDD-i with precisely i implied literals (0 \leq i \leq \infty). In particular, ROBDD-0 is isomorphic to ROBDD; ROBDD-\infty requires that each node should be associated by the implied literals as many as possible. We show that ROBDD-i has uniqueness over some specific variables order, and ROBDD-\infty is the most succinct subset in ROBDD-L and can meet most of the querying requirements involved in the knowledge compilation map. Finally, we propose an ROBDD-i compilation algorithm for any i and a ROBDD-\infty compilation algorithm. Based on them, we implement a ROBDD-L package called BDDjLu and then get some conclusions from preliminary experimental results: ROBDD-\infty is obviously smaller than ROBDD for all benchmarks; ROBDD-\infty is smaller than the d-DNNF the benchmarks whose compilation results are relatively small; it seems that it is better to transform ROBDDs-\infty into FBDDs and ROBDDs rather than straight compile the benchmarks.
Multi-parameter acoustic imaging of uniform objects in inhomogeneous media
Venue: arXiv cs.CV 2011
Year: 2011

The problem studied in this paper is ultrasound image reconstruction from frequency-domain measurements of the scattered field from an object with contrast in attenuation and sound speed. The case where the object has uniform but unknown contrast in these properties relative to the background is considered. Background clutter is taken into account in a physically realistic manner by considering an exact scattering model for randomly located small scatterers that vary in sound speed. The resulting statistical characteristics of the interference is incorporated into the imaging solution, which includes applying a total-variation minimization based approach where the relative effect of perturbation in sound speed to attenuation is included as a parameter. Convex optimization methods provide the basis for the reconstruction algorithm. Numerical data for inversion examples are generated by solving the discretized Lippman-Schwinger equation for the object and speckle-forming scatterers in the background. A statistical model based on the Born approximation is used for reconstruction of the object profile. Results are presented for a two dimensional problem in terms of classification performance and compared to minimum-l2-norm reconstruction. Classification using the proposed method is shown to be robust down to a signal-to-clutter ratio of less than 1 dB.
Superposition as a logical glue
Venue: arXiv cs.LO 2011
Year: 2011

The typical mathematical language systematically exploits notational and logical abuses whose resolution requires not just the knowledge of domain specific notation and conventions, but not trivial skills in the given mathematical discipline. A large part of this background knowledge is expressed in form of equalities and isomorphisms, allowing mathematicians to freely move between different incarnations of the same entity without even mentioning the transformation. Providing ITP-systems with similar capabilities seems to be a major way to improve their intelligence, and to ease the communication between the user and the machine. The present paper discusses our experience of integration of a superposition calculus within the Matita interactive prover, providing in particular a very flexible, "smart" application tactic, and a simple, innovative approach to automation.
Stateless HOL
Venue: arXiv cs.LO 2011
Year: 2011

We present a version of the HOL Light system that supports undoing definitions in such a way that this does not compromise the soundness of the logic. In our system the code that keeps track of the constants that have been defined thus far has been moved out of the kernel. This means that the kernel now is purely functional. The changes to the system are small. All existing HOL Light developments can be run by the stateless system with only minor changes. The basic principle behind the system is not to name constants by strings, but by pairs consisting of a string and a definition. This means that the data structures for the terms are all merged into one big graph. OCaml - the implementation language of the system - can use pointer equality to establish equality of data structures fast. This allows the system to run at acceptable speeds. Our system runs at about 85% of the speed of the stateful version of HOL Light.
A Dynamic Multimedia User-Weight Classification Scheme for IEEE_802.11 WLANs
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we expose a dynamic traffic-classification scheme to support multimedia applications such as voice and broadband video transmissions over IEEE 802.11 Wireless Local Area Networks (WLANs). Obviously, over a Wi-Fi link and to better serve these applications - which normally have strict bounded transmission delay or minimum link rate requirement - a service differentiation technique can be applied to the media traffic transmitted by the same mobile node using the well-known 802.11e Enhanced Distributed Channel Access (EDCA) protocol. However, the given EDCA mode does not offer user differentiation, which can be viewed as a deficiency in multi-access wireless networks. Accordingly, we propose a new inter-node priority access scheme for IEEE 802.11e networks which is compatible with the EDCA scheme. The proposed scheme joins a dynamic user-weight to each mobile station depending on its outgoing data, and therefore deploys inter-node priority for the channel access to complement the existing EDCA inter-frame priority. This provides efficient quality of service control across multiple users within the same coverage area of an access point. We provide performance evaluations to compare the proposed access model with the basic EDCA 802.11 MAC protocol mode to elucidate the quality improvement achieved for multimedia communication over 802.11 WLANs.
Beyond the Cut-Set Bound: Uncertainty Computations in Network Coding with Correlated Sources
Venue: arXiv cs.IT 2011
Year: 2011

Cut-set bounds on achievable rates for network communication protocols are not in general tight. In this paper we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, that results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of "uncertainty region" which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture.
Diversity-Multiplexing Tradeoff in the Multiaccess Relay Channel with Finite Block Length
Venue: arXiv cs.IT 2011
Year: 2011

The Dynamic Decode-and-Forward (DDF) protocol and the Hybrid DDF and Amplified-and-Forward (HDAF) protocol for the multiple-access relay channel (MARC) with quasi static fading are evaluated using the Zheng-Tse diversity-multiplexing tradeoff (DMT). We assume that there are two users, one half-duplex relay, and a common destination, each equipped with single antenna. For the Rayleigh fading, the DDF protocol is well known and has been analyzed in terms of the DMT with infinite block length. By carefully dealing with properties specific to finite block length, we characterize the finite block length DMT which takes into account the fact that the event of decoding error at the relay causes the degradation in error performance when the block length is finite. Furthermore, we consider the situation where the destination does not have a priori knowledge of the relay decision time at which the relay switches from listening to transmitting. By introducing a decision rejection criterion such that the relay forwards message only when its decision is reliable, and the generalized likelihood ratio test (GLRT) at the destination that jointly decodes the relay decision time and the information message, our analysis show that the optimal DMT is achievable as if there is no decoding error at the relay and the relay decision time is known at the destination. Therefore, infinite block length and additional overhead for communicating the decision time are not needed for the DDF to achieve the optimal DMT. To further improve the DMT, we propose the HDAF protocol which take advantages of both the DDF and the Amplified-and-Forward protocols by judiciously choosing which protocol to use. Our result shows that the HDAF protocol outperforms the original DDF in the DMT perspective. Finally, a variant of the HDAF protocol with lower implementation complexity without sacrificing the DMT performance is devised.
MDS Array Codes with Optimal Rebuilding
Venue: arXiv cs.IT 2011
Year: 2011

MDS array codes are widely used in storage systems to protect data against erasures. We address the \emph{rebuilding ratio} problem, namely, in the case of erasures, what is the the fraction of the remaining information that needs to be accessed in order to rebuild \emph{exactly} the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting (and more practical) case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of $r$-erasure correcting MDS array codes that has optimal rebuilding ratio of $\frac{1}{r}$ in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the case $r=2$ they use a finite field of size 3) and an optimal update property.
Using a Secret Key to Foil an Eavesdropper
Venue: arXiv cs.CR 2011
Year: 2011

This work addresses private communication with distributed systems in mind. We consider how to best use secret key resources and communication to transmit signals across a system so that an eavesdropper is least capable to act on the signals. One of the key assumptions is that the private signals are publicly available with a delay---in this case a delay of one. We find that even if the source signal (information source) is memoryless, the design and performance of the optimal system has a strong dependence on which signals are assumed to be available to the eavesdropper with delay. Specifically, we consider a distributed system with two components where information is known to only one component and communication resources are limited. Instead of measuring secrecy by "equivocation," we define a value function for the system, based on the actions of the system and the adversary, and characterize the optimal performance of the system, as measured by the average value obtained against the worst adversary. The resulting optimal rate-payoff region is expressed with information theoretic inequalities, and the optimal communication methods are not standard source coding techniques but instead are methods that stem from synthesizing a memoryless channel.
A Simple Sampling Method for Metric Measure Spaces
Venue: arXiv cs.IT 2011
Year: 2011

We introduce a new, simple metric method of sampling metric measure spaces, based on a well-known "snowflakeing operator" and we show that, as a consequence of a classical result of Assouad, the sampling of doubling metric spaces is bilipschitz equivalent to that of subsets of some $\mathbb{R}^N$. Moreover, we compare this new method with two other approaches, in particular to one that represents a direct application of our triangulation method of metric measure spaces satisfying a generalized Ricci curvature condition.
Difference Sequence Compression of Multidimensional Databases
Venue: arXiv cs.DB 2011
Year: 2011

The multidimensional databases often use compression techniques in order to decrease the size of the database. This paper introduces a new method called difference sequence compression. Under some conditions, this new technique is able to create a smaller size multidimensional database than others like single count header compression, logical position compression or base-offset compression. Keywords: compression, multidimensional database, On-line Analytical Processing, OLAP.