OpenRaiser/Intern-Atlas huggingface dataset:
Summarizing Reports on Evolving Events; Part I: Linear Evolution
Venue: arXiv cs.CL 2005
Year: 2005

We present an approach for summarization from multiple documents which report on events that evolve through time, taking into account the different document sources. We distinguish the evolution of an event into linear and non-linear. According to our approach, each document is represented by a collection of messages which are then used in order to instantiate the cross-document relations that determine the summary content. The paper presents the summarization system that implements this approach through a case study on linear evolution.
Performance of PPM Multipath Synchronization in the Limit of Large Bandwidth
Venue: arXiv cs.IT 2005
Year: 2005

The acquisition, or synchronization, of the multipath profile for an ultrawideband pulse position modulation (PPM) communication systems is considered. Synchronization is critical for the proper operation of PPM based For the multipath channel, it is assumed that channel gains are known, but path delays are unknown. In the limit of large bandwidth, W, it is assumed that the number of paths, L, grows. The delay spread of the channel, M, is proportional to the bandwidth. The rate of growth of L versus M determines whether synchronization can occur. It is shown that if L/sqrt(M) --> 0, then the maximum likelihood synchronizer cannot acquire any of the paths and alternatively if L/M --> 0, the maximum likelihood synchronizer is guaranteed to miss at least one path.
On Multiple User Channels with Causal State Information at the Transmitters
Venue: arXiv cs.IT 2005
Year: 2005

We extend Shannon's result on the capacity of channels with state information to multiple user channels. More specifically, we characterize the capacity (region) of degraded broadcast channels and physically degraded relay channels where the channel state information is causally available at the transmitters. We also obtain inner and outer bounds on the capacity region for multiple access channels with causal state information at the transmitters.
An Explicit Construction of Universally Decodable Matrices
Venue: arXiv cs.IT 2005
Year: 2005

Universally decodable matrices can be used for coding purposes when transmitting over slow fading channels. These matrices are parameterized by positive integers $L$ and $n$ and a prime power $q$. Based on Pascal's triangle we give an explicit construction of universally decodable matrices for any non-zero integers $L$ and $n$ and any prime power $q$ where $L \leq q+1$. This is the largest set of possible parameter values since for any list of universally decodable matrices the value $L$ is upper bounded by $q+1$, except for the trivial case $n = 1$. For the proof of our construction we use properties of Hasse derivatives, and it turns out that our construction has connections to Reed-Solomon codes, Reed-Muller codes, and so-called repeated-root cyclic codes. Additionally, we show how universally decodable matrices can be modified so that they remain universally decodable matrices.
A primer on Answer Set Programming
Venue: arXiv cs.AI 2005
Year: 2005

A introduction to the syntax and Semantics of Answer Set Programming intended as an handout to [under]graduate students taking Artificial Intlligence or Logic Programming classes.
Proving or Disproving likely Invariants with Constraint Reasoning
Venue: arXiv cs.SE 2005
Year: 2005

A program invariant is a property that holds for every execution of the program. Recent work suggest to infer likely-only invariants, via dynamic analysis. A likely invariant is a property that holds for some executions but is not guaranteed to hold for all executions. In this paper, we present work in progress addressing the challenging problem of automatically verifying that likely invariants are actual invariants. We propose a constraint-based reasoning approach that is able, unlike other approaches, to both prove or disprove likely invariants. In the latter case, our approach provides counter-examples. We illustrate the approach on a motivating example where automatically generated likely invariants are verified.
A Family of Binary Sequences with Optimal Correlation Property and Large Linear Span
Venue: arXiv cs.CR 2005
Year: 2005

A family of binary sequences is presented and proved to have optimal correlation property and large linear span. It includes the small set of Kasami sequences, No sequence set and TN sequence set as special cases. An explicit lower bound expression on the linear span of sequences in the family is given. With suitable choices of parameters, it is proved that the family has exponentially larger linear spans than both No sequences and TN sequences. A class of ideal autocorrelation sequences is also constructed and proved to have large linear span.
Quantum Algorithm Processors to Reveal Hamiltonian Cycles
Venue: arXiv cs.AR 2005
Year: 2005

Quantum computer versus quantum algorithm processor in CMOS are compared to find (in parallel) all Hamiltonian cycles in a graph with m edges and n vertices, each represented by k bits. A quantum computer uses quantum states analogous to CMOS registers. With efficient initialization, number of CMOS registers is proportional to (n-1)! Number of qubits in a quantum computer is approximately proportional to kn+2mn in the approach below. Using CMOS, the bits per register is about proportional to kn, which is less since bits can be irreversibly reset. In either concept, number of gates, or operations to identify Hamiltonian cycles is proportional to kmn. However, a quantum computer needs an additional exponentially large number of operations to accomplish a probabilistic readout. In contrast, CMOS is deterministic and readout is comparable to ordinary memory.
Iterative Algorithm for Finding Frequent Patterns in Transactional Databases
Venue: arXiv cs.DB 2005
Year: 2005

A high-performance algorithm for searching for frequent patterns (FPs) in transactional databases is presented. The search for FPs is carried out by using an iterative sieve algorithm by computing the set of enclosed cycles. In each inner cycle of level FPs composed of elements are generated. The assigned number of enclosed cycles (the parameter of the problem) defines the maximum length of the desired FPs. The efficiency of the algorithm is produced by (i) the extremely simple logical searching scheme, (ii) the avoidance of recursive procedures, and (iii) the usage of only one-dimensional arrays of integers.
Temporal Phylogenetic Networks and Logic Programming
Venue: arXiv cs.LO 2005
Year: 2005

The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages. To appear in Theory and Practice of Logic Programming (TPLP).
The Throughput-Reliability Tradeoff in MIMO Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, an outage limited MIMO channel is considered. We build on Zheng and Tse's elegant formulation of the diversity-multiplexing tradeoff to develop a better understanding of the asymptotic relationship between the probability of error, transmission rate, and signal-to-noise ratio. In particular, we identify the limitation imposed by the multiplexing gain notion and develop a new formulation for the throughput-reliability tradeoff that avoids this limitation. The new characterization is then used to elucidate the asymptotic trends exhibited by the outage probability curves of MIMO channels.
Sampling to estimate arbitrary subset sums
Venue: arXiv cs.DS 2005
Year: 2005

Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpose, we propose priority sampling which tested on Internet data performed better than previous methods by orders of magnitude. Priority sampling is simple to define and implement: we consider a steam of items i=0,...,n-1 with weights w_i. For each item i, we generate a random number r_i in (0,1) and create a priority q_i=w_i/r_i. The sample S consists of the k highest priority items. Let t be the (k+1)th highest priority. Each sampled item i in S gets a weight estimate W_i=max{w_i,t}, while non-sampled items get weight estimate W_i=0. Magically, it turns out that the weight estimates are unbiased, that is, E[W_i]=w_i, and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and surpricingly, there is no co-variance between different weight estimates W_i and W_j. We conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased estimators that gets smaller total variance than priority sampling with k+1 items. Very recently Mario Szegedy has settled this conjecture.
Efficient Reconciliation of Correlated Continuous Random Variables using LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

This paper investigates an efficient and practical information reconciliation method in the case where two parties have access to correlated continuous random variables. We show that reconciliation is a special case of channel coding and that existing coded modulation techniques can be adapted for reconciliation. We describe an explicit reconciliation method based on LDPC codes in the case of correlated Gaussian variables. We believe that the proposed method can improve the efficiency of quantum key distribution protocols based on continuous-spectrum quantum states.
Computing over the Reals: Foundations for Scientific Computing
Venue: arXiv cs.CC 2005
Year: 2005

We give a detailed treatment of the ``bit-model'' of computability and complexity of real functions and subsets of R^n, and argue that this is a good way to formalize many problems of scientific computation. In the introduction we also discuss the alternative Blum-Shub-Smale model. In the final section we discuss the issue of whether physical systems could defeat the Church-Turing Thesis.
Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the Binary Erasure Channel Capacity with Bounded Complexity
Venue: arXiv cs.IT 2005
Year: 2005

The paper introduces ensembles of accumulate-repeat-accumulate (ARA) codes which asymptotically achieve capacity on the binary erasure channel (BEC) with {\em bounded complexity} per information bit. It also introduces symmetry properties which play a central role in the construction of capacity-achieving ensembles for the BEC. The results here improve on the tradeoff between performance and complexity provided by the first capacity-achieving ensembles of irregular repeat-accumulate (IRA) codes with bounded complexity per information bit; these IRA ensembles were previously constructed by Pfister, Sason and Urbanke. The superiority of ARA codes with moderate to large block length is exemplified by computer simulations which compare their performance with those of previously reported capacity-achieving ensembles of LDPC and IRA codes. The ARA codes also have the advantage of being systematic.
Channel Uncertainty in Ultra Wideband Communication Systems
Venue: arXiv cs.IT 2005
Year: 2005

Wide band systems operating over multipath channels may spread their power over bandwidth if they use duty cycle. Channel uncertainty limits the achievable data rates of power constrained wide band systems; Duty cycle transmission reduces the channel uncertainty because the receiver has to estimate the channel only when transmission takes place. The optimal choice of the fraction of time used for transmission depends on the spectral efficiency of the signal modulation. The general principle is demonstrated by comparing the channel conditions that allow different modulations to achieve the capacity in the limit. Direct sequence spread spectrum and pulse position modulation systems with duty cycle achieve the channel capacity, if the increase of the number of channel paths with the bandwidth is not too rapid. The higher spectral efficiency of the spread spectrum modulation lets it achieve the channel capacity in the limit, in environments where pulse position modulation with non-vanishing symbol time cannot be used because of the large number of channel paths.
Folksonomy as a Complex Network
Venue: arXiv cs.IR 2005
Year: 2005

Folksonomy is an emerging technology that works to classify the information over WWW through tagging the bookmarks, photos or other web-based contents. It is understood to be organized by every user while not limited to the authors of the contents and the professional editors. This study surveyed the folksonomy as a complex network. The result indicates that the network, which is composed of the tags from the folksonomy, displays both properties of small world and scale-free. However, the statistics only shows a local and static slice of the vast body of folksonomy which is still evolving.
Representing Digital Assets for Long-Term Preservation using MPEG-21 DID
Venue: arXiv cs.DL 2005
Year: 2005

Various efforts aimed at representing digital assets have emerged from several communities over the last years, including the Metadata Encoding and Transmission Standard (METS), the IMS Content Packaging (IMS-CP) XML Binding and the XML Formatted Data Units (XFDU). The MPEG-21 Digital Item Declaration (MPEG-21 DID) is another approach that can be used for the representation of digital assets in XML. This paper will explore the potential of the MPEG-21 DID in a Digital Preservation context, by looking at the core building blocks of the OAIS Information Model and the way in which they map to the MPEG-21 DID abstract model and the MPEG-21 DIDL XML syntax.
Access Interfaces for Open Archival Information Systems based on the OAI-PMH and the OpenURL Framework for Context-Sensitive Services
Venue: arXiv cs.DL 2005
Year: 2005

In recent years, a variety of digital repository and archival systems have been developed and adopted. All of these systems aim at hosting a variety of compound digital assets and at providing tools for storing, managing and accessing those assets. This paper will focus on the definition of common and standardized access interfaces that could be deployed across such diverse digital respository and archival systems. The proposed interfaces are based on the two formal specifications that have recently emerged from the Digital Library community: The Open Archive Initiative Protocol for Metadata Harvesting (OAI-PMH) and the NISO OpenURL Framework for Context-Sensitive Services (OpenURL Standard). As will be described, the former allows for the retrieval of batches of XML-based representations of digital assets, while the latter facilitates the retrieval of disseminations of a specific digital asset or of one or more of its constituents. The core properties of the proposed interfaces are explained in terms of the Reference Model for an Open Archival Information System (OAIS).
Telling Great Stories: An NSDL Content and Communications System for Aggregation, Display, and Distribution of News and Features
Venue: arXiv cs.DL 2005
Year: 2005

Education digital libraries contain cataloged resources as well as contextual information about innovations in the use of educational technology, exemplar stories about community activities, and news from various user communities that include teachers, students, scholars, and developers. Long-standing library traditions of service, preservation, democratization of knowledge, rich discourse, equal access, and fair use are evident in library communications models that both pull in and push out contextual information from multiple sources integrated with editorial production processes. This paper argues that a dynamic narrative flow [1] is enabled by effective management of complex content and communications in a decentralized web-based education digital library making publishing objects such as aggregations of resources, or selected parts of objects [4] accessible through a Content and Communications System. Providing services that encourage patrons to reuse, reflect out, and contribute resources back [5] to the Library increases the reach and impact of the National Science Digital Library (NSDL). This system is a model for distributed content development and effective communications for education digital libraries in general.
Iterative Algebraic Soft-Decision List Decoding of Reed-Solomon Codes
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon codes offering both complexity and performance advantages over previously known decoding algorithms. Our algorithm is a list decoding algorithm which combines two powerful soft decision decoding techniques which were previously regarded in the literature as competitive, namely, the Koetter-Vardy algebraic soft-decision decoding algorithm and belief-propagation based on adaptive parity check matrices, recently proposed by Jiang and Narayanan. Building on the Jiang-Narayanan algorithm, we present a belief-propagation based algorithm with a significant reduction in computational complexity. We introduce the concept of using a belief-propagation based decoder to enhance the soft-input information prior to decoding with an algebraic soft-decision decoder. Our algorithm can also be viewed as an interpolation multiplicity assignment scheme for algebraic soft-decision decoding of Reed-Solomon codes.
Sur le statut référentiel des entités nommées
Venue: arXiv cs.AI 2005
Year: 2005

We show in this paper that, on the one hand, named entities can be designated using different denominations and that, on the second hand, names denoting named entities are polysemous. The analysis cannot be limited to reference resolution but should take into account naming strategies, which are mainly based on two linguistic operations: synecdoche and metonymy. Lastly, we present a model that explicitly represents the different denominations in discourse, unifying the way to represent linguistic knowledge and world knowledge.
Conditionally independent random variables
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we investigate the notion of conditional independence and prove several information inequalities for conditionally independent random variables.
Semantic Optimization Techniques for Preference Queries
Venue: arXiv cs.DB 2005
Year: 2005

Preference queries are relational algebra or SQL queries that contain occurrences of the winnow operator ("find the most preferred tuples in a given relation"). Such queries are parameterized by specific preference relations. Semantic optimization techniques make use of integrity constraints holding in the database. In the context of semantic optimization of preference queries, we identify two fundamental properties: containment of preference relations relative to integrity constraints and satisfaction of order axioms relative to integrity constraints. We show numerous applications of those notions to preference query evaluation and optimization. As integrity constraints, we consider constraint-generating dependencies, a class generalizing functional dependencies. We demonstrate that the problems of containment and satisfaction of order axioms can be captured as specific instances of constraint-generating dependency entailment. This makes it possible to formulate necessary and sufficient conditions for the applicability of our techniques as constraint validity problems. We characterize the computational complexity of such problems.
DyNoC: A Dynamic Infrastructure for Communication in Dynamically Reconfigurable Devices
Venue: arXiv cs.AR 2005
Year: 2005

A new paradigm to support the communication among modules dynamically placed on a reconfigurable device at run-time is presented. Based on the network on chip (NoC) infrastructure, we developed a dynamic communication infrastructure as well as routing methodologies capable to handle routing in a NoC with obstacles created by dynamically placed components. We prove the unrestricted reachability of components and pins, the deadlock-freeness and we finally show the feasibility of our approach by means on real life example applications.
Degrees of Freedom in Multiuser MIMO
Venue: arXiv cs.IT 2005
Year: 2005

We explore the available degrees of freedom for various multiuser MIMO communication scenarios such as the multiple access, broadcast, interference, relay, X and Z channels. For the two user MIMO interference channel, we find a general inner bound and a genie-aided outer bound that give us the exact number of degrees of freedom in many cases. We also study a share-and-transmit scheme for transmitter cooperation. For the share-and-transmit scheme, we show how the gains of transmitter cooperation are entirely offset by the cost of enabling that cooperation so that the available degrees of freedom are not increased.
Using Interval Particle Filtering for Marker less 3D Human Motion Capture
Venue: arXiv cs.AI 2005
Year: 2005

In this paper we present a new approach for marker less human motion capture from conventional camera feeds. The aim of our study is to recover 3D positions of key points of the body that can serve for gait analysis. Our approach is based on foreground segmentation, an articulated body model and particle filters. In order to be generic and simple no restrictive dynamic modelling was used. A new modified particle filtering algorithm was introduced. It is used efficiently to search the model configuration space. This new algorithm which we call Interval Particle Filtering reorganizes the configurations search space in an optimal deterministic way and proved to be efficient in tracking natural human movement. Results for human motion capture from a single camera are presented and compared to results obtained from a marker based system. The system proved to be able to track motion successfully even in partial occlusions.
Comparing Computational Power
Venue: arXiv cs.LO 2005
Year: 2005

It is common practice to compare the computational power of different models of computation. For example, the recursive functions are strictly more powerful than the primitive recursive functions, because the latter are a proper subset of the former (which includes Ackermann's function). Side-by-side with this "containment" method of measuring power, it is standard to use an approach based on "simulation". For example, one says that the (untyped) lambda calculus is as powerful--computationally speaking--as the partial recursive functions, because the lambda calculus can simulate all partial recursive functions by encoding the natural numbers as Church numerals. The problem is that unbridled use of these two ways of comparing power allows one to show that some computational models are strictly stronger than themselves! We argue that a better definition is that model A is strictly stronger than B if A can simulate B via some encoding, whereas B cannot simulate A under any encoding. We then show that the recursive functions are strictly stronger in this sense than the primitive recursive. We also prove that the recursive functions, partial recursive functions, and Turing machines are "complete", in the sense that no injective encoding can make them equivalent to any "hypercomputational" model.