OpenRaiser/Intern-Atlas huggingface dataset:
Capacity constraints and the inevitability of mediators in adword auctions
Venue: arXiv cs.GT 2007
Year: 2007

One natural constraint in the sponsored search advertising framework arises from the fact that there is a limit on the number of available slots, especially for the popular keywords, and as a result, a significant pool of advertisers are left out. We study the emergence of diversification in the adword market triggered by such capacity constraints in the sense that new market mechanisms, as well as, new for-profit agents are likely to emerge to combat or to make profit from the opportunities created by shortages in ad-space inventory. We propose a model where the additional capacity is provided by for-profit agents (or, mediators), who compete for slots in the original auction, draw traffic, and run their own sub-auctions. The quality of the additional capacity provided by a mediator is measured by its {\it fitness} factor. We compute revenues and payoffs for all the different parties at a {\it symmetric Nash equilibrium} (SNE) when the mediator-based model is operated by a mechanism currently being used by Google and Yahoo!, and then compare these numbers with those obtained at a corresponding SNE for the same mechanism, but without any mediators involved in the auctions. Such calculations allow us to determine the value of the additional capacity. Our results show that the revenue of the auctioneer, as well as the social value (i.e. efficiency), always increase when mediators are involved; moreover even the payoffs of {\em all} the bidders will increase if the mediator has a high enough fitness. Thus, our analysis indicates that there are significant opportunities for diversification in the internet economy and we should expect it to continue to develop richer structure, with room for different types of agents and mechanisms to coexist.
An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation
Venue: arXiv cs.DB 2007
Year: 2007

Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting a sequence in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem using the l_inf norm, and we present an optimal linear time algorithm based on novel formalism. Moreover, given a precomputation in time O(n log n) consisting of a labeling of all extrema, we compute any optimal segmentation in constant time. We compare experimentally its performance to two piecewise linear segmentation heuristics (top-down and bottom-up). We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.
An efficient algorithm finds noticeable trends and examples concerning the Černy conjecture
Venue: arXiv cs.DM 2007
Year: 2007

A word w is called synchronizing (recurrent, reset, directed) word of a deterministic finite automaton (DFA) if w sends all states of the automaton on a unique state. Jan Cerny had found in 1964 a sequence of n-state complete DFA with shortest synchronizing word of length (n-1)^2. He had conjectured that it is an upper bound for the length of the shortest synchronizing word for any $n$-state complete DFA. The examples of DFA with shortest synchronizing word of length (n-1)^2 are relatively rare. To the Cerny sequence were added in all examples of Cerny, Piricka and Rosenauerova (1971), of Kari (2001) and of Roman (2004). By help of a program based on some effective algorithms, a wide class of automata of size less than 11 was checked. The order of the algorithm finding synchronizing word is quadratic for overwhelming majority of known to date automata. Some new examples of n-state DFA with minimal synchronizing word of length (n-1)^2 were discovered. The program recognized some remarkable trends concerning the length of the minimal synchronizing word. http://www.cs.biu.ac.il/~trakht/Testas.html
Information-theoretic analysis of MIMO channel sounding
Venue: arXiv cs.IT 2007
Year: 2007

The large majority of commercially available multiple-input multiple-output (MIMO) radio channel measurement devices (sounders) is based on time-division multiplexed switching (TDMS) of a single transmit/receive radio-frequency chain into the elements of a transmit/receive antenna array. While being cost-effective, such a solution can cause significant measurement errors due to phase noise and frequency offset in the local oscillators. In this paper, we systematically analyze the resulting errors and show that, in practice, overestimation of channel capacity by several hundred percent can occur. Overestimation is caused by phase noise (and to a lesser extent frequency offset) leading to an increase of the MIMO channel rank. Our analysis furthermore reveals that the impact of phase errors is, in general, most pronounced if the physical channel has low rank (typical for line-of-sight or poor scattering scenarios). The extreme case of a rank-1 physical channel is analyzed in detail. Finally, we present measurement results obtained from a commercially employed TDMS-based MIMO channel sounder. In the light of the findings of this paper, the results obtained through MIMO channel measurement campaigns using TDMS-based channel sounders should be interpreted with great care.
Unfolding Restricted Convex Caps
Venue: arXiv cs.CG 2007
Year: 2007

This paper details an algorithm for unfolding a class of convex polyhedra, where each polyhedron in the class consists of a convex cap over a rectangular base, with several restrictions: the cap's faces are quadrilaterals, with vertices over an underlying integer lattice, and such that the cap convexity is ``radially monotone,'' a type of smoothness constraint. Extensions of Cauchy's arm lemma are used in the proof of non-overlap.
Enrichment of Qualitative Beliefs for Reasoning under Uncertainty
Venue: arXiv cs.AI 2007
Year: 2007

This paper deals with enriched qualitative belief functions for reasoning under uncertainty and for combining information expressed in natural language through linguistic labels. In this work, two possible enrichments (quantitative and/or qualitative) of linguistic labels are considered and operators (addition, multiplication, division, etc) for dealing with them are proposed and explained. We denote them $qe$-operators, $qe$ standing for "qualitative-enriched" operators. These operators can be seen as a direct extension of the classical qualitative operators ($q$-operators) proposed recently in the Dezert-Smarandache Theory of plausible and paradoxist reasoning (DSmT). $q$-operators are also justified in details in this paper. The quantitative enrichment of linguistic label is a numerical supporting degree in $[0,\infty)$, while the qualitative enrichment takes its values in a finite ordered set of linguistic values. Quantitative enrichment is less precise than qualitative enrichment, but it is expected more close with what human experts can easily provide when expressing linguistic labels with supporting degrees. Two simple examples are given to show how the fusion of qualitative-enriched belief assignments can be done.
A Simple Characterization of Strategic Behaviors in Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we consider the problem of resource allocation among two competing users sharing a binary symmetric broadcast channel. We model the interaction between autonomous selfish users in the resource allocation and analyze their strategic behavior in manipulating the allocation outcome. We analytically show that users will improve their performance (i.e. gain higher allocated rates) if they have more information about the strategy of the competing user.
Learning for Dynamic Bidding in Cognitive Radio Resources
Venue: arXiv cs.LG 2007
Year: 2007

In this paper, we model the various wireless users in a cognitive radio network as a collection of selfish, autonomous agents that strategically interact in order to acquire the dynamically available spectrum opportunities. Our main focus is on developing solutions for wireless users to successfully compete with each other for the limited and time-varying spectrum opportunities, given the experienced dynamics in the wireless network. We categorize these dynamics into two types: one is the disturbance due to the environment (e.g. wireless channel conditions, source traffic characteristics, etc.) and the other is the impact caused by competing users. To analyze the interactions among users given the environment disturbance, we propose a general stochastic framework for modeling how the competition among users for spectrum opportunities evolves over time. At each stage of the dynamic resource allocation, a central spectrum moderator auctions the available resources and the users strategically bid for the required resources. The joint bid actions affect the resource allocation and hence, the rewards and future strategies of all users. Based on the observed resource allocation and corresponding rewards from previous allocations, we propose a best response learning algorithm that can be deployed by wireless users to improve their bidding policy at each stage. The simulation results show that by deploying the proposed best response learning algorithm, the wireless users can significantly improve their own performance in terms of both the packet loss rate and the incurred cost for the used resources.
Pricing, Competition, and Routing for Selfish and Strategic Nodes in Multi-hop Relay Networks
Venue: arXiv cs.GT 2007
Year: 2007

We study a pricing game in multi-hop relay networks where nodes price their services and route their traffic selfishly and strategically. In this game, each node (1) announces pricing functions which specify the payments it demands from its respective customers depending on the amount of traffic they route to it and (2) allocates the total traffic it receives to its service providers. The profit of a node is the difference between the revenue earned from servicing others and the cost of using others' services. We show that the socially optimal routing of such a game can always be induced by an equilibrium where no node can increase its profit by unilaterally changing its pricing functions or routing decision. On the other hand, there may also exist inefficient equilibria. We characterize the loss of efficiency by deriving the price of anarchy at inefficient equilibria. We show that the price of anarchy is finite for oligopolies with concave marginal cost functions, while it is infinite for general topologies and cost functions.
LDPC codes from Singer cycles
Venue: arXiv cs.IT 2007
Year: 2007

The main goal of coding theory is to devise efficient systems to exploit the full capacity of a communication channel, thus achieving an arbitrarily small error probability. Low Density Parity Check (LDPC) codes are a family of block codes--characterised by admitting a sparse parity check matrix--with good correction capabilities. In the present paper the orbits of subspaces of a finite projective space under the action of a Singer cycle are investigated.
Distributed Space Time Codes with Low Decoding Complexity for Asynchronous Relay Networks
Venue: arXiv cs.IT 2007
Year: 2007

Recently Li and Xia have proposed a transmission scheme for wireless relay networks based on the Alamouti space time code and orthogonal frequency division multiplexing to combat the effect of timing errors at the relay nodes. This transmission scheme is amazingly simple and achieves a diversity order of two for any number of relays. Motivated by its simplicity, this scheme is extended to a more general transmission scheme that can achieve full cooperative diversity for any number of relays. The conditions on the distributed space time code (DSTC) structure that admit its application in the proposed transmission scheme are identified and it is pointed out that the recently proposed full diversity four group decodable DSTCs from precoded co-ordinate interleaved orthogonal designs and extended Clifford algebras satisfy these conditions. It is then shown how differential encoding at the source can be combined with the proposed transmission scheme to arrive at a new transmission scheme that can achieve full cooperative diversity in asynchronous wireless relay networks with no channel information and also no timing error knowledge at the destination node. Finally, four group decodable distributed differential space time codes applicable in this new transmission scheme for power of two number of relays are also provided.
Fast Selection of Spectral Variables with B-Spline Compression
Venue: arXiv cs.LG 2007
Year: 2007

The large number of spectral variables in most data sets encountered in spectral chemometrics often renders the prediction of a dependent variable uneasy. The number of variables hopefully can be reduced, by using either projection techniques or selection methods; the latter allow for the interpretation of the selected variables. Since the optimal approach of testing all possible subsets of variables with the prediction model is intractable, an incremental selection approach using a nonparametric statistics is a good option, as it avoids the computationally intensive use of the model itself. It has two drawbacks however: the number of groups of variables to test is still huge, and colinearities can make the results unstable. To overcome these limitations, this paper presents a method to select groups of spectral variables. It consists in a forward-backward procedure applied to the coefficients of a B-Spline representation of the spectra. The criterion used in the forward-backward procedure is the mutual information, allowing to find nonlinear dependencies between variables, on the contrary of the generally used correlation. The spline representation is used to get interpretability of the results, as groups of consecutive spectral variables will be selected. The experiments conducted on NIR spectra from fescue grass and diesel fuels show that the method provides clearly identified groups of selected variables, making interpretation easy, while keeping a low computational load. The prediction performances obtained using the selected coefficients are higher than those obtained by the same method applied directly to the original variables and similar to those obtained using traditional models, although using significantly less spectral variables.
Functional Multi-Layer Perceptron: a Nonlinear Tool for Functional Data Analysis
Venue: arXiv cs.NE 2007
Year: 2007

In this paper, we study a natural extension of Multi-Layer Perceptrons (MLP) to functional inputs. We show that fundamental results for classical MLP can be extended to functional MLP. We obtain universal approximation results that show the expressive power of functional MLP is comparable to that of numerical MLP. We obtain consistency results which imply that the estimation of optimal parameters for functional MLP is statistically well defined. We finally show on simulated and real world data that the proposed model performs in a very satisfactory way.
Research Paper on Transaction-Oriented Simulation In Ad Hoc Grids
Venue: arXiv cs.DC 2007
Year: 2007

This paper analyses the requirements of performing parallel transaction-oriented simulations with a special focus on the space-parallel approach and discrete event simulation synchronisation algorithms that are suitable for transaction-oriented simulation and the target environment of Ad Hoc Grids. To demonstrate the findings a Java-based parallel transaction-oriented simulator for the simulation language GPSS/H is implemented on the basis of the most promising Shock Resistant Time Warp synchronisation algorithm and using the Grid framework ProActive. The validation of this parallel simulator shows that the Shock Resistant Time Warp algorithm can successfully reduce the number of rolled back Transaction moves but it also reveals circumstances in which the Shock Resistant Time Warp algorithm can be outperformed by the normal Time Warp algorithm. The conclusion of this paper suggests possible improvements to the Shock Resistant Time Warp algorithm to avoid such problems.
Evolving Classifiers: Methods for Incremental Learning
Venue: arXiv cs.LG 2007
Year: 2007

The ability of a classifier to take on new information and classes by evolving the classifier without it having to be fully retrained is known as incremental learning. Incremental learning has been successfully applied to many classification problems, where the data is changing and is not all available at once. In this paper there is a comparison between Learn++, which is one of the most recent incremental learning algorithms, and the new proposed method of Incremental Learning Using Genetic Algorithm (ILUGA). Learn++ has shown good incremental learning capabilities on benchmark datasets on which the new ILUGA method has been tested. ILUGA has also shown good incremental learning ability using only a few classifiers and does not suffer from catastrophic forgetting. The results obtained for ILUGA on the Optical Character Recognition (OCR) and Wine datasets are good, with an overall accuracy of 93% and 94% respectively showing a 4% improvement over Learn++.MT for the difficult multi-class OCR dataset.
Set Matrices and The Path/Cycle Problem
Venue: arXiv cs.DM 2007
Year: 2007

Presentation of set matrices and demonstration of their efficiency as a tool using the path/cycle problem.
Comparing Maintenance Strategies for Overlays
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we present an analytical tool for understanding the performance of structured overlay networks under churn based on the master-equation approach of physics. We motivate and derive an equation for the average number of hops taken by lookups during churn, for the Chord network. We analyse this equation in detail to understand the behaviour with and without churn. We then use this understanding to predict how lookups will scale for varying peer population as well as varying the sizes of the routing tables. We then consider a change in the maintenance algorithm of the overlay, from periodic stabilisation to a reactive one which corrects fingers only when a change is detected. We generalise our earlier analysis to underdstand how the reactive strategy compares with the periodic one.
Colour image segmentation by the vector-valued Allen-Cahn phase-field model: a multigrid solution
Venue: arXiv cs.CV 2007
Year: 2007

We propose a new method for the numerical solution of a PDE-driven model for colour image segmentation and give numerical examples of the results. The method combines the vector-valued Allen-Cahn phase field equation with initial data fitting terms. This method is known to be closely related to the Mumford-Shah problem and the level set segmentation by Chan and Vese. Our numerical solution is performed using a multigrid splitting of a finite element space, thereby producing an efficient and robust method for the segmentation of large images.
Band Unfoldings and Prismatoids: A Counterexample
Venue: arXiv cs.CG 2007
Year: 2007

This note shows that the hope expressed in [ADL+07]--that the new algorithm for edge-unfolding any polyhedral band without overlap might lead to an algorithm for unfolding any prismatoid without overlap--cannot be realized. A prismatoid is constructed whose sides constitute a nested polyhedral band, with the property that every placement of the prismatoid top face overlaps with the band unfolding.
Emotion capture based on body postures and movements
Venue: arXiv cs.HC 2007
Year: 2007

In this paper we present a preliminary study for designing interactive systems that are sensible to human emotions based on the body movements. To do so, we first review the literature on the various approaches for defining and characterizing human emotions. After justifying the adopted characterization space for emotions, we then focus on the movement characteristics that must be captured by the system for being able to recognize the human emotions.
Control and Monitoring System for Modular Wireless Robot
Venue: arXiv cs.RO 2007
Year: 2007

We introduce our concept on the modular wireless robot consisting of three main modules : main unit, data acquisition and data processing modules. We have developed a generic prototype with an integrated control and monitoring system to enhance its flexibility, and to enable simple operation through a web-based interface accessible wirelessly. In present paper, we focus on the microcontroller based hardware to enable data acquisition and remote mechanical control.
Two representation theorems of three-valued structures by means of binary relations
Venue: arXiv cs.DM 2007
Year: 2007

The results here presented are a continuation of the algebraic research line which attempts to find properties of multiple-valued systems based on a poset of two agents. The aim of this paper is to exhibit two relationships between some three-valued structures and binary relations. The established connections are so narrow that two representation theorems are obtained.
Verification of Ptime Reducibility for system F Terms: Type Inference in<br> Dual Light Affine Logic
Venue: arXiv cs.LO 2007
Year: 2007

In a previous work Baillot and Terui introduced Dual light affine logic (DLAL) as a variant of Light linear logic suitable for guaranteeing complexity properties on lambda calculus terms: all typable terms can be evaluated in polynomial time by beta reduction and all Ptime functions can be represented. In the present work we address the problem of typing lambda-terms in second-order DLAL. For that we give a procedure which, starting with a term typed in system F, determines whether it is typable in DLAL and outputs a concrete typing if there exists any. We show that our procedure can be run in time polynomial in the size of the original Church typed system F term.
Distributed spatial multiplexing with 1-bit feedback
Venue: arXiv cs.IT 2007
Year: 2007

We analyze a slow-fading interference network with MN non-cooperating single-antenna sources and M non-cooperating single-antenna destinations. In particular, we assume that the sources are divided into M mutually exclusive groups of N sources each, every group is dedicated to transmit a common message to a unique destination, all transmissions occur concurrently and in the same frequency band and a dedicated 1-bit broadcast feedback channel from each destination to its corresponding group of sources exists. We provide a feedback-based iterative distributed (multi-user) beamforming algorithm, which "learns" the channels between each group of sources and its assigned destination. This algorithm is a straightforward generalization, to the multi-user case, of the feedback-based iterative distributed beamforming algorithm proposed recently by Mudumbai et al., in IEEE Trans. Inf. Th. (submitted) for networks with a single group of sources and a single destination. Putting the algorithm into a Markov chain context, we provide a simple convergence proof. We then show that, for M finite and N approaching infinity, spatial multiplexing based on the beamforming weights produced by the algorithm achieves full spatial multiplexing gain of M and full per-stream array gain of N, provided the time spent "learning'' the channels scales linearly in N. The network is furthermore shown to "crystallize''. Finally, we characterize the corresponding crystallization rate.
Designing a commutative replicated data type
Venue: arXiv cs.DC 2007
Year: 2007

Commuting operations greatly simplify consistency in distributed systems. This paper focuses on designing for commutativity, a topic neglected previously. We show that the replicas of \emph{any} data type for which concurrent operations commute converges to a correct value, under some simple and standard assumptions. We also show that such a data type supports transactions with very low cost. We identify a number of approaches and techniques to ensure commutativity. We re-use some existing ideas (non-destructive updates coupled with invariant identification), but propose a much more efficient implementation. Furthermore, we propose a new technique, background consensus. We illustrate these ideas with a shared edit buffer data type.