OpenRaiser/Intern-Atlas huggingface dataset:
On the Second-Order Statistics of the Instantaneous Mutual Information in Rayleigh Fading Channels
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, the second-order statistics of the instantaneous mutual information are studied, in time-varying Rayleigh fading channels, assuming general non-isotropic scattering environments. Specifically, first the autocorrelation function, correlation coefficient, level crossing rate, and the average outage duration of the instantaneous mutual information are investigated in single-input single-output (SISO) systems. Closed-form exact expressions are derived, as well as accurate approximations in low- and high-SNR regimes. Then, the results are extended to multiple-input single-output and single-input multiple-output systems, as well as multiple-input multiple-output systems with orthogonal space-time block code transmission. Monte Carlo simulations are provided to verify the accuracy of the analytical results. The results shed more light on the dynamic behavior of the instantaneous mutual information in mobile fading channels.
A Service-Centric Approach to a Parameterized RBAC Service
Venue: arXiv cs.CR 2006
Year: 2006

Significant research has been done in the area of Role Based Access Control [RBAC]. Within this research there has been a thread of work focusing on adding parameters to the role and permissions within RBAC. The primary benefit of parameter support in RBAC comes in the form of a significant increase in specificity in how permissions may be granted. This paper focuses on implementing a parameterized implementation based heavily upon existing standards.
Evaluation of interval extension of the power function by graph decomposition
Venue: arXiv cs.MS 2006
Year: 2006

The subject of our talk is the correct evaluation of interval extension of the function specified by the expression x^y without any constraints on the values of x and y. The core of our approach is a decomposition of the graph of x^y into a small number of parts which can be transformed into subsets of the graph of x^y for non-negative bases x. Because of this fact, evaluation of interval extension of x^y, without any constraints on x and y, is not much harder than evaluation of interval extension of x^y for non-negative bases x.
Implementation and Deployment of a Distributed Network Topology Discovery Algorithm
Venue: arXiv cs.NI 2006
Year: 2006

In the past few years, the network measurement community has been interested in the problem of internet topology discovery using a large number (hundreds or thousands) of measurement monitors. The standard way to obtain information about the internet topology is to use the traceroute tool from a small number of monitors. Recent papers have made the case that increasing the number of monitors will give a more accurate view of the topology. However, scaling up the number of monitors is not a trivial process. Duplication of effort close to the monitors wastes time by reexploring well-known parts of the network, and close to destinations might appear to be a distributed denial-of-service (DDoS) attack as the probes converge from a set of sources towards a given destination. In prior work, authors of this report proposed Doubletree, an algorithm for cooperative topology discovery, that reduces the load on the network, i.e., router IP interfaces and end-hosts, while discovering almost as many nodes and links as standard approaches based on traceroute. This report presents our open-source and freely downloadable implementation of Doubletree in a tool we call traceroute@home. We describe the deployment and validation of traceroute@home on the PlanetLab testbed and we report on the lessons learned from this experience. We discuss how traceroute@home can be developed further and discuss ideas for future improvements.
User-Relative Names for Globally Connected Personal Devices
Venue: arXiv cs.NI 2006
Year: 2006

Nontechnical users who own increasingly ubiquitous network-enabled personal devices such as laptops, digital cameras, and smart phones need a simple, intuitive, and secure way to share information and services between their devices. User Information Architecture, or UIA, is a novel naming and peer-to-peer connectivity architecture addressing this need. Users assign UIA names by "introducing" devices to each other on a common local-area network, but these names remain securely bound to their target as devices migrate. Multiple devices owned by the same user, once introduced, automatically merge their namespaces to form a distributed "personal cluster" that the owner can access or modify from any of his devices. Instead of requiring users to allocate globally unique names from a central authority, UIA enables users to assign their own "user-relative" names both to their own devices and to other users. With UIA, for example, Alice can always access her iPod from any of her own personal devices at any location via the name "ipod", and her friend Bob can access her iPod via a relative name like "ipod.Alice".
Matching Edges in Images ; Application to Face Recognition
Venue: arXiv cs.CV 2006
Year: 2006

This communication describes a representation of images as a set of edges characterized by their position and orientation. This representation allows the comparison of two images and the computation of their similarity. The first step in this computation of similarity is the seach of a geometrical basis of the two dimensional space where the two images are represented simultaneously after transformation of one of them. Presently, this simultaneous representation takes into account a shift and a scaling ; it may be extended to rotations or other global geometrical transformations. An elementary probabilistic computation shows that a sufficient but not excessive number of trials (a few tens) ensures that the exhibition of this common basis is guaranteed in spite of possible errors in the detection of edges. When this first step is performed, the search of similarity between the two images reduces to counting the coincidence of edges in the two images. The approach may be applied to many problems of pattern matching ; it was checked on face recognition.
A unifying framework for seed sensitivity and its application to subset seeds (Extended abstract)
Venue: arXiv cs.OH 2006
Year: 2006

We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem - a set of target alignments, an associated probability distribution, and a seed model - that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.
Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence
Venue: arXiv cs.LG 2006
Year: 2006

We address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions. The task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown but belongs to a known countable family of environments. We find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. We analyze how tight these conditions are and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as Markov Decision Processes and mixing conditions.
Complex Systems + Systems Engineering = Complex Systems Engineeri
Venue: arXiv cs.MA 2006
Year: 2006

One may define a complex system as a system in which phenomena emerge as a consequence of multiscale interaction among the system's components and their environments. The field of Complex Systems is the study of such systems--usually naturally occurring, either bio-logical or social. Systems Engineering may be understood to include the conceptualising and building of systems that consist of a large number of concurrently operating and interacting components--usually including both human and non-human elements. It has become increasingly apparent that the kinds of systems that systems engineers build have many of the same multiscale characteristics as those of naturally occurring complex systems. In other words, systems engineering is the engineering of complex systems. This paper and the associated panel will explore some of the connections between the fields of complex systems and systems engineering.
Digital watermarking in the singular vector domain
Venue: arXiv cs.MM 2006
Year: 2006

Many current watermarking algorithms insert data in the spatial or transform domains like the discrete cosine, the discrete Fourier, and the discrete wavelet transforms. In this paper, we present a data-hiding algorithm that exploits the singular value decomposition (SVD) representation of the data. We compute the SVD of the host image and the watermark and embed the watermark in the singular vectors of the host image. The proposed method leads to an imperceptible scheme for digital images, both in grey scale and color and is quite robust against attacks like noise and JPEG compression.
Graphics Turing Test
Venue: arXiv cs.GR 2006
Year: 2006

We define a Graphics Turing Test to measure graphics performance in a similar manner to the definition of the traditional Turing Test. To pass the test one needs to reach a computational scale, the Graphics Turing Scale, for which Computer Generated Imagery becomes comparatively indistinguishable from real images while also being interactive. We derive an estimate for this computational scale which, although large, is within reach of todays supercomputers. We consider advantages and disadvantages of various computer systems designed to pass the Graphics Turing Test. Finally we discuss commercial applications from the creation of such a system, in particular Interactive Cinema.
Multiterminal Source Coding with Two Encoders--I: A Computable Outer Bound
Venue: arXiv cs.IT 2006
Year: 2006

In this first part, a computable outer bound is proved for the multiterminal source coding problem, for a setup with two encoders, discrete memoryless sources, and bounded distortion measures.
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures
Venue: arXiv cs.DM 2006
Year: 2006

We study the notion of limit sets of cellular automata associated with probability measures (mu-limit sets). This notion was introduced by P. Kurka and A. Maass. It is a refinement of the classical notion of omega-limit sets dealing with the typical long term behavior of cellular automata. It focuses on the words whose probability of appearance does not tend to 0 as time tends to infinity (the persistent words). In this paper, we give a characterisation of the persistent language for non sensible cellular automata associated with Bernouilli measures. We also study the computational complexity of these languages. We show that the persistent language can be non-recursive. But our main result is that the set of quasi-nilpotent cellular automata (those with a single configuration in their mu-limit set) is neither recursively enumerable nor co-recursively enumerable.
Minimum-Cost Coverage of Point Sets by Disks
Venue: arXiv cs.DS 2006
Year: 2006

We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t_j) and radii (r_j) that cover a given set of demand points Y in the plane at the smallest possible cost. We consider cost functions of the form sum_j f(r_j), where f(r)=r^alpha is the cost of transmission to radius r. Special cases arise for alpha=1 (sum of radii) and alpha=2 (total area); power consumption models in wireless network design often use an exponent alpha>2. Different scenarios arise according to possible restrictions on the transmission centers t_j, which may be constrained to belong to a given discrete set or to lie on a line, etc. We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points t_j on a given line in order to cover demand points Y in the plane; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in the plane and any fixed alpha>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.
Can an Organism Adapt Itself to Unforeseen Circumstances?
Venue: arXiv cs.AI 2006
Year: 2006

A model of an organism as an autonomous intelligent system has been proposed. This model was used to analyze learning of an organism in various environmental conditions. Processes of learning were divided into two types: strong and weak processes taking place in the absence and the presence of aprioristic information about an object respectively. Weak learning is synonymous to adaptation when aprioristic programs already available in a system (an organism) are started. It was shown that strong learning is impossible for both an organism and any autonomous intelligent system. It was shown also that the knowledge base of an organism cannot be updated. Therefore, all behavior programs of an organism are congenital. A model of a conditioned reflex as a series of consecutive measurements of environmental parameters has been advanced. Repeated measurements are necessary in this case to reduce the error during decision making.
AS Relationships: Inference and Validation
Venue: arXiv cs.NI 2006
Year: 2006

Research on performance, robustness, and evolution of the global Internet is fundamentally handicapped without accurate and thorough knowledge of the nature and structure of the contractual relationships between Autonomous Systems (ASs). In this work we introduce novel heuristics for inferring AS relationships. Our heuristics improve upon previous works in several technical aspects, which we outline in detail and demonstrate with several examples. Seeking to increase the value and reliability of our inference results, we then focus on validation of inferred AS relationships. We perform a survey with ASs' network administrators to collect information on the actual connectivity and policies of the surveyed ASs. Based on the survey results, we find that our new AS relationship inference techniques achieve high levels of accuracy: we correctly infer 96.5% customer to provider (c2p), 82.8% peer to peer (p2p), and 90.3% sibling to sibling (s2s) relationships. We then cross-compare the reported AS connectivity with the AS connectivity data contained in BGP tables. We find that BGP tables miss up to 86.2% of the true adjacencies of the surveyed ASs. The majority of the missing links are of the p2p type, which highlights the limitations of present measuring techniques to capture links of this type. Finally, to make our results easily accessible and practically useful for the community, we open an AS relationship repository where we archive, on a weekly basis, and make publicly available the complete Internet AS-level topology annotated with AS relationship information for every pair of AS neighbors.
Low Latency Wireless Ad-Hoc Networking: Power and Bandwidth Challenges and a Hierarchical Solution
Venue: arXiv cs.IT 2006
Year: 2006

This paper is concerned with the scaling of the number of hops in a large scale wireless ad-hoc network (WANET), a quantity we call network latency. A large network latency affects all aspects of data communication in a WANET, including an increase in delay, packet loss, required processing power and memory. We consider network management and data routing challenges in WANETs with scalable network latency. On the physical side, reducing network latency imposes a significantly higher power and bandwidth demand on nodes, as is reflected in a set of new bounds. On the protocol front, designing distributed routing protocols that can guarantee the delivery of data packets within scalable number of hops is a challenging task. To solve this, we introduce multi-resolution randomized hierarchy (MRRH), a novel power and bandwidth efficient WANET protocol with scalable network latency. MRRH uses a randomized algorithm for building and maintaining a random hierarchical network topology, which together with the proposed routing algorithm can guarantee efficient delivery of data packets in the wireless network. For a network of size $N$, MRRH can provide an average latency of only $O(\log^{3} N)$. The power and bandwidth consumption of MRRH are shown to be \emph{nearly} optimal for the latency it provides. Therefore, MRRH, is a provably efficient candidate for truly large scale wireless ad-hoc networking.
Statistical Properties of Eigen-Modes and Instantaneous Mutual Information in MIMO Time-Varying Rayleigh Channels
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we study two important metrics in multiple-input multiple-output (MIMO) time-varying Rayleigh flat fading channels. One is the eigen-mode, and the other is the instantaneous mutual information (IMI). Their second-order statistics, such as the correlation coefficient, level crossing rate (LCR), and average fade/outage duration, are investigated, assuming a general nonisotropic scattering environment. Exact closed-form expressions are derived and Monte Carlo simulations are provided to verify the accuracy of the analytical results. For the eigen-modes, we found they tend to be spatio-temporally uncorrelated in large MIMO systems. For the IMI, the results show that its correlation coefficient can be well approximated by the squared amplitude of the correlation coefficient of the channel, under certain conditions. Moreover, we also found the LCR of IMI is much more sensitive to the scattering environment than that of each eigen-mode.
Collaborative thesaurus tagging the Wikipedia way
Venue: arXiv cs.IR 2006
Year: 2006

This paper explores the system of categories that is used to classify articles in Wikipedia. It is compared to collaborative tagging systems like del.icio.us and to hierarchical classification like the Dewey Decimal Classification (DDC). Specifics and commonalitiess of these systems of subject indexing are exposed. Analysis of structural and statistical properties (descriptors per record, records per descriptor, descriptor levels) shows that the category system of Wikimedia is a thesaurus that combines collaborative tagging and hierarchical subject indexing in a special way.
Concerning the differentiability of the energy function in vector quantization algorithms
Venue: arXiv cs.LG 2006
Year: 2006

The adaptation rule for Vector Quantization algorithms, and consequently the convergence of the generated sequence, depends on the existence and properties of a function called the energy function, defined on a topological manifold. Our aim is to investigate the conditions of existence of such a function for a class of algorithms examplified by the initial ''K-means'' and Kohonen algorithms. The results presented here supplement previous studies and show that the energy function is not always a potential but at least the uniform limit of a series of potential functions which we call a pseudo-potential. Our work also shows that a large number of existing vector quantization algorithms developped by the Artificial Neural Networks community fall into this category. The framework we define opens the way to study the convergence of all the corresponding adaptation rules at once, and a theorem gives promising insights in that direction. We also demonstrate that the ''K-means'' energy function is a pseudo-potential but not a potential in general. Consequently, the energy function associated to the ''Neural-Gas'' is not a potential in general.
Efficient algorithms for deciding the type of growth of products of integer matrices
Venue: arXiv cs.CC 2006
Year: 2006

For a given finite set $Σ$ of matrices with nonnegative integer entries we study the growth of $$ \max_t(Σ) = \max\{\|A_{1}... A_{t}\|: A_i \in Σ\}.$$ We show how to determine in polynomial time whether the growth with $t$ is bounded, polynomial, or exponential, and we characterize precisely all possible behaviors.
Solving Classical String Problems on Compressed Texts
Venue: arXiv cs.DS 2006
Year: 2006

Here we study the complexity of string problems as a function of the size of a program that generates input. We consider straight-line programs (SLP), since all algorithms on SLP-generated strings could be applied to processing LZ-compressed texts. The main result is a new algorithm for pattern matching when both a text T and a pattern P are presented by SLPs (so-called fully compressed pattern matching problem). We show how to find a first occurrence, count all occurrences, check whether any given position is an occurrence or not in time O(n^2m). Here m,n are the sizes of straight-line programs generating correspondingly P and T. Then we present polynomial algorithms for computing fingerprint table and compressed representation of all covers (for the first time) and for finding periods of a given compressed string (our algorithm is faster than previously known). On the other hand, we show that computing the Hamming distance between two SLP-generated strings is NP- and coNP-hard.
Certain t-partite graphs
Venue: arXiv cs.DM 2006
Year: 2006

By making use of the generalized concept of orthogonality in Latin squares, certain t-partite graphs have been constructed and a suggestion for a net work system and some applications have been made.
Retraction and Generalized Extension of Computing with Words
Venue: arXiv cs.AI 2006
Year: 2006

Fuzzy automata, whose input alphabet is a set of numbers or symbols, are a formal model of computing with values. Motivated by Zadeh's paradigm of computing with words rather than numbers, Ying proposed a kind of fuzzy automata, whose input alphabet consists of all fuzzy subsets of a set of symbols, as a formal model of computing with all words. In this paper, we introduce a somewhat general formal model of computing with (some special) words. The new features of the model are that the input alphabet only comprises some (not necessarily all) fuzzy subsets of a set of symbols and the fuzzy transition function can be specified arbitrarily. By employing the methodology of fuzzy control, we establish a retraction principle from computing with words to computing with values for handling crisp inputs and a generalized extension principle from computing with words to computing with all words for handling fuzzy inputs. These principles show that computing with values and computing with all words can be respectively implemented by computing with words. Some algebraic properties of retractions and generalized extensions are addressed as well.
Successive Wyner-Ziv Coding Scheme and its Application to the Quadratic Gaussian CEO Problem
Venue: arXiv cs.IT 2006
Year: 2006

We introduce a distributed source coding scheme called successive Wyner-Ziv coding. We show that any point in the rate region of the quadratic Gaussian CEO problem can be achieved via the successive Wyner-Ziv coding. The concept of successive refinement in the single source coding is generalized to the distributed source coding scenario, which we refer to as distributed successive refinement. For the quadratic Gaussian CEO problem, we establish a necessary and sufficient condition for distributed successive refinement, where the successive Wyner-Ziv coding scheme plays an important role.