OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Compact Prefix Codes
Venue: arXiv cs.DS 2009
Year: 2009

It is well-known that, given a probability distribution over $n$ characters, in the worst case it takes (Θ(n \log n)) bits to store a prefix code with minimum expected codeword length. However, in this paper we first show that, for any $0<ε<1/2$ with (1 / ε= \Oh{\polylog{n}}), it takes $\Oh{n \log \log (1 / ε)}$ bits to store a prefix code with expected codeword length within $ε$ of the minimum. We then show that, for any constant (c > 1), it takes $\Oh{n^{1 / c} \log n}$ bits to store a prefix code with expected codeword length at most $c$ times the minimum. In both cases, our data structures allow us to encode and decode any character in $\Oh{1}$ time.
Dynamic and Non-Uniform Pricing Strategies for Revenue Maximization
Venue: arXiv cs.GT 2009
Year: 2009

We consider the Item Pricing problem for revenue maximization in the limited supply setting, where a single seller with $n$ items caters to $m$ buyers with unknown subadditive valuation functions who arrive in a sequence. The seller sets the prices on individual items. Each buyer buys a subset of yet unsold items that maximizes her utility. Our goal is to design pricing strategies that guarantee an expected revenue that is within a small factor $α$ of the maximum possible social welfare -- an upper bound on the maximum revenue that can be generated. Most earlier work has focused on the unlimited supply setting, where selling items to some buyer does not affect their availability to the future buyers. Balcan et. al. (EC 2008) studied the limited supply setting, giving a randomized strategy that assigns a single price to all items (uniform strategy), and never changes it (static strategy), that gives an $2^{O(\sqrt{\log n \log \log n})}$-approximation, and moreover, no static uniform pricing strategy can give better than $2^{Ω(\log^{1/4} n)}$- approximation. We improve this lower bound to $2^{Ω(sqrt{\log n})}$. We consider dynamic uniform strategies, which can change the price upon the arrival of each buyer but the price on all unsold items is the same at all times, and static non-uniform strategies, which can assign different prices to different items but can never change it after setting it initially. We design such pricing strategies that give a poly-logarithmic approximation to maximum revenue. Thus in the limited supply setting, our results highlight a strong separation between the power of dynamic and non-uniform pricing versus static uniform pricing. To our knowledge, this is the first non-trivial analysis of dynamic and non-uniform pricing schemes for revenue maximization.
An Analysis of Bug Distribution in Object Oriented Systems
Venue: arXiv cs.SE 2009
Year: 2009

We introduced a new approach to describe Java software as graph, where nodes represent a Java file - called compilation unit (CU) - and an edges represent a relations between them. The software system is characterized by the degree distribution of the graph properties, like in-or-out links, as well as by the distribution of Chidamber and Kemerer metrics computed on its CUs. Every CU can be related to one or more bugs during its life. We find a relationship among the software system and the bugs hitting its nodes. We found that the distribution of some metrics, and the number of bugs per CU, exhibit a power-law behavior in their tails, as well as the number of CUs influenced by a specific bug. We examine the evolution of software metrics across different releases to understand how relationships among CUs metrics and CUs faultness change with time.
Information Distance in Multiples
Venue: arXiv cs.CV 2009
Year: 2009

Information distance is a parameter-free similarity measure based on compression, used in pattern recognition, data mining, phylogeny, clustering, and classification. The notion of information distance is extended from pairs to multiples (finite lists). We study maximal overlap, metricity, universality, minimal overlap, additivity, and normalized information distance in multiples. We use the theoretical notion of Kolmogorov complexity which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. {\em Index Terms}-- Information distance, multiples, pattern recognition, data mining, similarity, Kolmogorov complexity
Interpretations of the Web of Data
Venue: arXiv cs.AI 2009
Year: 2009

The emerging Web of Data utilizes the web infrastructure to represent and interrelate data. The foundational standards of the Web of Data include the Uniform Resource Identifier (URI) and the Resource Description Framework (RDF). URIs are used to identify resources and RDF is used to relate resources. While RDF has been posited as a logic language designed specifically for knowledge representation and reasoning, it is more generally useful if it can conveniently support other models of computing. In order to realize the Web of Data as a general-purpose medium for storing and processing the world's data, it is necessary to separate RDF from its logic language legacy and frame it simply as a data model. Moreover, there is significant advantage in seeing the Semantic Web as a particular interpretation of the Web of Data that is focused specifically on knowledge representation and reasoning. By doing so, other interpretations of the Web of Data are exposed that realize RDF in different capacities and in support of different computing models.
Finding Anomalous Periodic Time Series: An Application to Catalogs of Periodic Variable Stars
Venue: arXiv cs.LG 2009
Year: 2009

Catalogs of periodic variable stars contain large numbers of periodic light-curves (photometric time series data from the astrophysics domain). Separating anomalous objects from well-known classes is an important step towards the discovery of new classes of astronomical objects. Most anomaly detection methods for time series data assume either a single continuous time series or a set of time series whose periods are aligned. Light-curve data precludes the use of these methods as the periods of any given pair of light-curves may be out of sync. One may use an existing anomaly detection method if, prior to similarity calculation, one performs the costly act of aligning two light-curves, an operation that scales poorly to massive data sets. This paper presents PCAD, an unsupervised anomaly detection method for large sets of unsynchronized periodic time-series data, that outputs a ranked list of both global and local anomalies. It calculates its anomaly score for each light-curve in relation to a set of centroids produced by a modified k-means clustering algorithm. Our method is able to scale to large data sets through the use of sampling. We validate our method on both light-curve data and other time series data sets. We demonstrate its effectiveness at finding known anomalies, and discuss the effect of sample size and number of centroids on our results. We compare our method to naive solutions and existing time series anomaly detection methods for unphased data, and show that PCAD's reported anomalies are comparable to or better than all other methods. Finally, astrophysicists on our team have verified that PCAD finds true anomalies that might be indicative of novel astrophysical phenomena.
Level Crossing Rates of Interference in Cognitive Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

The future deployment of cognitive radios is critically dependent on the fact that the incumbent primary user system must remain as oblivious as possible to their presence. This in turn heavily relies on the fluctuations of the interfering cognitive radio signals. In this letter we compute the level crossing rates of the cumulative interference created by the cognitive radios. We derive analytical formulae for the level crossing rates in Rayleigh and Rician fast fading conditions. We approximate Rayleigh and Rician level crossing rates using fluctuation rates of gamma and scaled noncentral $χ^2$ processes respectively. The analytical results and the approximations used in their derivations are verified by Monte Carlo simulations and the analysis is applied to a particular CR allocation strategy.
Coevolutionary Genetic Algorithms for Establishing Nash Equilibrium in Symmetric Cournot Games
Venue: arXiv cs.GT 2009
Year: 2009

We use co-evolutionary genetic algorithms to model the players' learning process in several Cournot models, and evaluate them in terms of their convergence to the Nash Equilibrium. The "social-learning" versions of the two co-evolutionary algorithms we introduce, establish Nash Equilibrium in those models, in contrast to the "individual learning" versions which, as we see here, do not imply the convergence of the players' strategies to the Nash outcome. When players use "canonical co-evolutionary genetic algorithms" as learning algorithms, the process of the game is an ergodic Markov Chain, and therefore we analyze simulation results using both the relevant methodology and more general statistical tests, to find that in the "social" case, states leading to NE play are highly frequent at the stationary distribution of the chain, in contrast to the "individual learning" case, when NE is not reached at all in our simulations; to find that the expected Hamming distance of the states at the limiting distribution from the "NE state" is significantly smaller in the "social" than in the "individual learning case"; to estimate the expected time that the "social" algorithms need to get to the "NE state" and verify their robustness and finally to show that a large fraction of the games played are indeed at the Nash Equilibrium.
Major and minor. The formula of musical emotions
Venue: arXiv cs.SD 2009
Year: 2009

The new formulas, which determine sign and amplitude of utilitarian emotions, are proposed on the basis of the information theory of emotions. In area of perception of musical chords the force of emotions depends on the relative pitch of sounds of major and minor chords. Is advanced hypothesis that in the perception of a musical chord in the psyche caused by the subject value of some objective function L. This function is expressed directly through the proportion of the pitch of chord. Major chords are expressed as the straight proportions, which generate idea about an increase in the objective function (L>1) and are caused positive utilitarian emotions. Minor chords are expressed as the inverse proportion, which generate idea about the decrease of objective function (L<1) and are caused negative utilitarian emotions. The formula of musical emotions is advanced: Pwe = log(L) = (1/M)*log(n1*n2*n3* ... *nM), where M is a quantity of voices of chord, ni - integer number (or reciprocal fraction) from the pitch proportion, which corresponds to the i-th voice of chord. Confined experimental check is produced. The limits of the applicability of the formula of musical emotions are investigated. Keywords: sound, music, chord, major, minor, emotions, the formula of musical emotions, the information theory of emotions.
Towards Barter Double Auction as Model for Bilateral Social Cooperations
Venue: arXiv cs.GT 2009
Year: 2009

The idea of this paper is an advanced game concept. This concept is expected to model non-monetary bilateral cooperations between self-interested agents. Such non-monetary cases are social cooperations like allocation of high level jobs or sexual relationships among humans. In a barter double auction, there is a big amount of agents. Every agent has a vector of parameters which specifies his demand and a vector which specifies his offer. Two agents can achieve a commitment through barter exchange. The subjective satisfaction level (a number between 0% and 100%) of an agent is as high as small is the distance between his demand and the accepted offer. This paper introduces some facets of this complex game concept.
Scenario-based Stochastic Constraint Programming
Venue: arXiv cs.AI 2009
Year: 2009

To model combinatorial decision problems involving uncertainty and probability, we extend the stochastic constraint programming framework proposed in [Walsh, 2002] along a number of important dimensions (e.g. to multiple chance constraints and to a range of new objectives). We also provide a new (but equivalent) semantics based on scenarios. Using this semantics, we can compile stochastic constraint programs down into conventional (nonstochastic) constraint programs. This allows us to exploit the full power of existing constraint solvers. We have implemented this framework for decision making under uncertainty in stochastic OPL, a language which is based on the OPL constraint modelling language [Hentenryck et al., 1999]. To illustrate the potential of this framework, we model a wide range of problems in areas as diverse as finance, agriculture and production.
Swap Bribery
Venue: arXiv cs.GT 2009
Year: 2009

In voting theory, bribery is a form of manipulative behavior in which an external actor (the briber) offers to pay the voters to change their votes in order to get her preferred candidate elected. We investigate a model of bribery where the price of each vote depends on the amount of change that the voter is asked to implement. Specifically, in our model the briber can change a voter's preference list by paying for a sequence of swaps of consecutive candidates. Each swap may have a different price; the price of a bribery is the sum of the prices of all swaps that it involves. We prove complexity results for this model, which we call swap bribery, for a broad class of election systems, including variants of approval and k-approval, Borda, Copeland, and maximin.
FTOS-Verify: Analysis and Verification of Non-Functional Properties for Fault-Tolerant Systems
Venue: arXiv cs.DC 2009
Year: 2009

The focus of the tool FTOS is to alleviate designers' burden by offering code generation for non-functional aspects including fault-tolerance mechanisms. One crucial aspect in this context is to ensure that user-selected mechanisms for the system model are sufficient to resist faults as specified in the underlying fault hypothesis. In this paper, formal approaches in verification are proposed to assist the claim. We first raise the precision of FTOS into pure mathematical constructs, and formulate the deterministic assumption, which is necessary as an extension of Giotto-like systems (e.g., FTOS) to equip with fault-tolerance abilities. We show that local properties of a system with the deterministic assumption will be preserved in a modified synchronous system used as the verification model. This enables the use of techniques known from hardware verification. As for implementation, we develop a prototype tool called FTOS-Verify, deploy it as an Eclipse add-on for FTOS, and conduct several case studies.
A New Solution to the Relative Orientation Problem using only 3 Points and the Vertical Direction
Venue: arXiv cs.CV 2009
Year: 2009

This paper presents a new method to recover the relative pose between two images, using three points and the vertical direction information. The vertical direction can be determined in two ways: 1- using direct physical measurement like IMU (inertial measurement unit), 2- using vertical vanishing point. This knowledge of the vertical direction solves 2 unknowns among the 3 parameters of the relative rotation, so that only 3 homologous points are requested to position a couple of images. Rewriting the coplanarity equations leads to a simpler solution. The remaining unknowns resolution is performed by an algebraic method using Grobner bases. The elements necessary to build a specific algebraic solver are given in this paper, allowing for a real-time implementation. The results on real and synthetic data show the efficiency of this method.
DMT Optimality of LR-Aided Linear Decoders for a General Class of Channels, Lattice Designs, and System Models
Venue: arXiv cs.IT 2009
Year: 2009

The work identifies the first general, explicit, and non-random MIMO encoder-decoder structures that guarantee optimality with respect to the diversity-multiplexing tradeoff (DMT), without employing a computationally expensive maximum-likelihood (ML) receiver. Specifically, the work establishes the DMT optimality of a class of regularized lattice decoders, and more importantly the DMT optimality of their lattice-reduction (LR)-aided linear counterparts. The results hold for all channel statistics, for all channel dimensions, and most interestingly, irrespective of the particular lattice-code applied. As a special case, it is established that the LLL-based LR-aided linear implementation of the MMSE-GDFE lattice decoder facilitates DMT optimal decoding of any lattice code at a worst-case complexity that grows at most linearly in the data rate. This represents a fundamental reduction in the decoding complexity when compared to ML decoding whose complexity is generally exponential in rate. The results' generality lends them applicable to a plethora of pertinent communication scenarios such as quasi-static MIMO, MIMO-OFDM, ISI, cooperative-relaying, and MIMO-ARQ channels, in all of which the DMT optimality of the LR-aided linear decoder is guaranteed. The adopted approach yields insight, and motivates further study, into joint transceiver designs with an improved SNR gap to ML decoding.
Distributed Discovery of Large Near-Cliques
Venue: arXiv cs.DC 2009
Year: 2009

Given an undirected graph and $0\leε\le1$, a set of nodes is called $ε$-near clique if all but an $ε$ fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size $ε$-near clique if there exists an $ε^3$-near clique of linear size in the graph. The algorithm uses messages of $O(\log n)$ bits. The failure probability can be reduced to $n^{-Ω(1)}$ in $O(\log n)$ time, and the algorithm also works if the graph contains a clique of size $Ω(n/\log^α\log n)$ for some $α\in (0,1)$.
Answers to Questions Formulated in the Paper "On States Observability in Deterministic Finite Automata"
Venue: arXiv cs.FL 2009
Year: 2009

This paper gives answers to questions formulated as open in the paper "On State Observability in Deterministic Finite Automata" by A. Mateescu and Gh. Paun. Specifically, it demonstrates that for all k >= 2, the families of regular languages acceptable by deterministic finite automata with no more than k semi-observable states, denoted by Tk, are anti-AFL's, and that the family T1 differs in the closure property under Kleene +.
Multimedia Aplication for Solving a Sudoku Game
Venue: arXiv cs.OH 2009
Year: 2009

This article explains the way in which, with the help of Action Script 3 in combination with Flash, a method of solving Sudoku game was implemented, through searching for the certain numbers and after that trying to guess for the squares where there are two possible numbers.
Strong Dependencies between Software Components
Venue: arXiv cs.SE 2009
Year: 2009

Component-based systems often describe context requirements in terms of explicit inter-component dependencies. Studying large instances of such systems?such as free and open source software (FOSS) distributions?in terms of declared dependencies between packages is appealing. It is however also misleading when the language to express dependencies is as expressive as boolean formulae, which is often the case. In such settings, a more appropriate notion of component dependency exists: strong dependency. This paper introduces such notion as a first step towards modeling semantic, rather then syntactic, inter-component relationships. Furthermore, a notion of component sensitivity is derived from strong dependencies, with ap- plications to quality assurance and to the evaluation of upgrade risks. An empirical study of strong dependencies and sensitivity is presented, in the context of one of the largest, freely available, component-based system.
The Convergence of Bird Flocking
Venue: arXiv cs.CG 2009
Year: 2009

We bound the time it takes for a group of birds to reach steady state in a standard flocking model. We prove that (i) within single exponential time fragmentation ceases and each bird settles on a fixed flying direction; (ii) the flocking network converges only after a number of steps that is an iterated exponential of height logarithmic in the number of birds. We also prove the highly surprising result that this bound is optimal. The model directs the birds to adjust their velocities repeatedly by averaging them with their neighbors within a fixed radius. The model is deterministic, but we show that it can tolerate a reasonable amount of stochastic or even adversarial noise. Our methods are highly general and we speculate that the results extend to a wider class of models based on undirected flocking networks, whether defined metrically or topologically. This work introduces new techniques of broader interest, including the "flight net," the "iterated spectral shift," and a certain "residue-clearing" argument in circuit complexity.
On Block Noncoherent Communication with Low-Precision Phase Quantization at the Receiver
Venue: arXiv cs.IT 2009
Year: 2009

We consider communication over the block noncoherent AWGN channel with low-precision Analog-to-Digital Converters (ADCs) at the receiver. For standard uniform Phase Shift Keying (PSK) modulation, we investigate the performance of a receiver architecture that quantizes only the phase of the received signal; this has the advantage of being implementable without automatic gain control, using multiple 1-bit ADCs preceded by analog multipliers. We study the structure of the transition density of the resulting channel model. Several results, based on the symmetry inherent in the channel, are provided to characterize this transition density. A low complexity procedure for computing the channel capacity is obtained using these results. Numerical capacity computations for QPSK show that 8-bin phase quantization of the received signal recovers more than 80-85 % of the capacity attained with unquantized observations, while 12-bin phase quantization recovers above 90-95 % of the unquantized capacity. Dithering the constellation is shown to improve the performance in the face of drastic quantization.
On expressive power and class invariance
Venue: arXiv cs.LO 2009
Year: 2009

In computer science, various logical languages are defined to analyze properties of systems. One way to pinpoint the essential differences between those logics is to compare their expressivity in terms of distinguishing power and expressive power. In this paper, we study those two concepts by regarding the latter notion as the former lifted to classes of models. We show some general results on lifting an invariance relation on models to one on classes of models, such that when the former corresponds to the distinguishing power of a logic, the latter corresponds to its expressive power, given certain compactness requirements. In particular, we introduce the notion of class bisimulation to capture the expressive power of modal logics. We demonstrate the application of our results by revisiting modal definability with our new insights.