OpenRaiser/Intern-Atlas huggingface dataset:
Impact of Channel Estimation Errors on Multiuser Detection via the Replica Method
Venue: arXiv cs.IT 2005
Year: 2005

For practical wireless DS-CDMA systems, channel estimation is imperfect due to noise and interference. In this paper, the impact of channel estimation errors on multiuser detection (MUD) is analyzed under the framework of the replica method. System performance is obtained in the large system limit for optimal MUD, linear MUD and turbo MUD, and is validated by numerical results for finite systems.
Under-approximation of the Greatest Fixpoints in Real-Time System Verification
Venue: arXiv cs.SE 2005
Year: 2005

Techniques for the efficient successive under-approximation of the greatest fixpoint in TCTL formulas can be useful in fast refutation of inevitability properties and vacuity checking. We first give an integrated algorithmic framework for both under and over-approximate model-checking. We design the {\em NZF (Non-Zeno Fairness) predicate}, with a greatest fixpoint formulation, as a unified framework for the evaluation of formulas like $\exists\pfrrη_1$, $\exists\pfrr\pevtη_1$, and $\exists\pevt\pfrrη_1$. We then prove the correctness of a new formulation for the characterization of the NZF predicate based on zone search and the least fixpoint evaluation. The new formulation then leads to the design of an evaluation algorithm, with the capability of successive under-approximation, for $\exists\pfrrη_1$, $\exists\pfrr\pevtη_1$, and $\exists\pevt\pfrrη_1$. We then present techniques to efficiently search for the zones and to speed up the under-approximate evaluation of those three formulas. Our experiments show that the techniques have significantly enhanced the verification performance against several benchmarks over exact model-checking.
Learning to automatically detect features for mobile robots using second-order Hidden Markov Models
Venue: arXiv cs.AI 2005
Year: 2005

In this paper, we propose a new method based on Hidden Markov Models to interpret temporal sequences of sensor data from mobile robots to automatically detect features. Hidden Markov Models have been used for a long time in pattern recognition, especially in speech recognition. Their main advantages over other methods (such as neural networks) are their ability to model noisy temporal signals of variable length. We show in this paper that this approach is well suited for interpretation of temporal sequences of mobile-robot sensor data. We present two distinct experiments and results: the first one in an indoor environment where a mobile robot learns to detect features like open doors or T-intersections, the second one in an outdoor environment where a different mobile robot has to identify situations like climbing a hill or crossing a rock.
A Statistical Theory of Chord under Churn
Venue: arXiv cs.NI 2005
Year: 2005

Most earlier studies of Distributed Hash Tables (DHTs) under churn have either depended on simulations as the primary investigation tool, or on establishing bounds for DHTs to function. In this paper, we present a complete analytical study of churn using a master-equation-based approach, used traditionally in non-equilibrium statistical mechanics to describe steady-state or transient phenomena. Simulations are used to verify all theoretical predictions. We demonstrate the application of our methodology to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately predict the fraction of failed or incorrect successor and finger pointers and show how we can use these quantities to predict the performance and consistency of lookups under churn. We also discuss briefly how churn may actually be of different 'types' and the implications this will have for the functioning of DHTs in general.
Inferring knowledge from a large semantic network
Venue: arXiv cs.AI 2005
Year: 2005

In this paper, we present a rich semantic network based on a differential analysis. We then detail implemented measures that take into account common and differential features between words. In a last section, we describe some industrial applications.
Stochastic Iterative Decoders
Venue: arXiv cs.IT 2005
Year: 2005

This paper presents a stochastic algorithm for iterative error control decoding. We show that the stochastic decoding algorithm is an approximation of the sum-product algorithm. When the code's factor graph is a tree, as with trellises, the algorithm approaches maximum a-posteriori decoding. We also demonstrate a stochastic approximations to the alternative update rule known as successive relaxation. Stochastic decoders have very simple digital implementations which have almost no RAM requirements. We present example stochastic decoders for a trellis-based Hamming code, and for a Block Turbo code constructed from Hamming codes.
Transforming Business Rules Into Natural Language Text
Venue: arXiv cs.AI 2005
Year: 2005

The aim of the project presented in this paper is to design a system for an NLG architecture, which supports the documentation process of eBusiness models. A major task is to enrich the formal description of an eBusiness model with additional information needed in an NLG task.
Transforming and Enriching Documents for the Semantic Web
Venue: arXiv cs.AI 2005
Year: 2005

We suggest to employ techniques from Natural Language Processing (NLP) and Knowledge Representation (KR) to transform existing documents into documents amenable for the Semantic Web. Semantic Web documents have at least part of their semantics and pragmatics marked up explicitly in both a machine processable as well as human readable manner. XML and its related standards (XSLT, RDF, Topic Maps etc.) are the unifying platform for the tools and methodologies developed for different application scenarios.
Directed Threshold Multi – Signature Scheme without SDC
Venue: arXiv cs.CR 2005
Year: 2005

In this paper, we propose a Directed threshold multisignature scheme without SDC. This signature scheme is applicable when the message is sensitive to the signature receiver; and the signatures are generated by the cooperation of a number of people from a given group of senders. In this scheme, any malicious set of signers cannot impersonate any other set of signers to forge the signatures. In case of forgery, it is possible to trace the signing set.
Where the Rubber Meets the Sky: Bridging the Gap between Databases and Science
Venue: arXiv cs.DB 2005
Year: 2005

Scientists in all domains face a data avalanche - both from better instruments and from improved simulations. We believe that computer science tools and computer scientists are in a position to help all the sciences by building tools and developing techniques to manage, analyze, and visualize peta-scale scientific information. This article is summarizes our experiences over the last seven years trying to bridge the gap between database technology and the needs of the astronomy community in building the World-Wide Telescope.
Stability Analysis for Regularized Least Squares Regression
Venue: arXiv cs.LG 2005
Year: 2005

We discuss stability for a class of learning algorithms with respect to noisy labels. The algorithms we consider are for regression, and they involve the minimization of regularized risk functionals, such as L(f) := 1/N sum_i (f(x_i)-y_i)^2+ lambda ||f||_H^2. We shall call the algorithm `stable' if, when y_i is a noisy version of f*(x_i) for some function f* in H, the output of the algorithm converges to f* as the regularization term and noise simultaneously vanish. We consider two flavors of this problem, one where a data set of N points remains fixed, and the other where N -> infinity. For the case where N -> infinity, we give conditions for convergence to f_E (the function which is the expectation of y(x) for each x), as lambda -> 0. For the fixed N case, we describe the limiting 'non-noisy', 'non-regularized' function f*, and give conditions for convergence. In the process, we develop a set of tools for dealing with functionals such as L(f), which are applicable to many other problems in learning theory.
Sub-Structural Niching in Non-Stationary Environments
Venue: arXiv cs.NE 2005
Year: 2005

Niching enables a genetic algorithm (GA) to maintain diversity in a population. It is particularly useful when the problem has multiple optima where the aim is to find all or as many as possible of these optima. When the fitness landscape of a problem changes overtime, the problem is called non--stationary, dynamic or time--variant problem. In these problems, niching can maintain useful solutions to respond quickly, reliably and accurately to a change in the environment. In this paper, we present a niching method that works on the problem substructures rather than the whole solution, therefore it has less space complexity than previously known niching mechanisms. We show that the method is responding accurately when environmental changes occur.
Sub-structural Niching in Estimation of Distribution Algorithms
Venue: arXiv cs.NE 2005
Year: 2005

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation of distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The proposed method consists of three key components: (1) Problem decomposition and sub-structure identification, (2) sub-structure fitness estimation, and (3) sub-structural niche preservation. The sub-structural niching method is compared to restricted tournament selection (RTS)--a niching method used in hierarchical Bayesian optimization algorithm--with special emphasis on sustained preservation of multiple global solutions of a class of boundedly-difficult, additively-separable multimodal problems. The results show that sub-structural niching successfully maintains multiple global optima over large number of generations and does so with significantly less population than RTS. Additionally, the market share of each of the niche is much closer to the expected level in sub-structural niching when compared to RTS.
On Dynamic Range Reporting in One Dimension
Venue: arXiv cs.DS 2005
Year: 2005

We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. However, for a RAM with w-bit words, we show how to perform updates in O(lg w) time and answer queries in O(lglg w) time. The update time is identical to the van Emde Boas structure, but the query time is exponentially faster. Existing lower bounds show that achieving our query time for predecessor search requires doubly-exponentially slower updates. We present some arguments supporting the conjecture that our solution is optimal. Our solution is based on a new and interesting recursion idea which is "more extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van Emde Boas-like recursion on every such path. Despite this, our algorithm is quite clean when seen from the right angle. To achieve linear space for our data structure, we solve a problem which is of independent interest. We develop the first scheme for dynamic perfect hashing requiring sublinear space. This gives a dynamic Bloomier filter (an approximate storage scheme for sparse vectors) which uses low space. We strengthen previous lower bounds to show that these results are optimal.
GF(2^m) Low-Density Parity-Check Codes Derived from Cyclotomic Cosets
Venue: arXiv cs.IT 2005
Year: 2005

Based on the ideas of cyclotomic cosets, idempotents and Mattson-Solomon polynomials, we present a new method to construct GF(2^m), where m>0 cyclic low-density parity-check codes. The construction method produces the dual code idempotent which is used to define the parity-check matrix of the low-density parity-check code. An interesting feature of this construction method is the ability to increment the code dimension by adding more idempotents and so steadily decrease the sparseness of the parity-check matrix. We show that the constructed codes can achieve performance very close to the sphere-packing-bound constrained for binary transmission.
Logarithmic Lower Bounds in the Cell-Probe Model
Venue: arXiv cs.DS 2005
Year: 2005

We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per operation for several data structural problems on n elements, including partial sums, dynamic connectivity among disjoint paths (or a forest or a graph), and several other dynamic graph problems (by simple reductions). Such a lower bound breaks a long-standing barrier of Omega(lg n / lglg n) for any dynamic language membership problem. It also establishes the optimality of several existing data structures, such as Sleator and Tarjan's dynamic trees. We also prove the first Omega(log_B n) lower bound in the external-memory model without assumptions on the data structure (such as the comparison model). Our lower bounds also give a query-update trade-off curve matched, e.g., by several data structures for dynamic connectivity in graphs. We also prove matching upper and lower bounds for partial sums when parameterized by the word size and the maximum additive change in an update.
The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties
Venue: arXiv cs.SC 2005
Year: 2005

We continue the study of counting complexity begun in [Buergisser, Cucker 04] and [Buergisser, Cucker, Lotz 05] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound of Bach (JSC 1999).
Limits of Rush Hour Logic Complexity
Venue: arXiv cs.CC 2005
Year: 2005

Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally or vertically within a parking lot. The authors show how the model supports polynomial space computation, using certain car configurations as building blocks to construct boolean circuits for a cpu and memory. They consider the use of cars of length 3 crucial to their construction, and conjecture that cars of size 2 only, which we'll call `Size 2 Rush Hour', do not support polynomial space computation. We settle this conjecture by showing that the required building blocks are constructible in Size 2 Rush Hour. Furthermore, we consider Unit Rush Hour, which was hitherto believed to be trivial, show its relation to maze puzzles, and provide empirical support for its hardness.
Batch is back: CasJobs, serving multi-TB data on the Web
Venue: arXiv cs.DC 2005
Year: 2005

The Sloan Digital Sky Survey (SDSS) science database describes over 140 million objects and is over 1.5 TB in size. The SDSS Catalog Archive Server (CAS) provides several levels of query interface to the SDSS data via the SkyServer website. Most queries execute in seconds or minutes. However, some queries can take hours or days, either because they require non-index scans of the largest tables, or because they request very large result sets, or because they represent very complex aggregations of the data. These "monster queries" not only take a long time, they also affect response times for everyone else - one or more of them can clog the entire system. To ameliorate this problem, we developed a multi-server multi-queue batch job submission and tracking system for the CAS called CasJobs. The transfer of very large result sets from queries over the network is another serious problem. Statistics suggested that much of this data transfer is unnecessary; users would prefer to store results locally in order to allow further joins and filtering. To allow local analysis, a system was developed that gives users their own personal databases (MyDB) at the server side. Users may transfer data to their MyDB, and then perform further analysis before extracting it to their own machine. MyDB tables also provide a convenient way to share results of queries with collaborators without downloading them. CasJobs is built using SOAP XML Web services and has been in operation since May 2004.
On the Achievable Information Rates of Finite-State Input Two-Dimensional Channels with Memory
Venue: arXiv cs.IT 2005
Year: 2005

The achievable information rate of finite-state input two-dimensional (2-D) channels with memory is an open problem, which is relevant, e.g., for inter-symbol-interference (ISI) channels and cellular multiple-access channels. We propose a method for simulation-based computation of such information rates. We first draw a connection between the Shannon-theoretic information rate and the statistical mechanics notion of free energy. Since the free energy of such systems is intractable, we approximate it using the cluster variation method, implemented via generalized belief propagation. The derived, fully tractable, algorithm is shown to provide a practically accurate estimate of the information rate. In our experimental study we calculate the information rates of 2-D ISI channels and of hexagonal Wyner cellular networks with binary inputs, for which formerly only bounds were known.
Sensor Configuration and Activation for Field Detection in Large Sensor Arrays
Venue: arXiv cs.IT 2005
Year: 2005

The problems of sensor configuration and activation for the detection of correlated random fields using large sensor arrays are considered. Using results that characterize the large-array performance of sensor networks in this application, the detection capabilities of different sensor configurations are analyzed and compared. The dependence of the optimal choice of configuration on parameters such as sensor signal-to-noise ratio (SNR), field correlation, etc., is examined, yielding insights into the most effective choices for sensor selection and activation in various operating regimes.
An Audit Logic for Accountability
Venue: arXiv cs.CR 2005
Year: 2005

We describe and implement a policy language. In our system, agents can distribute data along with usage policies in a decentralized architecture. Our language supports the specification of conditions and obligations, and also the possibility to refine policies. In our framework, the compliance with usage policies is not actively enforced. However, agents are accountable for their actions, and may be audited by an authority requiring justifications.
Online Permutation Routing in Partitioned Optical Passive Star Networks
Venue: arXiv cs.DC 2005
Year: 2005

This paper establishes the state of the art in both deterministic and randomized online permutation routing in the POPS network. Indeed, we show that any permutation can be routed online on a POPS network either with $O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with $5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant $c=\exp (1+e^{-1})\approx 3.927$. When $d=Θ(g)$, that we claim to be the "interesting" case, the randomized algorithm is exponentially faster than any other algorithm in the literature, both deterministic and randomized ones. This is true in practice as well. Indeed, experiments show that it outperforms its rivals even starting from as small a network as a POPS(2,2), and the gap grows exponentially with the size of the network. We can also show that, under proper hypothesis, no deterministic algorithm can asymptotically match its performance.
Coalition Formation: Concessions, Task Relationships and Complexity Reduction
Venue: arXiv cs.MA 2005
Year: 2005

Solutions to the coalition formation problem commonly assume agent rationality and, correspondingly, utility maximization. This in turn may prevent agents from making compromises. As shown in recent studies, compromise may facilitate coalition formation and increase agent utilities. In this study we leverage on those new results. We devise a novel coalition formation mechanism that enhances compromise. Our mechanism can utilize information on task dependencies to reduce formation complexity. Further, it works well with both cardinal and ordinal task values. Via experiments we show that the use of the suggested compromise-based coalition formation mechanism provides significant savings in the computation and communication complexity of coalition formation. Our results also show that when information on task dependencies is used, the complexity of coalition formation is further reduced. We demonstrate successful use of the mechanism for collaborative information filtering, where agents combine linguistic rules to analyze documents' contents.
Top-Down Unsupervised Image Segmentation (it sounds like oxymoron, but actually it is not)
Venue: arXiv cs.CV 2005
Year: 2005

Pattern recognition is generally assumed as an interaction of two inversely directed image-processing streams: the bottom-up information details gathering and localization (segmentation) stream, and the top-down information features aggregation, association and interpretation (recognition) stream. Inspired by recent evidence from biological vision research and by the insights of Kolmogorov Complexity theory, we propose a new, just top-down evolving, procedure of initial image segmentation. We claim that traditional top-down cognitive reasoning, which is supposed to guide the segmentation process to its final result, is not at all a part of the image information content evaluation. And that initial image segmentation is certainly an unsupervised process. We present some illustrative examples, which support our claims.
Local and Global Analysis: Complementary Activities for Increasing the Effectiveness of Requirements Verification and Validation
Venue: arXiv cs.SE 2005
Year: 2005

This paper presents a unique approach to connecting requirements engineering (RE) activities into a process framework that can be employed to obtain quality requirements with reduced expenditures of effort and cost. We propose a two-phase model that is novel in that it introduces the concept of verification and validation (V&V) early in the requirements life cycle. In the first phase, we perform V&V immediately following the elicitation of requirements for each individually distinct system function. Because the first phase focuses on capturing smaller sets of related requirements iteratively, each corresponding V&V activity is better focused for detecting and correcting errors in each requirement set. In the second phase, a complementary verification activity is initiated; the corresponding focus is on the quality of linkages between requirements sets rather than on the requirements within the sets. Consequently, this approach reduces the effort in verification and enhances the focus on the verification task. Our approach, unlike other models, has a minimal time delay between the elicitation of requirements and the execution of the V&V activities. Because of this short time gap, the stakeholders have a clearer recollection of the requirements, their context and rationale; this enhances the stakeholder feedback. Furthermore, our model includes activities that closely align with the effective RE processes employed in the software industry. Thus, our approach facilitates a better understanding of the flow of requirements, and provides guidance for the implementation of the RE process.