OpenRaiser/Intern-Atlas huggingface dataset:
High Rate Single-Symbol Decodable Precoded DSTBCs for Cooperative Networks
Venue: arXiv cs.IT 2007
Year: 2007

Distributed Orthogonal Space-Time Block Codes (DOSTBCs) achieving full diversity order and single-symbol ML decodability have been introduced recently for cooperative networks and an upper-bound on the maximal rate of such codes along with code constructions has been presented. In this report, we introduce a new class of Distributed STBCs called Semi-orthogonal Precoded Distributed Single-Symbol Decodable STBCs (S-PDSSDC) wherein, the source performs co-ordinate interleaving of information symbols appropriately before transmitting it to all the relays. It is shown that DOSTBCs are a special case of S-PDSSDCs. A special class of S-PDSSDCs having diagonal covariance matrix at the destination is studied and an upper bound on the maximal rate of such codes is derived. The bounds obtained are approximately twice larger than that of the DOSTBCs. A systematic construction of S-PDSSDCs is presented when the number of relays $K \geq 4$. The constructed codes are shown to achieve the upper-bound on the rate when $K$ is of the form 0 modulo 4 or 3 modulo 4. For the rest of the values of $K$, the constructed codes are shown to have rates higher than that of DOSTBCs. It is also shown that S-PDSSDCs cannot be constructed with any form of linear processing at the relays when the source doesn't perform co-ordinate interleaving of the information symbols.
Optimal Per-Edge Processing Times in the Semi-Streaming Model
Venue: arXiv cs.DM 2007
Year: 2007

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to O(n*polylog n) bits. Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(alpha(n)), for determining k-vertex and k-edge connectivity O(k^2n) and O(n*log n) respectively for any constant k and for computing a minimum spanning forest O(log n). All these time bounds we reduce to O(1). Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems.
2006: Celebrating 75 years of AI - History and Outlook: the Next 25 Years
Venue: arXiv cs.AI 2007
Year: 2007

When Kurt Goedel layed the foundations of theoretical computer science in 1931, he also introduced essential concepts of the theory of Artificial Intelligence (AI). Although much of subsequent AI research has focused on heuristics, which still play a major role in many practical AI applications, in the new millennium AI theory has finally become a full-fledged formal science, with important optimality results for embodied agents living in unknown environments, obtained through a combination of theory a la Goedel and probability theory. Here we look back at important milestones of AI history, mention essential recent results, and speculate about what we may expect from the next 25 years, emphasizing the significance of the ongoing dramatic hardware speedups, and discussing Goedel-inspired, self-referential, self-improving universal problem solvers.
High Rate Single-Symbol ML Decodable Precoded DSTBCs for Cooperative Networks
Venue: arXiv cs.IT 2007
Year: 2007

Distributed Orthogonal Space-Time Block Codes (DOSTBCs) achieving full diversity order and single-symbol ML decodability have been introduced recently by Yi and Kim for cooperative networks and an upperbound on the maximal rate of such codes along with code constructions has been presented. In this paper, we introduce a new class of Distributed STBCs called Semi-orthogonal Precoded Distributed Single-Symbol Decodable STBCs (S-PDSSDC) wherein, the source performs co-ordinate interleaving of information symbols appropriately before transmitting it to all the relays. It is shown that DOSTBCs are a special case of S-PDSSDCs. A special class of S-PDSSDCs having diagonal covariance matrix at the destination is studied and an upperbound on the maximal rate of such codes is derived. The bounds obtained are approximately twice larger than that of the DOSTBCs. A systematic construction of S-PDSSDCs is presented when the number of relays $K \geq 4$. The constructed codes are shown to achieve the upperbound on the rate when $K$ is of the form 0 or 3 modulo 4. For the rest of the values of $K$, the constructed codes are shown to have rates higher than that of DOSTBCs. It is shown that S-PDSSDCs cannot be constructed with any form of linear processing at the relays when the source doesn't perform co-ordinate interleaving of the information symbols. Simulation result shows that S-PDSSDCs have better probability of error performance than that of DOSTBCs.
Brief encounter networks
Venue: arXiv cs.CY 2007
Year: 2007

Many complex human and natural phenomena can usefully be represented as networks describing the relationships between individuals. While these relationships are typically intermittent, previous research has used network representations that aggregate the relationships at discrete intervals. However, such an aggregation discards important temporal information, thus inhibiting our understanding of the networks dynamic behaviour and evolution. We have recorded patterns of human urban encounter using Bluetooth technology thus retaining the temporal properties of this network. Here we show how this temporal information influences the structural properties of the network. We show that the temporal properties of human urban encounter are scale-free, leading to an overwhelming proportion of brief encounters between individuals. While previous research has shown preferential attachment to result in scale-free connectivity in aggregated network data, we found that scale-free connectivity results from the temporal properties of the network. In addition, we show that brief encounters act as weak social ties in the diffusion of non-expiring information, yet persistent encounters provide the means for sustaining time-expiring information through a network.
Oral messages improve visual search
Venue: arXiv cs.HC 2007
Year: 2007

Input multimodality combining speech and hand gestures has motivated numerous usability studies. Contrastingly, issues relating to the design and ergonomic evaluation of multimodal output messages combining speech with visual modalities have not yet been addressed extensively. The experimental study presented here addresses one of these issues. Its aim is to assess the actual efficiency and usability of oral system messages including brief spatial information for helping users to locate objects on crowded displays rapidly. Target presentation mode, scene spatial structure and task difficulty were chosen as independent variables. Two conditions were defined: the visual target presentation mode (VP condition) and the multimodal target presentation mode (MP condition). Each participant carried out two blocks of visual search tasks (120 tasks per block, and one block per condition). Scene target presentation mode, scene structure and task difficulty were found to be significant factors. Multimodal target presentation proved to be more efficient than visual target presentation. In addition, participants expressed very positive judgments on multimodal target presentations which were preferred to visual presentations by a majority of participants. Besides, the contribution of spatial messages to visual search speed and accuracy was influenced by scene spatial structure and task difficulty: (i) messages improved search efficiency to a lesser extent for 2D array layouts than for some other symmetrical layouts, although the use of 2D arrays for displaying pictures is currently prevailing; (ii) message usefulness increased with task difficulty. Most of these results are statistically significant.
Qualitative Belief Conditioning Rules (QBCR)
Venue: arXiv cs.AI 2007
Year: 2007

In this paper we extend the new family of (quantitative) Belief Conditioning Rules (BCR) recently developed in the Dezert-Smarandache Theory (DSmT) to their qualitative counterpart for belief revision. Since the revision of quantitative as well as qualitative belief assignment given the occurrence of a new event (the conditioning constraint) can be done in many possible ways, we present here only what we consider as the most appealing Qualitative Belief Conditioning Rules (QBCR) which allow to revise the belief directly with words and linguistic labels and thus avoids the introduction of ad-hoc translations of quantitative beliefs into quantitative ones for solving the problem.
On Faster Integer Calculations using Non-Arithmetic Primitives
Venue: arXiv cs.DS 2007
Year: 2007

The unit cost model is both convenient and largely realistic for describing integer decision algorithms over (+,*). Additional operations like division with remainder or bitwise conjunction, although equally supported by computing hardware, may lead to a considerable drop in complexity. We show a variety of concrete problems to benefit from such NON-arithmetic primitives by presenting and analyzing corresponding fast algorithms.
On the Complexity of Protein Local Structure Alignment Under the Discrete Fréchet Distance
Venue: arXiv cs.CC 2007
Year: 2007

We show that given $m$ proteins (or protein backbones, which are modeled as 3D polygonal chains each of length O(n)) the problem of protein local structure alignment under the discrete Fréchet distance is as hard as Independent Set. So the problem does not admit any approximation of factor $n^{1-ε}$. This is the strongest negative result regarding the protein local structure alignment problem. On the other hand, if $m$ is a constant, then the problem can be solved in polygnomial time.
The Induced Bounded-Degree Subgraph Problem and Stream Control in MIMO Networks
Venue: arXiv cs.NI 2007
Year: 2007

In this report, we consider maximal solutions to the induced bounded-degree subgraph problem and relate it to issues concerning stream control in multiple-input multiple-output (MIMO) networks. We present a new distributed algorithm that completes in logarithmic time with high probability and is guaranteed to complete in linear time. We conclude the report with simulation results that address the effectiveness of stream control and the relative impact of receiver overloading and flexible interference suppression.
Johnson Type Bounds on Constant Dimension Codes
Venue: arXiv cs.IT 2007
Year: 2007

Very recently, an operator channel was defined by Koetter and Kschischang when they studied random network coding. They also introduced constant dimension codes and demonstrated that these codes can be employed to correct errors and/or erasures over the operator channel. Constant dimension codes are equivalent to the so-called linear authentication codes introduced by Wang, Xing and Safavi-Naini when constructing distributed authentication systems in 2003. In this paper, we study constant dimension codes. It is shown that Steiner structures are optimal constant dimension codes achieving the Wang-Xing-Safavi-Naini bound. Furthermore, we show that constant dimension codes achieve the Wang-Xing-Safavi-Naini bound if and only if they are certain Steiner structures. Then, we derive two Johnson type upper bounds, say I and II, on constant dimension codes. The Johnson type bound II slightly improves on the Wang-Xing-Safavi-Naini bound. Finally, we point out that a family of known Steiner structures is actually a family of optimal constant dimension codes achieving both the Johnson type bounds I and II.
A proof of strong normalisation using domain theory
Venue: arXiv cs.LO 2007
Year: 2007

Ulrich Berger presented a powerful proof of strong normalisation using domains, in particular it simplifies significantly Tait's proof of strong normalisation of Spector's bar recursion. The main contribution of this paper is to show that, using ideas from intersection types and Martin-Lof's domain interpretation of type theory one can in turn simplify further U. Berger's argument. We build a domain model for an untyped programming language where U. Berger has an interpretation only for typed terms or alternatively has an interpretation for untyped terms but need an extra condition to deduce strong normalisation. As a main application, we show that Martin-Löf dependent type theory extended with a program for Spector double negation shift.
Distribution of PageRank Mass Among Principle Components of the Web
Venue: arXiv cs.NI 2007
Year: 2007

We study the PageRank mass of principal components in a bow-tie Web Graph, as a function of the damping factor c. Using a singular perturbation approach, we show that the PageRank share of IN and SCC components remains high even for very large values of the damping factor, in spite of the fact that it drops to zero when c goes to one. However, a detailed study of the OUT component reveals the presence ``dead-ends'' (small groups of pages linking only to each other) that receive an unfairly high ranking when c is close to one. We argue that this problem can be mitigated by choosing c as small as 1/2.
Pushdown Compression
Venue: arXiv cs.IT 2007
Year: 2007

The pressing need for eficient compression schemes for XML documents has recently been focused on stack computation [6, 9], and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. The celebrated Lempel-Ziv algorithm LZ78 [10] was introduced as a general purpose compression algorithm that outperforms finite-state compressors on all sequences. We compare the performance of the Lempel-Ziv algorithm with that of the pushdown compressors, or compression algorithms that can be implemented with a pushdown transducer. This comparison is made without any a priori assumption on the data's source and considering the asymptotic compression ratio for infinite sequences. We prove that Lempel-Ziv is incomparable with pushdown compressors.
Quantifying Homology Classes II: Localization and Stability
Venue: arXiv cs.CG 2007
Year: 2007

In the companion paper, we measured homology classes and computed the optimal homology basis. This paper addresses two related problems, namely, localization and stability. We localize a class with the cycle minimizing a certain objective function. We explore three different objective functions, namely, volume, diameter and radius. We show that it is NP-hard to compute the smallest cycle using the former two. We also prove that the measurement defined in the companion paper is stable with regard to small changes of the geometry of the concerned space.
When are recommender systems useful?
Venue: arXiv cs.IR 2007
Year: 2007

Recommender systems are crucial tools to overcome the information overload brought about by the Internet. Rigorous tests are needed to establish to what extent sophisticated methods can improve the quality of the predictions. Here we analyse a refined correlation-based collaborative filtering algorithm and compare it with a novel spectral method for recommending. We test them on two databases that bear different statistical properties (MovieLens and Jester) without filtering out the less active users and ordering the opinions in time, whenever possible. We find that, when the distribution of user-user correlations is narrow, simple averages work nearly as well as advanced methods. Recommender systems can, on the other hand, exploit a great deal of additional information in systems where external influence is negligible and peoples' tastes emerge entirely. These findings are validated by simulations with artificially generated data.
Supervised learning on graphs of spatio-temporal similarity in satellite image sequences
Venue: arXiv cs.CV 2007
Year: 2007

High resolution satellite image sequences are multidimensional signals composed of spatio-temporal patterns associated to numerous and various phenomena. Bayesian methods have been previously proposed in (Heas and Datcu, 2005) to code the information contained in satellite image sequences in a graph representation using Bayesian methods. Based on such a representation, this paper further presents a supervised learning methodology of semantics associated to spatio-temporal patterns occurring in satellite image sequences. It enables the recognition and the probabilistic retrieval of similar events. Indeed, graphs are attached to statistical models for spatio-temporal processes, which at their turn describe physical changes in the observed scene. Therefore, we adjust a parametric model evaluating similarity types between graph patterns in order to represent user-specific semantics attached to spatio-temporal phenomena. The learning step is performed by the incremental definition of similarity types via user-provided spatio-temporal pattern examples attached to positive or/and negative semantics. From these examples, probabilities are inferred using a Bayesian network and a Dirichlet model. This enables to links user interest to a specific similarity model between graph patterns. According to the current state of learning, semantic posterior probabilities are updated for all possible graph patterns so that similar spatio-temporal phenomena can be recognized and retrieved from the image sequence. Few experiments performed on a multi-spectral SPOT image sequence illustrate the proposed spatio-temporal recognition method.
A software for learning Information Theory basics with emphasis on Entropy of Spanish
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a tutorial software to learn Information Theory basics in a practical way is reported. The software, called IT-tutor-UV, makes use of a modern existing Spanish corpus for the modeling of the source. Both the source and the channel coding are also included in this educational tool as part of the learning experience. Entropy values of the Spanish language obtained with the IT-tutor-UV are discussed and compared to others that were previously calculated under limited conditions.
Fast Algorithm and Implementation of Dissimilarity Self-Organizing Maps
Venue: arXiv cs.NE 2007
Year: 2007

In many real world applications, data cannot be accurately represented by vectors. In those situations, one possible solution is to rely on dissimilarity measures that enable sensible comparison between observations. Kohonen's Self-Organizing Map (SOM) has been adapted to data described only through their dissimilarity matrix. This algorithm provides both non linear projection and clustering of non vector data. Unfortunately, the algorithm suffers from a high cost that makes it quite difficult to use with voluminous data sets. In this paper, we propose a new algorithm that provides an important reduction of the theoretical cost of the dissimilarity SOM without changing its outcome (the results are exactly the same as the ones obtained with the original algorithm). Moreover, we introduce implementation methods that result in very short running times. Improvements deduced from the theoretical cost model are validated on simulated and real world data (a word list clustering problem). We also demonstrate that the proposed implementation methods reduce by a factor up to 3 the running time of the fast algorithm over a standard implementation.
Cooperative Multiplexing in a Half Duplex Relay Network: Performance and Constraints
Venue: arXiv cs.IT 2007
Year: 2007

Previous work on relay networks has concentrated primarily on the diversity benefits of such techniques. This paper explores the possibility of also obtaining multiplexing gain in a relay network, while retaining diversity gain. Specifically, consider a network in which a single source node is equipped with one antenna and a destination is equipped with two antennas. It is shown that, in certain scenarios, by adding a relay with two antennas and using a successive relaying protocol, the diversity multiplexing tradeoff performance of the network can be lower bounded by that of a 2 by 2 MIMO channel, when the decode-and-forward protocol is applied at the relay. A distributed D-BLAST architecture is developed, in which parallel channel coding is applied to achieve this tradeoff. A space-time coding strategy, which can bring a maximal multiplexing gain of more than one, is also derived for this scenario. As will be shown, while this space-time coding strategy exploits maximal diversity for a small multiplexing gain, the proposed successive relaying scheme offers a significant performance advantage for higher data rate transmission. In addition to the specific results shown here, these ideas open a new direction for exploiting the benefits of wireless relay networks.
Static Deadlock Detection in MPI Synchronization Communication
Venue: arXiv cs.DC 2007
Year: 2007

It is very common to use dynamic methods to detect deadlocks in MPI programs for the reason that static methods have some restrictions. To guarantee high reliability of some important MPI-based application software, a model of MPI synchronization communication is abstracted and a type of static method is devised to examine deadlocks in such modes. The model has three forms with different complexity: sequential model, single-loop model and nested-loop model. Sequential model is a base for all models. Single-loop model must be treated with a special type of equation group and nested-loop model extends the methods for the other two models. A standard Java-based software framework originated from these methods is constructed for determining whether MPI programs are free from synchronization communication deadlocks. Our practice shows the software framework is better than those tools using dynamic methods because it can dig out all synchronization communication deadlocks before an MPI-based program goes into running.
Geographic Gossip: Efficient Averaging for Sensor Networks
Venue: arXiv cs.IT 2007
Year: 2007

Gossip algorithms for distributed computation are attractive due to their simplicity, distributed nature, and robustness in noisy and uncertain environments. However, using standard gossip algorithms can lead to a significant waste in energy by repeatedly recirculating redundant information. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is related to the slow mixing times of random walks on the communication graph. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing geographic routing combined with a simple resampling method, we demonstrate substantial gains over previously proposed gossip protocols. For regular graphs such as the ring or grid, our algorithm improves standard gossip by factors of $n$ and $\sqrt{n}$ respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy $ε$ using $O(\frac{n^{1.5}}{\sqrt{\log n}} \log ε^{-1})$ radio transmissions, which yields a $\sqrt{\frac{n}{\log n}}$ factor improvement over standard gossip algorithms. We illustrate these theoretical results with experimental comparisons between our algorithm and standard methods as applied to various classes of random fields.
Optimum Diversity-Multiplexing Tradeoff in the Multiple Relays Network
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a multiple-relay network in considered, in which $K$ single-antenna relays assist a single-antenna transmitter to communicate with a single-antenna receiver in a half-duplex mode. A new Amplify and Forward (AF) scheme is proposed for this network and is shown to achieve the optimum diversity-multiplexing trade-off curve.