OpenRaiser/Intern-Atlas huggingface dataset:
The Noncoherent Rician Fading Channel -- Part I : Structure of the Capacity-Achieving Input
Venue: arXiv cs.IT 2005
Year: 2005

Transmission of information over a discrete-time memoryless Rician fading channel is considered where neither the receiver nor the transmitter knows the fading coefficients. First the structure of the capacity-achieving input signals is investigated when the input is constrained to have limited peakedness by imposing either a fourth moment or a peak constraint. When the input is subject to second and fourth moment limitations, it is shown that the capacity-achieving input amplitude distribution is discrete with a finite number of mass points in the low-power regime. A similar discrete structure for the optimal amplitude is proven over the entire SNR range when there is only a peak power constraint. The Rician fading with phase-noise channel model, where there is phase uncertainty in the specular component, is analyzed. For this model it is shown that, with only an average power constraint, the capacity-achieving input amplitude is discrete with a finite number of levels. For the classical average power limited Rician fading channel, it is proven that the optimal input amplitude distribution has bounded support.
Geometric Complexity III: on deciding positivity of Littlewood-Richardson coefficients
Venue: arXiv cs.CC 2005
Year: 2005

We point out that the remarkable Knutson and Tao Saturation Theorem and polynomial time algorithms for LP have together an important and immediate consequence in Geometric Complexity Theory. The problem of deciding positivity of Littlewood-Richardson coefficients for GLn(C) belongs to P. Furthermore, the algorithm is strongly polynomial. The main goal of this article is to explain the significance of this result in the context of Geometric Complexity Theory. Furthermore, it is also conjectured that an analogous result holds for arbitrary symmetrizable Kac-Moody algebras.
Clever Search: A WordNet Based Wrapper for Internet Search Engines
Venue: arXiv cs.AI 2005
Year: 2005

This paper presents an approach to enhance search engines with information about word senses available in WordNet. The approach exploits information about the conceptual relations within the lexical-semantic net. In the wrapper for search engines presented, WordNet information is used to specify user's request or to classify the results of a publicly available web search engine, like google, yahoo, etc.
TerraServer SAN-Cluster Architecture and Operations Experience
Venue: arXiv cs.DC 2005
Year: 2005

Microsoft TerraServer displays aerial, satellite, and to-pographic images of the earth in a SQL database available via the Internet. It is one of the most popular online at-lases, presenting seventeen terabytes of image data from the United States Geological Survey (USGS). Initially de-ployed in 1998, the system demonstrated the scalability of PC hardware and software - Windows and SQL Server - on a single, mainframe-class processor. In September 2000, the back-end database application was migrated to 4-node active/passive cluster connected to an 18 terabyte Storage Area Network (SAN). The new configuration was designed to achieve 99.99% availability for the back-end application. This paper describes the hardware and software components of the TerraServer Cluster and SAN, and describes our experience in configuring and operating this system for three years. Not surprisingly, the hardware and architecture delivered better than four-9's of availability, but operations mistakes delivered three-9's.
Can Computer Algebra be Liberated from its Algebraic Yoke ?
Venue: arXiv cs.SC 2005
Year: 2005

So far, the scope of computer algebra has been needlessly restricted to exact algebraic methods. Its possible extension to approximate analytical methods is discussed. The entangled roles of functional analysis and symbolic programming, especially the functional and transformational paradigms, are put forward. In the future, algebraic algorithms could constitute the core of extended symbolic manipulation systems including primitives for symbolic approximations.
A Price-Anticipating Resource Allocation Mechanism for Distributed Shared Clusters
Venue: arXiv cs.DC 2005
Year: 2005

In this paper we formulate the fixed budget resource allocation game to understand the performance of a distributed market-based resource allocation system. Multiple users decide how to distribute their budget (bids) among multiple machines according to their individual preferences to maximize their individual utility. We look at both the efficiency and the fairness of the allocation at the equilibrium, where fairness is evaluated through the measures of utility uniformity and envy-freeness. We show analytically and through simulations that despite being highly decentralized, such a system converges quickly to an equilibrium and unlike the social optimum that achieves high efficiency but poor fairness, the proposed allocation scheme achieves a nice balance of high degrees of efficiency and fairness at the equilibrium.
Proof obligations for specification and refinement of liveness properties under weak fairness
Venue: arXiv cs.LO 2005
Year: 2005

In this report, we present a formal model of fair iteration of events for B event systems. The model is used to justify proof obligations for basic liveness properties and preservation under refinement of general liveness properties. The model of fair iteration of events uses the dovetail operator, an operator proposed by Broy and Nelson to model fair choice. The proofs are mainly founded in fixpoint calculations of fair iteration of events and weakest precondition calculus.
Generalised Bent Criteria for Boolean Functions (II)
Venue: arXiv cs.IT 2005
Year: 2005

In the first part of this paper [16], some results on how to compute the flat spectra of Boolean constructions w.r.t. the transforms {I,H}^n, {H,N}^n and {I,H,N}^n were presented, and the relevance of Local Complementation to the quadratic case was indicated. In this second part, the results are applied to develop recursive formulae for the numbers of flat spectra of some structural quadratics. Observations are made as to the generalised Bent properties of boolean functions of algebraic degree greater than two, and the number of flat spectra w.r.t. {I,H,N}^n are computed for some of them.
A Semantic Grid-based E-Learning Framework (SELF)
Venue: arXiv cs.DC 2005
Year: 2005

E-learning can be loosely defined as a wide set of applications and processes, which uses available electronic media (and tools) to deliver vocational education and training. With its increasing recognition as an ubiquitous mode of instruction and interaction in the academic as well as corporate world, the need for a scaleable and realistic model is becoming important. In this paper we introduce SELF; a Semantic grid-based E-Learning Framework. SELF aims to identify the key-enablers in a practical grid-based E-learning environment and to minimize technological reworking by proposing a well-defined interaction plan among currently available tools and technologies. We define a dichotomy with E-learning specific application layers on top and semantic grid-based support layers underneath. We also map the latest open and freeware technologies with various components in SELF.
Perspectives for Strong Artificial Life
Venue: arXiv cs.AI 2005
Year: 2005

This text introduces the twin deadlocks of strong artificial life. Conceptualization of life is a deadlock both because of the existence of a continuum between the inert and the living, and because we only know one instance of life. Computationalism is a second deadlock since it remains a matter of faith. Nevertheless, artificial life realizations quickly progress and recent constructions embed an always growing set of the intuitive properties of life. This growing gap between theory and realizations should sooner or later crystallize in some kind of paradigm shift and then give clues to break the twin deadlocks.
Koordinatenfreies Lokationsbewusstsein (Localization without Coordinates)
Venue: arXiv cs.DC 2005
Year: 2005

Localization is one of the fundamental issues in sensor networks. It is almost always assumed that it must be solved by assigning coordinates to the nodes. This article discusses positioning algorithms from a theoretical, practical and simulative point of view, and identifies difficulties and limitations. Ideas for more abstract means of location awareness are presented and the resulting possible improvements for applications are shown. Nodes with certain topological or environmental properties are clustered, and the neighborhood structure of the clusters is modeled as a graph. Eines der fundamentalen Probleme in Sensornetzwerken besteht darin, ein Bewusstsein fuer die Position eines Knotens im Netz zu entwickeln. Dabei wird fast immer davon ausgegangen, dass dies durch die Zuweisung von Koordinaten zu erfolgen hat. In diesem Artikel wird auf theoretischer, praktischer und simulativer Ebene ein kritischer Blick auf entsprechende Verfahren geworfen, und es werden Grenzen aufgezeigt. Es wird ein Ansatz vorgestellt, mit dem in der Zukunft eine abstrakte Form von Lokationsbewusstsein etabliert werden kann, und es wird gezeigt, wie Anwendungen dadurch verbessert werden koennen. Er basiert auf einer graphenbasierten Modellierung des Netzes: Knoten mit bestimmten topologischen oder Umwelteigenschaften werden zu Clustern zusammengefasst, und Clusternachbarschaften dann als Graphen modelliert.
Semantical Characterizations and Complexity of Equivalences in Answer Set Programming
Venue: arXiv cs.AI 2005
Year: 2005

In recent research on non-monotonic logic programming, repeatedly strong equivalence of logic programs P and Q has been considered, which holds if the programs P union R and Q union R have the same answer sets for any other program R. This property strengthens equivalence of P and Q with respect to answer sets (which is the particular case for R is the empty set), and has its applications in program optimization, verification, and modular logic programming. In this paper, we consider more liberal notions of strong equivalence, in which the actual form of R may be syntactically restricted. On the one hand, we consider uniform equivalence, where R is a set of facts rather than a set of rules. This notion, which is well known in the area of deductive databases, is particularly useful for assessing whether programs P and Q are equivalent as components of a logic program which is modularly structured. On the other hand, we consider relativized notions of equivalence, where R ranges over rules over a fixed alphabet, and thus generalize our results to relativized notions of strong and uniform equivalence. For all these notions, we consider disjunctive logic programs in the propositional (ground) case, as well as some restricted classes, provide semantical characterizations and analyze the computational complexity. Our results, which naturally extend to answer set semantics for programs with strong negation, complement the results on strong equivalence of logic programs and pave the way for optimizations in answer set solvers as a tool for input-based problem solving.
Toward alternative metrics of journal impact: A comparison of download and citation data
Venue: arXiv cs.DL 2005
Year: 2005

We generated networks of journal relationships from citation and download data, and determined journal impact rankings from these networks using a set of social network centrality metrics. The resulting journal impact rankings were compared to the ISI IF. Results indicate that, although social network metrics and ISI IF rankings deviate moderately for citation-based journal networks, they differ considerably for journal networks derived from download data. We believe the results represent a unique aspect of general journal impact that is not captured by the ISI IF. These results furthermore raise questions regarding the validity of the ISI IF as the sole assessment of journal impact, and suggest the possibility of devising impact metrics based on usage information in general.
Probabilistic Algorithmic Knowledge
Venue: arXiv cs.AI 2005
Year: 2005

The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning ``Yes'' to a query about a fact ϕprovides evidence for ϕbeing true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.
Authentication with Distortion Criteria
Venue: arXiv cs.IT 2005
Year: 2005

In a variety of applications, there is a need to authenticate content that has experienced legitimate editing in addition to potential tampering attacks. We develop one formulation of this problem based on a strict notion of security, and characterize and interpret the associated information-theoretic performance limits. The results can be viewed as a natural generalization of classical approaches to traditional authentication. Additional insights into the structure of such systems and their behavior are obtained by further specializing the results to Bernoulli and Gaussian cases. The associated systems are shown to be substantially better in terms of performance and/or security than commonly advocated approaches based on data hiding and digital watermarking. Finally, the formulation is extended to obtain efficient layered authentication system constructions.
Timed Analysis of Security Protocols
Venue: arXiv cs.CR 2005
Year: 2005

We propose a method for engineering security protocols that are aware of timing aspects. We study a simplified version of the well-known Needham Schroeder protocol and the complete Yahalom protocol, where timing information allows the study of different attack scenarios. We model check the protocols using UPPAAL. Further, a taxonomy is obtained by studying and categorising protocols from the well known Clark Jacob library and the Security Protocol Open Repository (SPORE) library. Finally, we present some new challenges and threats that arise when considering time in the analysis, by providing a novel protocol that uses time challenges and exposing a timing attack over an implementation of an existing security protocol.
Systematic Method for Path-Complete White Box Testing
Venue: arXiv cs.SE 2005
Year: 2005

A systematic, language-independent method of finding a minimal set of paths covering the code of a sequential program is proposed for application in White Box testing. Execution of all paths from the set ensures also statement coverage. Execution fault marks problematic areas of the code. The method starts from a UML activity diagram of a program. The diagram is transformed into a directed graph: graph's nodes substitute decision and action points; graph's directed edges substitute action arrows. The number of independent paths equals easy-to-compute cyclomatic complexity of the graph. Association of a vector to each path creates a path vector space. Independence of the paths is equivalent to linear independence of the vectors. It is sufficient to test any base of the path space to complete the procedure. An effective algorithm for choosing the base paths is presented.
On the Stopping Distance and the Stopping Redundancy of Codes
Venue: arXiv cs.IT 2005
Year: 2005

It is now well known that the performance of a linear code $C$ under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for $C$. Several recent papers refer to this parameter as the \emph{stopping distance} $s$ of $C$. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for $C$ depends on the corresponding choice of a parity-check matrix. It is easy to see that $s \le d$, where $d$ is the minimum Hamming distance of $C$, and we show that it is always possible to choose a parity-check matrix for $C$ (with sufficiently many dependent rows) such that $s = d$. We thus introduce a new parameter, termed the \emph{stopping redundancy} of $C$, defined as the minimum number of rows in a parity-check matrix $H$ for $C$ such that the corresponding stopping distance $s(H)$ attains its largest possible value, namely $s(H) = d$. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 35 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.
A Survey of Reverse Engineering and Program Comprehension
Venue: arXiv cs.SE 2005
Year: 2005

Reverse engineering has been a standard practice in the hardware community for some time. It has only been within the last ten years that reverse engineering, or "program comprehension", has grown into the current sub-discipline of software engineering. Traditional software engineering is primarily focused on the development and design of new software. However, most programmers work on software that other people have designed and developed. Up to 50% of a software maintainers time can be spent determining the intent of source code. The growing demand to reevaluate and reimplement legacy software systems, brought on by the proliferation of clientserver and World Wide Web technologies, has underscored the need for reverse engineering tools and techniques. This paper introduces the terminology of reverse engineering and gives some of the obstacles that make reverse engineering difficult. Although reverse engineering remains heavily dependent on the human component, a number of automated tools are presented that aid the reverse engineer.
Distributed Learning in Wireless Sensor Networks
Venue: arXiv cs.IT 2005
Year: 2005

The problem of distributed or decentralized detection and estimation in applications such as wireless sensor networks has often been considered in the framework of parametric models, in which strong assumptions are made about a statistical description of nature. In certain applications, such assumptions are warranted and systems designed from these models show promise. However, in other scenarios, prior knowledge is at best vague and translating such knowledge into a statistical model is undesirable. Applications such as these pave the way for a nonparametric study of distributed detection and estimation. In this paper, we review recent work of the authors in which some elementary models for distributed learning are considered. These models are in the spirit of classical work in nonparametric statistics and are applicable to wireless sensor networks.
A File System Abstraction for Sense and Respond Systems
Venue: arXiv cs.NI 2005
Year: 2005

The heterogeneity and resource constraints of sense-and-respond systems pose significant challenges to system and application development. In this paper, we present a flexible, intuitive file system abstraction for organizing and managing sense-and-respond systems based on the Plan 9 design principles. A key feature of this abstraction is the ability to support multiple views of the system via filesystem namespaces. Constructed logical views present an application-specific representation of the network, thus enabling high-level programming of the network. Concurrently, structural views of the network enable resource-efficient planning and execution of tasks. We present and motivate the design using several examples, outline research challenges and our research plan to address them, and describe the current state of implementation.
A new SISO algorithm with application to turbo equalization
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we propose a new soft-input soft-output equalization algorithm, offering very good performance/complexity tradeoffs. It follows the structure of the BCJR algorithm, but dynamically constructs a simplified trellis during the forward recursion. In each trellis section, only the M states with the strongest forward metric are preserved, similar to the M-BCJR algorithm. Unlike the M-BCJR, however, the remaining states are not deleted, but rather merged into the surviving states. The new algorithm compares favorably with the reduced-state BCJR algorithm, offering better performance and more flexibility, particularly for systems with higher order modulations.
The Viterbi Algorithm: A Personal History
Venue: arXiv cs.IT 2005
Year: 2005

The story of the Viterbi algorithm (VA) is told from a personal perspective. Applications both within and beyond communications are discussed. In brief summary, the VA has proved to be an extremely important algorithm in a surprising variety of fields.
A Matter of Opinion: Sentiment Analysis and Business Intelligence (position paper)
Venue: arXiv cs.CL 2005
Year: 2005

A general-audience introduction to the area of "sentiment analysis", the computational treatment of subjective, opinion-oriented language (an example application is determining whether a review is "thumbs up" or "thumbs down"). Some challenges, applications to business-intelligence tasks, and potential future directions are described.
Convexity Analysis of Snake Models Based on Hamiltonian Formulation
Venue: arXiv cs.CV 2005
Year: 2005

This paper presents a convexity analysis for the dynamic snake model based on the Potential Energy functional and the Hamiltonian formulation of the classical mechanics. First we see the snake model as a dynamical system whose singular points are the borders we seek. Next we show that a necessary condition for a singular point to be an attractor is that the energy functional is strictly convex in a neighborhood of it, that means, if the singular point is a local minimum of the potential energy. As a consequence of this analysis, a local expression relating the dynamic parameters and the rate of convergence arises. Such results link the convexity analysis of the potential energy and the dynamic snake model and point forward to the necessity of a physical quantity whose convexity analysis is related to the dynamic and which incorporate the velocity space. Such a quantity is exactly the (conservative) Hamiltonian of the system.
Polynomial Neural Networks Learnt to Classify EEG Signals
Venue: arXiv cs.NE 2005
Year: 2005

A neural network based technique is presented, which is able to successfully extract polynomial classification rules from labeled electroencephalogram (EEG) signals. To represent the classification rules in an analytical form, we use the polynomial neural networks trained by a modified Group Method of Data Handling (GMDH). The classification rules were extracted from clinical EEG data that were recorded from an Alzheimer patient and the sudden death risk patients. The third data is EEG recordings that include the normal and artifact segments. These EEG data were visually identified by medical experts. The extracted polynomial rules verified on the testing EEG data allow to correctly classify 72% of the risk group patients and 96.5% of the segments. These rules performs slightly better than standard feedforward neural networks.