OpenRaiser/Intern-Atlas huggingface dataset:
Belief Conditioning Rules (BCRs)
Venue: arXiv cs.AI 2006
Year: 2006

In this paper we propose a new family of Belief Conditioning Rules (BCRs) for belief revision. These rules are not directly related with the fusion of several sources of evidence but with the revision of a belief assignment available at a given time according to the new truth (i.e. conditioning constraint) one has about the space of solutions of the problem.
ITs, a structure sensitive information theory
Venue: arXiv cs.IT 2006
Year: 2006

Broadly speaking Information theory (IT) assumes no structure of the underlying states. But what about contexts where states do have a clear structure - how should IT cope with such situations? And if such coping is at all possible then - how should structure be expressed so that it can be coped with? A possible answer to these questions is presented here. Noting that IT can cope well with a structure expressed as an accurate clustering (by shifting to the implied reduced alphabet), a generalization is suggested in which structure is expressed as a measure on reduced alphabets. Given such structure an extension of IT is presented where the reduced alphabets are treated simultaneously. This structure-sensitive IT, called ITs, extends traditional IT in the sense that: a)there are structure-sensitive analogs to the notions of traditional IT and b)translating a theorem in IT by replacing its notions with their structure-sensitive counterparts, yields a (provable) theorem of ITs. Seemingly paradoxically, ITs extends IT but it's completely within the framework of IT. The richness of the suggested structures is demonstrated by two disparate families studied in more detail: the family of hierarchical structures and the family of linear structures. The formal findings extend the scope of cases to which a rigorous application of IT can be applied (with implications on quantization, for example). The implications on the foundations of IT are that the assumption regarding no underlying structure of states is not mandatory and that there is a framework for expressing such underlying structure.
Strong Consistency of the Good-Turing Estimator
Venue: arXiv cs.IT 2006
Year: 2006

We consider the problem of estimating the total probability of all symbols that appear with a given frequency in a string of i.i.d. random variables with unknown distribution. We focus on the regime in which the block length is large yet no symbol appears frequently in the string. This is accomplished by allowing the distribution to change with the block length. Under a natural convergence assumption on the sequence of underlying distributions, we show that the total probabilities converge to a deterministic limit, which we characterize. We then show that the Good-Turing total probability estimator is strongly consistent.
The uncovering of hidden structures by Latent Semantic Analysis
Venue: arXiv cs.IR 2006
Year: 2006

Latent Semantic Analysis (LSA) is a well known method for information retrieval. It has also been applied as a model of cognitive processing and word-meaning acquisition. This dual importance of LSA derives from its capacity to modulate the meaning of words by contexts, dealing successfully with polysemy and synonymy. The underlying reasons that make the method work are not clear enough. We propose that the method works because it detects an underlying block structure (the blocks corresponding to topics) in the term by document matrix. In real cases this block structure is hidden because of perturbations. We propose that the correct explanation for LSA must be searched in the structure of singular vectors rather than in the profile of singular values. Using Perron-Frobenius theory we show that the presence of disjoint blocks of documents is marked by sign-homogeneous entries in the vectors corresponding to the documents of one block and zeros elsewhere. In the case of nearly disjoint blocks, perturbation theory shows that if the perturbations are small the zeros in the leading vectors are replaced by small numbers (pseudo-zeros). Since the singular values of each block might be very different in magnitude, their order does not mirror the order of blocks. When the norms of the blocks are similar, LSA works fine, but we propose that when the topics have different sizes, the usual procedure of selecting the first k singular triplets (k being the number of blocks) should be replaced by a method that selects the perturbed Perron vectors for each block.
Results on Parity-Check Matrices with Optimal Stopping and/or Dead-End Set Enumerators
Venue: arXiv cs.IT 2006
Year: 2006

The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this paper, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails a trade-off between performance and complexity. We give bounds on the complexity of iterative decoders achieving optimal performance in terms of the sizes of the underlying parity-check matrices. Further, we fully characterize codes for which the optimal stopping set enumerator equals the weight enumerator.
The evolution of navigable small-world networks
Venue: arXiv cs.DS 2006
Year: 2006

Small-world networks, which combine randomized and structured elements, are seen as prevalent in nature. Several random graph models have been given for small-world networks, with one of the most fruitful, introduced by Jon Kleinberg, showing in which type of graphs it is possible to route, or navigate, between vertices with very little knowledge of the graph itself. Kleinberg's model is static, with random edges added to a fixed grid. In this paper we introduce, analyze and test a randomized algorithm which successively rewires a graph with every application. The resulting process gives a model for the evolution of small-world networks with properties similar to those studied by Kleinberg.
Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives
Venue: arXiv cs.NI 2006
Year: 2006

Where distributed agents must share voluminous set membership information, Bloom filters provide a compact, though lossy, way for them to do so. Numerous recent networking papers have examined the trade-offs between the bandwidth consumed by the transmission of Bloom filters, and the error rate, which takes the form of false positives, and which rises the more the filters are compressed. In this paper, we introduce the retouched Bloom filter (RBF), an extension that makes the Bloom filter more flexible by permitting the removal of selected false positives at the expense of generating random false negatives. We analytically show that RBFs created through a random process maintain an overall error rate, expressed as a combination of the false positive rate and the false negative rate, that is equal to the false positive rate of the corresponding Bloom filters. We further provide some simple heuristics and improved algorithms that decrease the false positive rate more than than the corresponding increase in the false negative rate, when creating RBFs. Finally, we demonstrate the advantages of an RBF over a Bloom filter in a distributed network topology measurement application, where information about large stop sets must be shared among route tracing monitors.
Strip Packing vs. Bin Packing
Venue: arXiv cs.DS 2006
Year: 2006

In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) Any offline bin packing algorithm can be applied to strip packing maintaining the same asymptotic worst-case ratio. Thus using FFD (MFFD) as a subroutine, we get a practical (simple and fast) algorithm for strip packing with an upper bound 11/9 (71/60). A simple AFPTAS for strip packing immediately follows. (2) A class of Harmonic-based algorithms for bin packing can be applied to online strip packing maintaining the same asymptotic competitive ratio. It implies online strip packing admits an upper bound of 1.58889 on the asymptotic competitive ratio, which is very close to the lower bound 1.5401 and significantly improves the previously best bound of 1.6910 and affirmatively answers an open question posed by Csirik et. al.
Linguistically Grounded Models of Language Change
Venue: arXiv cs.AI 2006
Year: 2006

Questions related to the evolution of language have recently known an impressive increase of interest (Briscoe, 2002). This short paper aims at questioning the scientific status of these models and their relations to attested data. We show that one cannot directly model non-linguistic factors (exogenous factors) even if they play a crucial role in language evolution. We then examine the relation between linguistic models and attested language data, as well as their contribution to cognitive linguistics.
Creation and Growth of Components in a Random Hypergraph Process
Venue: arXiv cs.DM 2006
Year: 2006

Denote by an $\ell$-component a connected $b$-uniform hypergraph with $k$ edges and $k(b-1) - \ell$ vertices. We prove that the expected number of creations of $\ell$-component during a random hypergraph process tends to 1 as $\ell$ and $b$ tend to $\infty$ with the total number of vertices $n$ such that $\ell = o(\sqrt[3]{\frac{n}{b}})$. Under the same conditions, we also show that the expected number of vertices that ever belong to an $\ell$-component is approximately $12^{1/3} (b-1)^{1/3} \ell^{1/3} n^{2/3}$. As an immediate consequence, it follows that with high probability the largest $\ell$-component during the process is of size $O((b-1)^{1/3} \ell^{1/3} n^{2/3})$. Our results give insight about the size of giant components inside the phase transition of random hypergraphs.
Prioritizing Software Inspection Results using Static Profiling
Venue: arXiv cs.SE 2006
Year: 2006

Static software checking tools are useful as an additional automated software inspection step that can easily be integrated in the development cycle and assist in creating secure, reliable and high quality code. However, an often quoted disadvantage of these tools is that they generate an overly large number of warnings, including many false positives due to the approximate analysis techniques. This information overload effectively limits their usefulness. In this paper we present ELAN, a technique that helps the user prioritize the information generated by a software inspection tool, based on a demand-driven computation of the likelihood that execution reaches the locations for which warnings are reported. This analysis is orthogonal to other prioritization techniques known from literature, such as severity levels and statistical analysis to reduce false positives. We evaluate feasibility of our technique using a number of case studies and assess the quality of our predictions by comparing them to actual values obtained by dynamic profiling.
Finite element method for thermal analysis of concentrating solar receivers
Venue: arXiv cs.CE 2006
Year: 2006

Application of finite element method and heat conductivity transfer model for calculation of temperature distribution in receiver for dish-Stirling concentrating solar system is described. The method yields discretized equations that are entirely local to the elements and provides complete geometric flexibility. A computer program solving the finite element method problem is created and great number of numerical experiments is carried out. Illustrative numerical results are given for an array of triangular elements in receiver for dish-Stirling system.
Gallager's Exponent for MIMO Channels: A Reliability-Rate Tradeoff
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we derive Gallager's random coding error exponent for multiple-input multiple-output (MIMO) channels, assuming no channel-state information (CSI) at the transmitter and perfect CSI at the receiver. This measure gives insight into a fundamental tradeoff between the communication reliability and information rate of MIMO channels, enabling to determine the required codeword length to achieve a prescribed error probability at a given rate below the channel capacity. We quantify the effects of the number of antennas, channel coherence time, and spatial fading correlation on the MIMO exponent. In addition, general formulae for the ergodic capacity and the cutoff rate in the presence of spatial correlation are deduced from the exponent expressions. These formulae are applicable to arbitrary structures of transmit and receive correlation, encompassing all the previously known results as special cases of our expressions.
New Upper Bounds on The Approximability of 3D Strip Packing
Venue: arXiv cs.DS 2006
Year: 2006

In this paper, we study the 3D strip packing problem in which we are given a list of 3-dimensional boxes and required to pack all of them into a 3-dimensional strip with length 1 and width 1 and unlimited height to minimize the height used. Our results are below: i) we give an approximation algorithm with asymptotic worst-case ratio 1.69103, which improves the previous best bound of $2+ε$ by Jansen and Solis-Oba of SODA 2006; ii) we also present an asymptotic PTAS for the case in which all items have {\em square} bases.
Deriving Escape Analysis by Abstract Interpretation: Proofs of results
Venue: arXiv cs.PL 2006
Year: 2006

Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain e as an abstract interpretation of concrete states, which we then refine into an abstract domain er which is more concrete than e and, hence, leads to a more precise escape analysis than e. We provide optimality results for both e and er, in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of er is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications. This report contains the proofs of results of a paper with the same title and authors and to be published in the Journal "Higher-Order Symbolic Computation".
A Theory of Probabilistic Boosting, Decision Trees and Matryoshki
Venue: arXiv cs.LG 2006
Year: 2006

We present a theory of boosting probabilistic classifiers. We place ourselves in the situation of a user who only provides a stopping parameter and a probabilistic weak learner/classifier and compare three types of boosting algorithms: probabilistic Adaboost, decision tree, and tree of trees of ... of trees, which we call matryoshka. "Nested tree," "embedded tree" and "recursive tree" are also appropriate names for this algorithm, which is one of our contributions. Our other contribution is the theoretical analysis of the algorithms, in which we give training error bounds. This analysis suggests that the matryoshka leverages probabilistic weak classifiers more efficiently than simple decision trees.
Program Spectra Analysis in Embedded Software: A Case Study
Venue: arXiv cs.SE 2006
Year: 2006

Because of constraints imposed by the market, embedded software in consumer electronics is almost inevitably shipped with faults and the goal is just to reduce the inherent unreliability to an acceptable level before a product has to be released. Automatic fault diagnosis is a valuable tool to capture software faults without extra effort spent on testing. Apart from a debugging aid at design and integration time, fault diagnosis can help analyzing problems during operation, which allows for more accurate system recovery. In this paper we discuss perspectives and limitations for applying a particular fault diagnosis technique, namely the analysis of program spectra, in the area of embedded software in consumer electronics devices. We illustrate these by our first experience with a test case from industry.
Bidding to the Top: VCG and Equilibria of Position-Based Auctions
Venue: arXiv cs.GT 2006
Year: 2006

Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the auction. This bid is interpreted as the maximum amount the advertiser is willing to pay per click on its ad. When search queries arrive, the bids are used to rank the ads linearly on the search result page. The advertisers pay for each user who clicks on their ad, and the amount charged depends on the bids of all the advertisers participating in the auction. In order to be effective, advertisers seek to be as high on the list as their budget permits, subject to the market. We study the problem of ranking ads and associated pricing mechanisms when the advertisers not only specify a bid, but additionally express their preference for positions in the list of ads. In particular, we study "prefix position auctions" where advertiser $i$ can specify that she is interested only in the top $b_i$ positions. We present a simple allocation and pricing mechanism that generalizes the desirable properties of current auctions that do not have position constraints. In addition, we show that our auction has an "envy-free" or "symmetric" Nash equilibrium with the same outcome in allocation and pricing as the well-known truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this equilibrium is the best such equilibrium for the advertisers in terms of the profit made by each advertiser. We also discuss other position-based auctions.
Geometric definition of a new skeletonization concept
Venue: arXiv cs.CG 2006
Year: 2006

The Divider set, as an innovative alternative concept to maximal disks, Voronoi sets and cut loci, is presented with a formal definition based on topology and differential geometry. The relevant mathematical theory by previous authors and a comparison with other medial axis definitions is presented. Appropriate applications are proposed and examined.
An Introduction to the DSm Theory for the Combination of Paradoxical, Uncertain, and Imprecise Sources of Information
Venue: arXiv cs.AI 2006
Year: 2006

The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this introduction, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the literature, developed for dealing with imprecise, uncertain and paradoxical sources of information. We focus our presentation here rather on the foundations of DSmT, and on the two important new rules of combination, than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout the presentation to show the efficiency and the generality of this new approach.
On the randomness of independent experiments
Venue: arXiv cs.IT 2006
Year: 2006

Given a probability distribution P, what is the minimum amount of bits needed to store a value x sampled according to P, such that x can later be recovered (except with some small probability)? Or, what is the maximum amount of uniform randomness that can be extracted from x? Answering these and similar information-theoretic questions typically boils down to computing so-called smooth entropies. In this paper, we derive explicit and almost tight bounds on the smooth entropies of n-fold product distributions.
MIMO scheme performance and detection in epsilon noise
Venue: arXiv cs.IT 2006
Year: 2006

New approach for analysis and decoding MIMO signaling is developed for usual model of nongaussion noise consists of background and impulsive noise named epsilon - noise. It is shown that non-gaussion noise performance significantly worse than gaussion ones. Stimulation results strengthen out theory. Robust in statistical sense detection rule is suggested for such kind of noise features much best robust detector performance than detector designed for Gaussian noise in impulsive environment and modest margin in background noise. Proposed algorithms performance are comparable with developed potential bound. Proposed tool, is crucial issue for MIMO communication system design, since real noise environment has impulsive character that contradict with wide used Gaussian approach, so real MIMO performance much different for Gaussian a non-Gaussian noise model.
Expressing Security Properties Using Selective Interleaving Functions
Venue: arXiv cs.CR 2006
Year: 2006

McLean's notion of Selective Interleaving Functions (SIFs) is perhaps the best-known attempt to construct a framework for expressing various security properties. We examine the expressive power of SIFs carefully. We show that SIFs cannot capture nondeducibility on strategies (NOS). We also prove that the set of security properties expressed with SIFs is not closed under conjunction, from which it follows that separability is strictly stronger than double generalized noninterference. However, we show that if we generalize the notion of SIF in a natural way, then NOS is expressible, and the set of security properties expressible by generalized SIFs is closed under conjunction.
Security Assessment of E-Tax Filing Websites
Venue: arXiv cs.CR 2006
Year: 2006

Technical security is only part of E-Commerce security operations; human usability and security perception play major and sometimes dominating factors. For instance, slick websites with impressive security icons but no real technical security are often perceived by users to be trustworthy (and thus more profitable) than plain vanilla websites that use powerful encryption for transmission and server protection. We study one important type of E-Commerce transaction website, E-Tax Filing, that is exposed to large populations. We assess a large number of international (5), Federal (USA), and state E-Tax filing websites (38) for both technical security protection and human perception of security. As a result of this assessment, we identify security best practices across these E-Tax Filing websites and recommend additional security techniques that have not been found in current use by E-Tax Filing websites.
The Dynamics of A Self-Forming Network
Venue: arXiv cs.NI 2006
Year: 2006

This article describes our strategy for deploying self-forming ad hoc networks based on the Internet Protocol version 6 and evaluates the dynamics of this proposal. Among others, we suggest a technique called adaptive routing that provides secure intelligent routing capabilities to computer communication networks. This technique uses the flow label, supports hybrid metrics, network load sharing, and is not restricted to evaluation of performance on first hop routers when making routing decisions. Selective anycasting is an extension to the anycast addressing model that supports exclusion of members of groups that perform poorly or inappropriately on a per-host basis. Distributed name lookup is suggested for integrating self-forming and global networks where they coexist. At last, we pose an address hierarchy to support unmanaged discovery of services in unknown networks.