OpenRaiser/Intern-Atlas huggingface dataset:
Pure Saddle Points and Symmetric Relative Payoff Games
Venue: arXiv cs.GT 2010
Year: 2010

It is well known that the rock-paper-scissors game has no pure saddle point. We show that this holds more generally: A symmetric two-player zero-sum game has a pure saddle point if and only if it is not a generalized rock-paper-scissors game. Moreover, we show that every finite symmetric quasiconcave two-player zero-sum game has a pure saddle point. Further sufficient conditions for existence are provided. We apply our theory to a rich collection of examples by noting that the class of symmetric two-player zero-sum games coincides with the class of relative payoff games associated with symmetric two-player games. This allows us to derive results on the existence of a finite population evolutionary stable strategies.
Bottleneck Routing Games with Low Price of Anarchy
Venue: arXiv cs.GT 2010
Year: 2010

We study {\em bottleneck routing games} where the social cost is determined by the worst congestion on any edge in the network. In the literature, bottleneck games assume player utility costs determined by the worst congested edge in their paths. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high and proportional to the size of the network. In order to obtain smaller price of anarchy we introduce {\em exponential bottleneck games} where the utility costs of the players are exponential functions of their congestions. We find that exponential bottleneck games are very efficient and give a poly-log bound on the price of anarchy: $O(\log L \cdot \log |E|)$, where $L$ is the largest path length in the players' strategy sets and $E$ is the set of edges in the graph. By adjusting the exponential utility costs with a logarithm we obtain games whose player costs are almost identical to those in regular bottleneck games, and at the same time have the good price of anarchy of exponential games.
Closed-Form Expressions for Secrecy Capacity over Correlated Rayleigh Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

We investigate the secure communications over correlated wiretap Rayleigh fading channels assuming the full channel state information (CSI) available. Based on the information theoretic formulation, we derive closed-form expressions for the average secrecy capacity and the outage probability. Simulation results confirm our analytical expressions.
A Modal Logic for Termgraph Rewriting
Venue: arXiv cs.LO 2010
Year: 2010

We propose a modal logic tailored to describe graph transformations and discuss some of its properties. We focus on a particular class of graphs called termgraphs. They are first-order terms augmented with sharing and cycles. Termgraphs allow one to describe classical data-structures (possibly with pointers) such as doubly-linked lists, circular lists etc. We show how the proposed logic can faithfully describe (i) termgraphs as well as (ii) the application of a termgraph rewrite rule (i.e. matching and replacement) and (iii) the computation of normal forms with respect to a given rewrite system. We also show how the proposed logic, which is more expressive than propositional dynamic logic, can be used to specify shapes of classical data-structures (e.g. binary trees, circular lists etc.).
Enumeration of Hamiltonian Cycles in 6-cube
Venue: arXiv cs.DM 2010
Year: 2010

Finding the number 2H6 of directed Hamiltonian cycles in 6-cube is problem 43 in Section 7.2.1.1 of Knuth's ' The Art of Computer Programming'; various proposed estimates are surveyed below. We computed exact value: H6=14,754,666,508,334,433,250,560=6*2^4*217,199*1,085,989*5,429,923. Also the number Aut6 of those cycles up to automorphisms of 6-cube was computed as 147,365,405,634,413,085
Linear tail-biting trellises: Characteristic generators and the BCJR-construction
Venue: arXiv cs.IT 2010
Year: 2010

We investigate the constructions of tail-biting trellises for linear block codes introduced by Koetter/Vardy (2003) and Nori/Shankar (2006). For a given code we will define the sets of characteristic generators more generally than by Koetter/Vardy and we will investigate how the choice of characteristic generators affects the set of resulting product trellises, called KV-trellises. Furthermore, we will show that each KV-trellis is a BCJR-trellis, defined in a slightly stronger sense than by Nori/Shankar, and that the latter are always non-mergeable. Finally, we will address a duality conjecture of Koetter/Vardy by making use of a dualization technique of BCJR-trellises and prove the conjecture for minimal trellises.
A Review of Error Estimation in Adaptive Quadrature
Venue: arXiv cs.NA 2010
Year: 2010

The most critical component of any adaptive numerical quadrature routine is the estimation of the integration error. Since the publication of the first algorithms in the 1960s, many error estimation schemes have been presented, evaluated and discussed. This paper presents a review of existing error estimation techniques and discusses their differences and their common features. Some common shortcomings of these algorithms are discussed and a new general error estimation technique is presented.
A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates the uniqueness of a nonnegative vector solution and the uniqueness of a positive semidefinite matrix solution to underdetermined linear systems. A vector solution is the unique solution to an underdetermined linear system only if the measurement matrix has a row-span intersecting the positive orthant. Focusing on two types of binary measurement matrices, Bernoulli 0-1 matrices and adjacency matrices of general expander graphs, we show that, in both cases, the support size of a unique nonnegative solution can grow linearly, namely O(n), with the problem dimension n. We also provide closed-form characterizations of the ratio of this support size to the signal dimension. For the matrix case, we show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. We further show that a randomly generated Gaussian linear compressed observations operator will satisfy this condition with overwhelmingly high probability.
Large Margin Boltzmann Machines and Large Margin Sigmoid Belief Networks
Venue: arXiv cs.LG 2010
Year: 2010

Current statistical models for structured prediction make simplifying assumptions about the underlying output graph structure, such as assuming a low-order Markov chain, because exact inference becomes intractable as the tree-width of the underlying graph increases. Approximate inference algorithms, on the other hand, force one to trade off representational power with computational efficiency. In this paper, we propose two new types of probabilistic graphical models, large margin Boltzmann machines (LMBMs) and large margin sigmoid belief networks (LMSBNs), for structured prediction. LMSBNs in particular allow a very fast inference algorithm for arbitrary graph structures that runs in polynomial time with a high probability. This probability is data-distribution dependent and is maximized in learning. The new approach overcomes the representation-efficiency trade-off in previous models and allows fast structured prediction with complicated graph structures. We present results from applying a fully connected model to multi-label scene classification and demonstrate that the proposed approach can yield significant performance gains over current state-of-the-art methods.
A framework for designing concurrent and recoverable abstract data types based on commutativity
Venue: arXiv cs.DB 2010
Year: 2010

In this paper, we try to focus the reader's interest on the problems that transactional systems have to resolve for taking advantage of commutativity in a serializable and recoverable way. Our framework is, (as others), based on the use of conditional commutativity on abstract date types. We present new features that have not been found in the literature hitherto, that both increase concurrency and simplify recovery.
Ball on a beam: stabilization under saturated input control with large basin of attraction
Venue: arXiv cs.RO 2010
Year: 2010

This article is devoted to the stabilization of two underactuated planar systems, the well-known straight beam-and-ball system and an original circular beam-and-ball system. The feedback control for each system is designed, using the Jordan form of its model, linearized near the unstable equilibrium. The limits on the voltage, fed to the motor, are taken into account explicitly. The straight beam-and-ball system has one unstable mode in the motion near the equilibrium point. The proposed control law ensures that the basin of attraction coincides with the controllability domain. The circular beam-and-ball system has two unstable modes near the equilibrium point. Therefore, this device, never considered in the past, is much more difficult to control than the straight beam-and-ball system. The main contribution is to propose a simple new control law, which ensures by adjusting its gain parameters that the basin of attraction arbitrarily can approach the controllability domain for the linear case. For both nonlinear systems, simulation results are presented to illustrate the efficiency of the designed nonlinear control laws and to determine the basin of attraction.
On the maximal sum of exponents of runs in a string
Venue: arXiv cs.DM 2010
Year: 2010

A run is an inclusion maximal occurrence in a string (as a subinterval) of a repetition $v$ with a period $p$ such that $2p \le |v|$. The exponent of a run is defined as $|v|/p$ and is $\ge 2$. We show new bounds on the maximal sum of exponents of runs in a string of length $n$. Our upper bound of $4.1n$ is better than the best previously known proven bound of $5.6n$ by Crochemore & Ilie (2008). The lower bound of $2.035n$, obtained using a family of binary words, contradicts the conjecture of Kolpakov & Kucherov (1999) that the maximal sum of exponents of runs in a string of length $n$ is smaller than $2n$
Les entités spatiales dans la langue : étude descriptive, formelle et expérimentale de la catégorisation
Venue: arXiv cs.CL 2010
Year: 2010

While previous linguistic and psycholinguistic research on space has mainly analyzed spatial relations, the studies reported in this paper focus on how language distinguishes among spatial entities. Descriptive and experimental studies first propose a classification of entities, which accounts for both static and dynamic space, has some cross-linguistic validity, and underlies adults' cognitive processing. Formal and computational analyses then introduce theoretical elements aiming at modelling these categories, while fulfilling various properties of formal ontologies (generality, parsimony, coherence...). This formal framework accounts, in particular, for functional dependences among entities underlying some part-whole descriptions. Finally, developmental research shows that language-specific properties have a clear impact on how children talk about space. The results suggest some cross-linguistic variability in children's spatial representations from an early age onwards, bringing into question models in which general cognitive capacities are the only determinants of spatial cognition during the course of development.
On the stability of flow-aware CSMA
Venue: arXiv cs.PF 2010
Year: 2010

We consider a wireless network where each flow (instead of each link) runs its own CSMA (Carrier Sense Multiple Access) algorithm. Specifically, each flow attempts to access the radio channel after some random time and transmits a packet if the channel is sensed idle. We prove that, unlike the standard CSMA algorithm, this simple distributed access scheme is optimal in the sense that the network is stable for all traffic intensities in the capacity region of the network.
Improving Waiting Time of Tasks Scheduled Under Preemptive Round Robin Using Changeable Time Quantum
Venue: arXiv cs.DC 2010
Year: 2010

Minimizing waiting time for tasks waiting in the queue for execution is one of the important scheduling cri-teria which took a wide area in scheduling preemptive tasks. In this paper we present Changeable Time Quan-tum (CTQ) approach combined with the round-robin algorithm, we try to adjust the time quantum according to the burst times of the tasks in the ready queue. There are two important benefits of using (CTQ) approach: minimizing the average waiting time of the tasks, consequently minimizing the average turnaround time, and keeping the number of context switches as low as possible, consequently minimizing the scheduling overhead. In this paper, we consider the scheduling problem for preemptive tasks, where the time costs of these tasks are known a priori. Our experimental results demonstrate that CTQ can provide much lower scheduling overhead and better scheduling criteria.
An Improved Algorithm for Generating Database Transactions from Relational Algebra Specifications
Venue: arXiv cs.DB 2010
Year: 2010

Alloy is a lightweight modeling formalism based on relational algebra. In prior work with Fisler, Giannakopoulos, Krishnamurthi, and Yoo, we have presented a tool, Alchemy, that compiles Alloy specifications into implementations that execute against persistent databases. The foundation of Alchemy is an algorithm for rewriting relational algebra formulas into code for database transactions. In this paper we report on recent progress in improving the robustness and efficiency of this transformation.
Disabling equational theories in unification for cryptographic protocol analysis through tagging
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we show a new tagging scheme for cryptographic protocol messages. Under this tagging, equational theories of operators such as exclusive-or, binary addition etc. are effectively disabled, when terms are unified. We believe that this result has a significant impact on protocol analysis and security, since unification is at the heart of symbolic protocol analysis. Hence, disabling equational theories in unification implies disabling them altogether in protocol analysis for most operators and theories.
A Note on Integer Factorization Using Lattices
Venue: arXiv cs.DS 2010
Year: 2010

We revisit Schnorr's lattice-based integer factorization algorithm, now with an effective point of view. We present effective versions of Theorem 2 of Schnorr's "Factoring integers and computing discrete logarithms via diophantine approximation" paper, as well as new elementary properties of the Prime Number Lattice bases of Schnorr and Adleman.
Angle Tree: Nearest Neighbor Search in High Dimensions with Low Intrinsic Dimensionality
Venue: arXiv cs.DS 2010
Year: 2010

We propose an extension of tree-based space-partitioning indexing structures for data with low intrinsic dimensionality embedded in a high dimensional space. We call this extension an Angle Tree. Our extension can be applied to both classical kd-trees as well as the more recent rp-trees. The key idea of our approach is to store the angle (the "dihedral angle") between the data region (which is a low dimensional manifold) and the random hyperplane that splits the region (the "splitter"). We show that the dihedral angle can be used to obtain a tight lower bound on the distance between the query point and any point on the opposite side of the splitter. This in turn can be used to efficiently prune the search space. We introduce a novel randomized strategy to efficiently calculate the dihedral angle with a high degree of accuracy. Experiments and analysis on real and synthetic data sets shows that the Angle Tree is the most efficient known indexing structure for nearest neighbor queries in terms of preprocessing and space usage while achieving high accuracy and fast search time.
Competition with Dynamic Spectrum Leasing
Venue: arXiv cs.NI 2010
Year: 2010

This paper presents a comprehensive analytical study of two competitive cognitive operators' spectrum leasing and pricing strategies, taking into account operators' heterogeneity in leasing costs and users' heterogeneity in transmission power and channel conditions. We model the interactions between operators and users as a three-stage dynamic game, where operators make simultaneous spectrum leasing and pricing decisions in Stages I and II, and users make purchase decisions in Stage III. Using backward induction, we are able to completely characterize the game's equilibria. We show that both operators make the equilibrium leasing and pricing decisions based on simple threshold policies. Moreover, two operators always choose the same equilibrium price despite their difference in leasing costs. Each user receives the same signal-to-noise-ratio (SNR) at the equilibrium, and the obtained payoff is linear in its transmission power and channel gain. We also compare the duopoly equilibrium with the coordinated case where two operators cooperate to maximize their total profit. We show that the maximum loss of total profit due to operators' competition is no larger than 25%. The users, however, always benefit from operators' competition in terms of their payoffs. We show that most of these insights are robust in the general SNR regime.
On Linear Information Systems
Venue: arXiv cs.LO 2010
Year: 2010

Scott's information systems provide a categorically equivalent, intensional description of Scott domains and continuous functions. Following a well established pattern in denotational semantics, we define a linear version of information systems, providing a model of intuitionistic linear logic (a new-Seely category), with a "set-theoretic" interpretation of exponentials that recovers Scott continuous functions via the co-Kleisli construction. From a domain theoretic point of view, linear information systems are equivalent to prime algebraic Scott domains, which in turn generalize prime algebraic lattices, already known to provide a model of classical linear logic.
Flexible Authentication Technique for Ubiquitous Wireless Communication using Passport and Visa Tokens
Venue: arXiv cs.NI 2010
Year: 2010

The development of mobile devices (CPU, memory, and storage) and the introduction of mobile networks (Ad-Hoc, Wi-Fi, WiMAX, and 3.5G) have opened new opportunities for next generation of mobile services. It becomes more convenience and desirable for mobile internet users to be connected everywhere. However, ubiquitous mobile access connectivity faces interoperation issues between wireless network providers and wireless network technologies. Although mobile users would like to get as many services as possible while they travel, there is a lack of technology to identify visited users in current foreign network authentication systems. This challenge lies in the fact that a foreign network provider does not initially have the authentication credentials of a mobile user. Existing approaches use roaming agreement to exchange authentication information between home network and foreign network. This paper proposes a roaming agreement-less approach designed based on our ubiquitous mobile access model. Our approach consist of two tokens, Passport (identification token) and Visa (authorisation token) to provide the mobile user with a flexible authentication method to access foreign network services. The security analysis indicates that our proposal is more suitable for ubiquitous mobile communication especially in roaming agreement-less environment.
Spoken Language Identification Using Hybrid Feature Extraction Methods
Venue: arXiv cs.SD 2010
Year: 2010

This paper introduces and motivates the use of hybrid robust feature extraction technique for spoken language identification (LID) system. The speech recognizers use a parametric form of a signal to get the most important distinguishable features of speech signal for recognition task. In this paper Mel-frequency cepstral coefficients (MFCC), Perceptual linear prediction coefficients (PLP) along with two hybrid features are used for language Identification. Two hybrid features, Bark Frequency Cepstral Coefficients (BFCC) and Revised Perceptual Linear Prediction Coefficients (RPLP) were obtained from combination of MFCC and PLP. Two different classifiers, Vector Quantization (VQ) with Dynamic Time Warping (DTW) and Gaussian Mixture Model (GMM) were used for classification. The experiment shows better identification rate using hybrid feature extraction techniques compared to conventional feature extraction methods.BFCC has shown better performance than MFCC with both classifiers. RPLP along with GMM has shown best identification performance among all feature extraction techniques.
A Mobile Message Scheduling and Delivery System using m-Learning framework
Venue: arXiv cs.OH 2010
Year: 2010

Wireless data communications in form of Short Message Service (SMS) and Wireless Access Protocols (WAP) browsers have gained global popularity, yet, not much has been done to extend the usage of these devices in electronic learning (e-learning) and information sharing. This project explores the extension of e learning into wireless/ handheld (W/H) computing devices with the help of a mobile learning (m-learning) framework. This framework provides the requirements to develop m-learning application that can be used to share academic and administrative information among people within the university campus. A prototype application has been developed to demonstrate the important functionality of the proposed system in simulated environment. This system is supposed to work both in bulk SMS and interactive SMS delivery mode. Here we have combined both Short Message Service (SMS) and Wireless Access Protocols (WAP) browsers. SMS is used for Short and in time information delivery and WAP is used for detailed information delivery like course content, training material, interactive evolution tests etc. The push model is used for sending personalized multicasting messages to a group of mobile users with a common profile thereby improving the effectiveness and usefulness of the cntent delivered. Again pull mechanism can be applied for sending information as SMS when requested by end user in interactive SMS delivery mode. The main strength of the system is that, the actual SMS delivery application can be hosted on a mobile device, which can operate even when the device is on move.
BitTorrent Experiments on Testbeds: A Study of the Impact of Network Latencies
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we study the impact of network latency on the time required to download a file distributed using BitTorrent. This study is essential to understand if testbeds can be used for experimental evaluation of BitTorrent. We observe that the network latency has a marginal impact on the time required to download a file; hence, BitTorrent experiments can performed on testbeds.
Etiqueter un corpus oral par apprentissage automatique à l'aide de connaissances linguistiques
Venue: arXiv cs.LG 2010
Year: 2010

Thanks to the Eslo1 ("Enquête sociolinguistique d'Orléans", i.e. "Sociolinguistic Inquiery of Orléans") campain, a large oral corpus has been gathered and transcribed in a textual format. The purpose of the work presented here is to associate a morpho-syntactic label to each unit of this corpus. To this aim, we have first studied the specificities of the necessary labels, and their various possible levels of description. This study has led to a new original hierarchical structuration of labels. Then, considering that our new set of labels was different from the one used in every available software, and that these softwares usually do not fit for oral data, we have built a new labeling tool by a Machine Learning approach, from data labeled by Cordial and corrected by hand. We have applied linear CRF (Conditional Random Fields) trying to take the best possible advantage of the linguistic knowledge that was used to define the set of labels. We obtain an accuracy between 85 and 90%, depending of the parameters used.