OpenRaiser/Intern-Atlas huggingface dataset:
Settling the Complexity of Computing Two-Player Nash Equilibria
Venue: arXiv cs.GT 2007
Year: 2007

We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991. This is the first of a series of results concerning the complexity of Nash equilibria. In particular, we prove the following theorems: Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time. The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time. Our results demonstrate that, even in the simplest form of non-cooperative games, equilibrium computation and approximation are polynomial-time equivalent to fixed point computation. Our results also have two broad complexity implications in mathematical economics and operations research: Arrow-Debreu market equilibria are PPAD-hard to compute. The P-Matrix Linear Complementary Problem is computationally harder than convex programming unless every problem in PPAD is solvable in polynomial time.
Performance Analysis of the IEEE 802.11e Enhanced Distributed Coordination Function using Cycle Time Approach
Venue: arXiv cs.OH 2007
Year: 2007

The recently ratified IEEE 802.11e standard defines the Enhanced Distributed Channel Access (EDCA) function for Quality-of-Service (QoS) provisioning in the Wireless Local Area Networks (WLANs). The EDCA uses Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) and slotted Binary Exponential Backoff (BEB) mechanism. We present a simple mathematical analysis framework for the EDCA function. Our analysis considers the fact that the distributed random access systems exhibit cyclic behavior where each station successfully transmits a packet in a cycle. Our analysis shows that an AC-specific cycle time exists for the EDCA function. Validating the theoretical results via simulations, we show that the proposed analysis accurately captures EDCA saturation performance in terms of average throughput, medium access delay, and packet loss ratio. The cycle time analysis is a simple and insightful substitute for previously proposed more complex EDCA models.
Blind Identification of Distributed Antenna Systems with Multiple Carrier Frequency Offsets
Venue: arXiv cs.IT 2007
Year: 2007

In spatially distributed multiuser antenna systems, the received signal contains multiple carrier-frequency offsets (CFOs) arising from mismatch between the oscillators of transmitters and receivers. This results in a time-varying rotation of the data constellation, which needs to be compensated at the receiver before symbol recovery. In this paper, a new approach for blind CFO estimation and symbol recovery is proposed. The received base-band signal is over-sampled, and its polyphase components are used to formulate a virtual Multiple-Input Multiple-Output (MIMO) problem. By applying blind MIMO system estimation techniques, the system response can be estimated and decoupled versions of the user symbols can be recovered, each one of which contains a distinct CFO. By applying a decision feedback Phase Lock Loop (PLL), the CFO can be mitigated and the transmitted symbols can be recovered. The estimated MIMO system response provides information about the CFOs that can be used to initialize the PLL, speed up its convergence, and avoid ambiguities usually linked with PLL.
Extensive Games with Possibly Unaware Players
Venue: arXiv cs.GT 2007
Year: 2007

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of, and to subjective games, where payers may have no common knowledge regarding the actual game and their beliefs are incompatible with a common prior.
Introduction to Arabic Speech Recognition Using CMUSphinx System
Venue: arXiv cs.CL 2007
Year: 2007

In this paper Arabic was investigated from the speech recognition problem point of view. We propose a novel approach to build an Arabic Automated Speech Recognition System (ASR). This system is based on the open source CMU Sphinx-4, from the Carnegie Mellon University. CMU Sphinx is a large-vocabulary; speaker-independent, continuous speech recognition system based on discrete Hidden Markov Models (HMMs). We build a model using utilities from the OpenSource CMU Sphinx. We will demonstrate the possible adaptability of this system to Arabic voice recognition.
Arabic Speech Recognition System using CMU-Sphinx4
Venue: arXiv cs.CL 2007
Year: 2007

In this paper we present the creation of an Arabic version of Automated Speech Recognition System (ASR). This system is based on the open source Sphinx-4, from the Carnegie Mellon University. Which is a speech recognition system based on discrete hidden Markov models (HMMs). We investigate the changes that must be made to the model to adapt Arabic voice recognition. Keywords: Speech recognition, Acoustic model, Arabic language, HMMs, CMUSphinx-4, Artificial intelligence.
Parallel computing for the finite element method
Venue: arXiv cs.DC 2007
Year: 2007

A finite element method is presented to compute time harmonic microwave fields in three dimensional configurations. Nodal-based finite elements have been coupled with an absorbing boundary condition to solve open boundary problems. This paper describes how the modeling of large devices has been made possible using parallel computation, New algorithms are then proposed to implement this formulation on a cluster of workstations (10 DEC ALPHA 300X) and on a CRAY C98. Analysis of the computation efficiency is performed using simple problems. The electromagnetic scattering of a plane wave by a perfect electric conducting airplane is finally given as example.
Signal Set Design for Full-Diversity Low-Decoding-Complexity Differential Scaled-Unitary STBCs
Venue: arXiv cs.IT 2007
Year: 2007

The problem of designing high rate, full diversity noncoherent space-time block codes (STBCs) with low encoding and decoding complexity is addressed. First, the notion of $g$-group encodable and $g$-group decodable linear STBCs is introduced. Then for a known class of rate-1 linear designs, an explicit construction of fully-diverse signal sets that lead to four-group encodable and four-group decodable differential scaled unitary STBCs for any power of two number of antennas is provided. Previous works on differential STBCs either sacrifice decoding complexity for higher rate or sacrifice rate for lower decoding complexity.
Noncoherent Low-Decoding-Complexity Space-Time Codes for Wireless Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

The differential encoding/decoding setup introduced by Kiran et al, Oggier et al and Jing et al for wireless relay networks that use codebooks consisting of unitary matrices is extended to allow codebooks consisting of scaled unitary matrices. For such codebooks to be used in the Jing-Hassibi protocol for cooperative diversity, the conditions that need to be satisfied by the relay matrices and the codebook are identified. A class of previously known rate one, full diversity, four-group encodable and four-group decodable Differential Space-Time Codes (DSTCs) is proposed for use as Distributed DSTCs (DDSTCs) in the proposed set up. To the best of our knowledge, this is the first known low decoding complexity DDSTC scheme for cooperative wireless networks.
Narratives within immersive technologies
Venue: arXiv cs.HC 2007
Year: 2007

The main goal of this project is to research technical advances in order to enhance the possibility to develop narratives within immersive mediated environments. An important part of the research is concerned with the question of how a script can be written, annotated and realized for an immersive context. A first description of the main theoretical framework and the ongoing work and a first script example is provided. This project is part of the program for presence research, and it will exploit physiological feedback and Computational Intelligence within virtual reality.
Minimum Expected Distortion in Gaussian Layered Broadcast Coding with Successive Refinement
Venue: arXiv cs.IT 2007
Year: 2007

A transmitter without channel state information (CSI) wishes to send a delay-limited Gaussian source over a slowly fading channel. The source is coded in superimposed layers, with each layer successively refining the description in the previous one. The receiver decodes the layers that are supported by the channel realization and reconstructs the source up to a distortion. In the limit of a continuum of infinite layers, the optimal power distribution that minimizes the expected distortion is given by the solution to a set of linear differential equations in terms of the density of the fading distribution. In the optimal power distribution, as SNR increases, the allocation over the higher layers remains unchanged; rather the extra power is allocated towards the lower layers. On the other hand, as the bandwidth ratio b (channel uses per source symbol) tends to zero, the power distribution that minimizes expected distortion converges to the power distribution that maximizes expected capacity. While expected distortion can be improved by acquiring CSI at the transmitter (CSIT) or by increasing diversity from the realization of independent fading paths, at high SNR the performance benefit from diversity exceeds that from CSIT, especially when b is large.
A Channel that Heats Up
Venue: arXiv cs.IT 2007
Year: 2007

Motivated by on-chip communication, a channel model is proposed where the variance of the additive noise depends on the weighted sum of the past channel input powers. For this channel, an expression for the capacity per unit cost is derived, and it is shown that the expression holds also in the presence of feedback.
Algorithm for Evaluation of the Interval Power Function of Unconstrained Arguments
Venue: arXiv cs.MS 2007
Year: 2007

We describe an algorithm for evaluation of the interval extension of the power function of variables x and y given by the expression x^y. Our algorithm reduces the general case to the case of non-negative bases.
An Adaptive Strategy for the Classification of G-Protein Coupled Receptors
Venue: arXiv cs.AI 2007
Year: 2007

One of the major problems in computational biology is the inability of existing classification models to incorporate expanding and new domain knowledge. This problem of static classification models is addressed in this paper by the introduction of incremental learning for problems in bioinformatics. Many machine learning tools have been applied to this problem using static machine learning structures such as neural networks or support vector machines that are unable to accommodate new information into their existing models. We utilize the fuzzy ARTMAP as an alternate machine learning system that has the ability of incrementally learning new data as it becomes available. The fuzzy ARTMAP is found to be comparable to many of the widespread machine learning systems. The use of an evolutionary strategy in the selection and combination of individual classifiers into an ensemble system, coupled with the incremental learning ability of the fuzzy ARTMAP is proven to be suitable as a pattern classifier. The algorithm presented is tested using data from the G-Coupled Protein Receptors Database and shows good accuracy of 83%. The system presented is also generally applicable, and can be used in problems in genomics and proteomics.
Conception d'un banc d'essais décisionnel
Venue: arXiv cs.DB 2007
Year: 2007

We present in this paper a new benchmark for evaluating the performances of data warehouses. Benchmarking is useful either to system users for comparing the performances of different systems, or to system engineers for testing the effect of various design choices. While the TPC (Transaction Processing Performance Council) standard benchmarks address the first point, they are not tuneable enough to address the second one. Our Data Warehouse Engineering Benchmark (DWEB) allows to generate various ad-hoc synthetic data warehouses and workloads. DWEB is fully parameterized. However, two levels of parameterization keep it easy to tune. Since DWEB mainly meets engineering benchmarking needs, it is complimentary to the TPC standard benchmarks, and not a competitor. Finally, DWEB is implemented as a Java free software that can be interfaced with most existing relational database management systems.
Comparing Robustness of Pairwise and Multiclass Neural-Network Systems for Face Recognition
Venue: arXiv cs.AI 2007
Year: 2007

Noise, corruptions and variations in face images can seriously hurt the performance of face recognition systems. To make such systems robust, multiclass neuralnetwork classifiers capable of learning from noisy data have been suggested. However on large face data sets such systems cannot provide the robustness at a high level. In this paper we explore a pairwise neural-network system as an alternative approach to improving the robustness of face recognition. In our experiments this approach is shown to outperform the multiclass neural-network system in terms of the predictive accuracy on the face images corrupted by noise.
Rough Sets Computations to Impute Missing Data
Venue: arXiv cs.CV 2007
Year: 2007

Many techniques for handling missing data have been proposed in the literature. Most of these techniques are overly complex. This paper explores an imputation technique based on rough set computations. In this paper, characteristic relations are introduced to describe incompletely specified decision tables.It is shown that the basic rough set idea of lower and upper approximations for incompletely specified decision tables may be defined in a variety of different ways. Empirical results obtained using real data are given and they provide a valuable and promising insight to the problem of missing data. Missing data were predicted with an accuracy of up to 99%.
Evaluating Personal Archiving Strategies for Internet-based Information
Venue: arXiv cs.DL 2007
Year: 2007

Internet-based personal digital belongings present different vulnerabilities than locally stored materials. We use responses to a survey of people who have recovered lost websites, in combination with supplementary interviews, to paint a fuller picture of current curatorial strategies and practices. We examine the types of personal, topical, and commercial websites that respondents have lost and the reasons they have lost this potentially valuable material. We further explore what they have tried to recover and how the loss influences their subsequent practices. We found that curation of personal digital materials in online stores bears some striking similarities to the curation of similar materials stored locally in that study participants continue to archive personal assets by relying on a combination of benign neglect, sporadic backups, and unsystematic file replication. However, we have also identified issues specific to Internet-based material: how risk is spread by distributing the files among multiple servers and services; the circular reasoning participants use when they discuss the safety of their digital assets; and the types of online material that are particularly vulnerable to loss. The study reveals ways in which expectations of permanence and notification are violated and situations in which benign neglect has far greater consequences for the long-term fate of important digital assets.
Distributed Algorithms for Spectrum Allocation, Power Control, Routing, and Congestion Control in Wireless Networks
Venue: arXiv cs.NI 2007
Year: 2007

We develop distributed algorithms to allocate resources in multi-hop wireless networks with the aim of minimizing total cost. In order to observe the fundamental duplexing constraint that co-located transmitters and receivers cannot operate simultaneously on the same frequency band, we first devise a spectrum allocation scheme that divides the whole spectrum into multiple sub-bands and activates conflict-free links on each sub-band. We show that the minimum number of required sub-bands grows asymptotically at a logarithmic rate with the chromatic number of network connectivity graph. A simple distributed and asynchronous algorithm is developed to feasibly activate links on the available sub-bands. Given a feasible spectrum allocation, we then design node-based distributed algorithms for optimally controlling the transmission powers on active links for each sub-band, jointly with traffic routes and user input rates in response to channel states and traffic demands. We show that under specified conditions, the algorithms asymptotically converge to the optimal operating point.
Stochastic Optimization Algorithms
Venue: arXiv cs.NE 2007
Year: 2007

When looking for a solution, deterministic methods have the enormous advantage that they do find global optima. Unfortunately, they are very CPU-intensive, and are useless on untractable NP-hard problems that would require thousands of years for cutting-edge computers to explore. In order to get a result, one needs to revert to stochastic algorithms, that sample the search space without exploring it thoroughly. Such algorithms can find very good results, without any guarantee that the global optimum has been reached; but there is often no other choice than using them. This chapter is a short introduction to the main methods used in stochastic optimization.
Ensemble Learning for Free with Evolutionary Algorithms ?
Venue: arXiv cs.AI 2007
Year: 2007

Evolutionary Learning proceeds by evolving a population of classifiers, from which it generally returns (with some notable exceptions) the single best-of-run classifier as final result. In the meanwhile, Ensemble Learning, one of the most efficient approaches in supervised Machine Learning for the last decade, proceeds by building a population of diverse classifiers. Ensemble Learning with Evolutionary Computation thus receives increasing attention. The Evolutionary Ensemble Learning (EEL) approach presented in this paper features two contributions. First, a new fitness function, inspired by co-evolution and enforcing the classifier diversity, is presented. Further, a new selection criterion based on the classification margin is proposed. This criterion is used to extract the classifier ensemble from the final population only (Off-line) or incrementally along evolution (On-line). Experiments on a set of benchmark problems show that Off-line outperforms single-hypothesis evolutionary learning and state-of-art Boosting and generates smaller classifier ensembles.
Reliable Memories Built from Unreliable Components Based on Expander Graphs
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, memories built from components subject to transient faults are considered. A fault-tolerant memory architecture based on low-density parity-check codes is proposed and the existence of reliable memories for the adversarial failure model is proved. The proof relies on the expansion property of the underlying Tanner graph of the code. An equivalence between the Taylor-Kuznetsov (TK) scheme and Gallager B algorithm is established and the results are extended to the independent failure model. It is also shown that the proposed memory architecture has lower redundancy compared to the TK scheme. The results are illustrated with specific numerical examples.
On the Low-SNR Capacity of Phase-Shift Keying with Hard-Decision Detection
Venue: arXiv cs.IT 2007
Year: 2007

The low-snr capacity of M-ary PSK transmission over both the additive white Gaussian noise (AWGN) and fading channels is analyzed when hard-decision detection is employed at the receiver. Closed-form expressions for the first and second derivatives of the capacity at zero snr are obtained. The spectral-efficiency/bit-energy tradeoff in the low-snr regime is analyzed by finding the wideband slope and the bit energy required at zero spectral efficiency. Practical design guidelines are drawn from the information-theoretic analysis. The fading channel analysis is conducted for both coherent and noncoherent cases, and the performance penalty in the low-power regime for not knowing the channel is identified.
Fault Classification in Cylinders Using Multilayer Perceptrons, Support Vector Machines and Guassian Mixture Models
Venue: arXiv cs.AI 2007
Year: 2007

Gaussian mixture models (GMM) and support vector machines (SVM) are introduced to classify faults in a population of cylindrical shells. The proposed procedures are tested on a population of 20 cylindrical shells and their performance is compared to the procedure, which uses multi-layer perceptrons (MLP). The modal properties extracted from vibration data are used to train the GMM, SVM and MLP. It is observed that the GMM produces 98%, SVM produces 94% classification accuracy while the MLP produces 88% classification rates.
The Parameter-Less Self-Organizing Map algorithm
Venue: arXiv cs.NE 2007
Year: 2007

The Parameter-Less Self-Organizing Map (PLSOM) is a new neural network algorithm based on the Self-Organizing Map (SOM). It eliminates the need for a learning rate and annealing schemes for learning rate and neighbourhood size. We discuss the relative performance of the PLSOM and the SOM and demonstrate some tasks in which the SOM fails but the PLSOM performs satisfactory. Finally we discuss some example applications of the PLSOM and present a proof of ordering under certain limited conditions.
Batch Processor Sharing with Hyper-Exponential Service Time
Venue: arXiv cs.NI 2007
Year: 2007

We study Batch Processor-Sharing (BPS) queuing model with hyper-exponential service time distribution and Poisson batch arrival process. One of the main goals to study BPS is the possibility of its application in size-based scheduling, which is used in differentiation between Short and Long flows in the Internet. In the case of hyper-exponential service time distribution we find an analytical expression of the expected conditional response time for the BPS queue. We show, that the expected conditional response time is a concave function of the service time. We apply the received results to the Two Level Processor-Sharing (TLPS) model with hyper-exponential service time distribution and find the expression of the expected response time for the TLPS model. TLPS scheduling discipline can be applied to size-based differentiation in TCP/IP networks and Web server request handling.
Learning to Bluff
Venue: arXiv cs.AI 2007
Year: 2007

The act of bluffing confounds game designers to this day. The very nature of bluffing is even open for debate, adding further complication to the process of creating intelligent virtual players that can bluff, and hence play, realistically. Through the use of intelligent, learning agents, and carefully designed agent outlooks, an agent can in fact learn to predict its opponents reactions based not only on its own cards, but on the actions of those around it. With this wider scope of understanding, an agent can in learn to bluff its opponents, with the action representing not an illogical action, as bluffing is often viewed, but rather as an act of maximising returns through an effective statistical optimisation. By using a tee dee lambda learning algorithm to continuously adapt neural network agent intelligence, agents have been shown to be able to learn to bluff without outside prompting, and even to learn to call each others bluffs in free, competitive play.