OpenRaiser/Intern-Atlas huggingface dataset:
Robot Swarms in an Uncertain World: Controllable Adaptability
Venue: arXiv cs.RO 2006
Year: 2006

There is a belief that complexity and chaos are essential for adaptability. But life deals with complexity every moment, without the chaos that engineers fear so, by invoking goal-directed behaviour. Goals can be programmed. That is why living organisms give us hope to achieve adaptability in robots. In this paper a method for the description of a goal-directed, or programmed, behaviour, interacting with uncertainty of environment, is described. We suggest reducing the structural (goals, intentions) and stochastic components (probability to realise the goal) of individual behaviour to random variables with nominal values to apply probabilistic approach. This allowed us to use a Normalized Entropy Index to detect the system state by estimating the contribution of each agent to the group behaviour. The number of possible group states is 27. We argue that adaptation has a limited number of possible paths between these 27 states. Paths and states can be programmed so that after adjustment to any particular case of task and conditions, adaptability will never involve chaos. We suggest the application of the model to operation of robots or other devices in remote and/or dangerous places.
Robotics Vision-based Heuristic Reasoning for Underwater Target Tracking and Navigation
Venue: arXiv cs.RO 2006
Year: 2006

This paper presents a robotics vision-based heuristic reasoning system for underwater target tracking and navigation. This system is introduced to improve the level of automation of underwater Remote Operated Vehicles (ROVs) operations. A prototype which combines computer vision with an underwater robotics system is successfully designed and developed to perform target tracking and intelligent navigation. ...
Checkbochs: Use Hardware to Check Software
Venue: arXiv cs.OS 2006
Year: 2006

In this paper, we present a system called Checkbochs, a machine simulator that checks rules about its guest operating system and applications at the hardware level. The properties to be checked can be implemented as `plugins' in the Checkbochs simulator. Some of the properties that were checked using Checkbochs include null-pointer checks, format-string vulnerabilities, user/kernel pointer checks, and race-conditions. On implementing these checks, we were able to uncover previously-unknown bugs in widely used Linux distributions. We also tested our tools on undergraduate coursework, and found numerous bugs.
Instanton analysis of Low-Density-Parity-Check codes in the error-floor regime
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we develop instanton method introduced in [1], [2], [3] to analyze quantitatively performance of Low-Density-Parity-Check (LDPC) codes decoded iteratively in the so-called error-floor regime. We discuss statistical properties of the numerical instanton-amoeba scheme focusing on detailed analysis and comparison of two regular LDPC codes: Tanner's (155, 64, 20) and Margulis' (672, 336, 16) codes. In the regime of moderate values of the signal-to-noise ratio we critically compare results of the instanton-amoeba evaluations against the standard Monte-Carlo calculations of the Frame-Error-Rate.
Constraint Functional Logic Programming over Finite Domains
Venue: arXiv cs.PL 2006
Year: 2006

In this paper, we present our proposal to Constraint Functional Logic Programming over Finite Domains (CFLP(FD)) with a lazy functional logic programming language which seamlessly embodies finite domain (FD) constraints. This proposal increases the expressiveness and power of constraint logic programming over finite domains (CLP(FD)) by combining functional and relational notation, curried expressions, higher-order functions, patterns, partial applications, non-determinism, lazy evaluation, logical variables, types, domain variables, constraint composition, and finite domain constraints. We describe the syntax of the language, its type discipline, and its declarative and operational semantics. We also describe TOY(FD), an implementation for CFLPFD(FD), and a comparison of our approach with respect to CLP(FD) from a programming point of view, showing the new features we introduce. And, finally, we show a performance analysis which demonstrates that our implementation is competitive with respect to existing CLP(FD) systems and that clearly outperforms the closer approach to CFLP(FD).
Joint universal lossy coding and identification of i.i.d. vector sources
Venue: arXiv cs.IT 2006
Year: 2006

The problem of joint universal source coding and modeling, addressed by Rissanen in the context of lossless codes, is generalized to fixed-rate lossy coding of continuous-alphabet memoryless sources. We show that, for bounded distortion measures, any compactly parametrized family of i.i.d. real vector sources with absolutely continuous marginals (satisfying appropriate smoothness and Vapnik--Chervonenkis learnability conditions) admits a joint scheme for universal lossy block coding and parameter estimation, and give nonasymptotic estimates of convergence rates for distortion redundancies and variational distances between the active source and the estimated source. We also present explicit examples of parametric sources admitting such joint universal compression and modeling schemes.
A unifying framework for seed sensitivity and its application to subset seeds
Venue: arXiv cs.DS 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.
Low density codes achieve the rate-distortion bound
Venue: arXiv cs.IT 2006
Year: 2006

We propose a new construction for low-density source codes with multiple parameters that can be tuned to optimize the performance of the code. In addition, we introduce a set of analysis techniques for deriving upper bounds for the expected distortion of our construction, as well as more general low-density constructions. We show that (with an optimal encoding algorithm) our codes achieve the rate-distortion bound for a binary symmetric source and Hamming distortion. Our methods also provide rigorous upper bounds on the minimum distortion achievable by previously proposed low-density constructions.
From Dumb Wireless Sensors to Smart Networks using Network Coding
Venue: arXiv cs.IT 2006
Year: 2006

The vision of wireless sensor networks is one of a smart collection of tiny, dumb devices. These motes may be individually cheap, unintelligent, imprecise, and unreliable. Yet they are able to derive strength from numbers, rendering the whole to be strong, reliable and robust. Our approach is to adopt a distributed and randomized mindset and rely on in network processing and network coding. Our general abstraction is that nodes should act only locally and independently, and the desired global behavior should arise as a collective property of the network. We summarize our work and present how these ideas can be applied for communication and storage in sensor networks.
Scalable Algorithms for Aggregating Disparate Forecasts of Probability
Venue: arXiv cs.AI 2006
Year: 2006

In this paper, computational aspects of the panel aggregation problem are addressed. Motivated primarily by applications of risk assessment, an algorithm is developed for aggregating large corpora of internally incoherent probability assessments. The algorithm is characterized by a provable performance guarantee, and is demonstrated to be orders of magnitude faster than existing tools when tested on several real-world data-sets. In addition, unexpected connections between research in risk assessment and wireless sensor networks are exposed, as several key ideas are illustrated to be useful in both fields.
Simulating Network Influence Algorithms Using Particle-Swarms: PageRank and PageRank-Priors
Venue: arXiv cs.DS 2006
Year: 2006

A particle-swarm is a set of indivisible processing elements that traverse a network in order to perform a distributed function. This paper will describe a particular implementation of a particle-swarm that can simulate the behavior of the popular PageRank algorithm in both its {\it global-rank} and {\it relative-rank} incarnations. PageRank is compared against the particle-swarm method on artificially generated scale-free networks of 1,000 nodes constructed using a common gamma value, $γ= 2.5$. The running time of the particle-swarm algorithm is $O(|P|+|P|t)$ where $|P|$ is the size of the particle population and $t$ is the number of particle propagation iterations. The particle-swarm method is shown to be useful due to its ease of extension and running time.
A library of Taylor models for PVS automatic proof checker
Venue: arXiv cs.MS 2006
Year: 2006

We present in this paper a library to compute with Taylor models, a technique extending interval arithmetic to reduce decorrelation and to solve differential equations. Numerical software usually produces only numerical results. Our library can be used to produce both results and proofs. As seen during the development of Fermat's last theorem reported by Aczel 1996, providing a proof is not sufficient. Our library provides a proof that has been thoroughly scrutinized by a trustworthy and tireless assistant. PVS is an automatic proof assistant that has been fairly developed and used and that has no internal connection with interval arithmetic or Taylor models. We built our library so that PVS validates each result as it is produced. As producing and validating a proof, is and will certainly remain a bigger task than just producing a numerical result our library will never be a replacement to imperative implementations of Taylor models such as Cosy Infinity. Our library should mainly be used to validate small to medium size results that are involved in safety or life critical applications.
Improving the CSIEC Project and Adapting It to the English Teaching and Learning in China
Venue: arXiv cs.CY 2006
Year: 2006

In this paper after short review of the CSIEC project initialized by us in 2003 we present the continuing development and improvement of the CSIEC project in details, including the design of five new Microsoft agent characters representing different virtual chatting partners and the limitation of simulated dialogs in specific practical scenarios like graduate job application interview, then briefly analyze the actual conditions and features of its application field: web-based English education in China. Finally we introduce our efforts to adapt this system to the requirements of English teaching and learning in China and point out the work next to do.
n-Channel Entropy-Constrained Multiple-Description Lattice Vector Quantization
Venue: arXiv cs.IT 2006
Year: 2006

In this paper we derive analytical expressions for the central and side quantizers which, under high-resolutions assumptions, minimize the expected distortion of a symmetric multiple-description lattice vector quantization (MD-LVQ) system subject to entropy constraints on the side descriptions for given packet-loss probabilities. We consider a special case of the general n-channel symmetric multiple-description problem where only a single parameter controls the redundancy tradeoffs between the central and the side distortions. Previous work on two-channel MD-LVQ showed that the distortions of the side quantizers can be expressed through the normalized second moment of a sphere. We show here that this is also the case for three-channel MD-LVQ. Furthermore, we conjecture that this is true for the general n-channel MD-LVQ. For given source, target rate and packet-loss probabilities we find the optimal number of descriptions and construct the MD-LVQ system that minimizes the expected distortion. We verify theoretical expressions by numerical simulations and show in a practical setup that significant performance improvements can be achieved over state-of-the-art two-channel MD-LVQ by using three-channel MD-LVQ.
Computing Nash Equilibria: Approximation and Smoothed Complexity
Venue: arXiv cs.CC 2006
Year: 2006

We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/εcan compute an ε-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are PPAD-complete. Furthermore, we prove, unless PPAD is in RP, that the smoothed complexity of the Lemke-Howson algorithm or any algorithm for computing a Nash equilibrium of a bimatrix game is polynomial in n and 1/σunder perturbations with magnitude σ. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria.
The OverRelational Manifesto
Venue: arXiv cs.DB 2006
Year: 2006

The OverRelational Manifesto (below ORM) proposes a possible approach to creation of data storage systems of the next generation. ORM starts from the requirement that information in a relational database is represented by a set of relation values. Accordingly, it is assumed that the information about any entity of an enterprise must also be represented as a set of relation values (the ORM main requirement). A system of types is introduced, which allows one to fulfill the main requirement. The data are represented in the form of complex objects, and the state of any object is described as a set of relation values. Emphasize that the types describing the objects are encapsulated, inherited, and polymorphic. Then, it is shown that the data represented as a set of such objects may also be represented as a set of relational values defined on the set of scalar domains (dual data representation). In the general case, any class is associated with a set of relation variables (R-variables) each one containing some data about all objects of this class existing in the system. One of the key points is the fact that the usage of complex (from the user's viewpoint) refined names of R-variables and their attributes makes it possible to preserve the semantics of complex data structures represented in the form of a set of relation values. The most important part of the data storage system created on the approach proposed is an object-oriented translator operating over a relational DBMS. The expressiveness of such a system is comparable with that of OO programming languages.
Explicit Space-Time Codes Achieving The Diversity-Multiplexing Gain Tradeoff
Venue: arXiv cs.IT 2006
Year: 2006

A recent result of Zheng and Tse states that over a quasi-static channel, there exists a fundamental tradeoff, referred to as the diversity-multiplexing gain (D-MG) tradeoff, between the spatial multiplexing gain and the diversity gain that can be simultaneously achieved by a space-time (ST) block code. This tradeoff is precisely known in the case of i.i.d. Rayleigh-fading, for T>= n_t+n_r-1 where T is the number of time slots over which coding takes place and n_t,n_r are the number of transmit and receive antennas respectively. For T < n_t+n_r-1, only upper and lower bounds on the D-MG tradeoff are available. In this paper, we present a complete solution to the problem of explicitly constructing D-MG optimal ST codes, i.e., codes that achieve the D-MG tradeoff for any number of receive antennas. We do this by showing that for the square minimum-delay case when T=n_t=n, cyclic-division-algebra (CDA) based ST codes having the non-vanishing determinant property are D-MG optimal. While constructions of such codes were previously known for restricted values of n, we provide here a construction for such codes that is valid for all n. For the rectangular, T > n_t case, we present two general techniques for building D-MG-optimal rectangular ST codes from their square counterparts. A byproduct of our results establishes that the D-MG tradeoff for all T>= n_t is the same as that previously known to hold for T >= n_t + n_r -1.
D2D: Digital Archive to MPEG-21 DIDL
Venue: arXiv cs.DL 2006
Year: 2006

Digital Archive to MPEG-21 DIDL (D2D) analyzes the contents of the digital archive and produces an MPEG-21 Digital Item Declaration Language (DIDL) encapsulating the analysis results. DIDL is an extensible XML-based language that aggregates resources and the metadata. We provide a brief report on several analysis techniques applied on the digital archive by the D2D and provide an evaluation of its run-time performance.
Learning rational stochastic languages
Venue: arXiv cs.LG 2006
Year: 2006

Given a finite set of words w1,...,wn independently drawn according to a fixed unknown distribution law P called a stochastic language, an usual goal in Grammatical Inference is to infer an estimate of P in some class of probabilistic models, such as Probabilistic Automata (PA). Here, we study the class of rational stochastic languages, which consists in stochastic languages that can be generated by Multiplicity Automata (MA) and which strictly includes the class of stochastic languages generated by PA. Rational stochastic languages have minimal normal representation which may be very concise, and whose parameters can be efficiently estimated from stochastic samples. We design an efficient inference algorithm DEES which aims at building a minimal normal representation of the target. Despite the fact that no recursively enumerable class of MA computes exactly the set of rational stochastic languages over Q, we show that DEES strongly identifies tis set in the limit. We study the intermediary MA output by DEES and show that they compute rational series which converge absolutely to one and which can be used to provide stochastic languages which closely estimate the target.
Computing spectral sequences
Venue: arXiv cs.SC 2006
Year: 2006

In this paper, a set of programs enhancing the Kenzo system is presented. Kenzo is a Common Lisp program designed for computing in Algebraic Topology, in particular it allows the user to calculate homology and homotopy groups of complicated spaces. The new programs presented here entirely compute Serre and Eilenberg-Moore spectral sequences, in particular the groups and differential maps for arbitrary r. They also determine when the spectral sequence has converged and describe the filtration of the target homology groups induced by the spectral sequence.
Geographic Gossip: Efficient Aggregation for Sensor Networks
Venue: arXiv cs.IT 2006
Year: 2006

Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy $1/n^a$ using $O(n^{1.5}\sqrt{\log n})$ radio transmissions, which reduces the energy consumption by a $\sqrt{\frac{n}{\log n}}$ factor over standard gossip algorithms.
Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets
Venue: arXiv cs.IT 2006
Year: 2006

This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-size turbo stopping set which is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.
An O(n^{2.75}) algorithm for online topological ordering
Venue: arXiv cs.DS 2006
Year: 2006

We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O(min(m^{3/2} log(n), m^{3/2} + n^2 log(n)) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting. Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs.
Low-Density Parity-Check Code with Fast Decoding Speed
Venue: arXiv cs.IT 2006
Year: 2006

Low-Density Parity-Check (LDPC) codes received much attention recently due to their capacity-approaching performance. The iterative message-passing algorithm is a widely adopted decoding algorithm for LDPC codes \cite{Kschischang01}. An important design issue for LDPC codes is designing codes with fast decoding speed while maintaining capacity-approaching performance. In another words, it is desirable that the code can be successfully decoded in few number of decoding iterations, at the same time, achieves a significant portion of the channel capacity. Despite of its importance, this design issue received little attention so far. In this paper, we address this design issue for the case of binary erasure channel. We prove that density-efficient capacity-approaching LDPC codes satisfy a so called "flatness condition". We show an asymptotic approximation to the number of decoding iterations. Based on these facts, we propose an approximated optimization approach to finding the codes with good decoding speed. We further show that the optimal codes in the sense of decoding speed are "right-concentrated". That is, the degrees of check nodes concentrate around the average right degree.