OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Throughput-Diversity-Delay Tradeoff in MIMO ARQ Block-Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we consider an automatic-repeat-request (ARQ) retransmission protocol signaling over a block-fading multiple-input, multiple-output (MIMO) channel. Unlike previous work, we allow for multiple fading blocks within each transmission (ARQ round), and we constrain the transmitter to fixed rate codes constructed over complex signal constellations. In particular, we examine the general case of average input-power-constrained constellations as well as the practically important case of finite discrete constellations. This scenario is a suitable model for practical wireless communications systems employing orthogonal frequency division multiplexing techniques over a MIMO ARQ channel. Two cases of fading dynamics are considered, namely short-term static fading where channel fading gains change randomly for each ARQ round, and long-term static fading where channel fading gains remain constant over all ARQ rounds pertaining to a given message. As our main result, we prove that for the block-fading MIMO ARQ channel with discrete input signal constellation satisfying a short-term power constraint, the optimal signal-to-noise ratio (SNR) exponent is given by a modified Singleton bound, relating all the system parameters. To demonstrate the practical significance of the theoretical analysis, we present numerical results showing that practical Singleton-bound-achieving maximum distance separable codes achieve the optimal SNR exponent.
Characterization of Rate Region in Interference Channels with Constrained Power
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, an $n$-user Gaussian interference channel, where the power of the transmitters are subject to some upper-bounds is studied. We obtain a closed-form expression for the rate region of such a channel based on the Perron-Frobenius theorem. While the boundary of the rate region for the case of unconstrained power is a well-established result, this is the first result for the case of constrained power. We extend this result to the time-varying channels and obtain a closed-form solution for the rate region of such channels.
Data Management: Past, Present, and Future
Venue: arXiv cs.DB 2007
Year: 2007

Soon most information will be available at your fingertips, anytime, anywhere. Rapid advances in storage, communications, and processing allow us move all information into Cyberspace. Software to define, search, and visualize online information is also a key to creating and accessing online information. This article traces the evolution of data management systems and outlines current trends. Data management systems began by automating traditional tasks: recording transactions in business, science, and commerce. This data consisted primarily of numbers and character strings. Today these systems provide the infrastructure for much of our society, allowing fast, reliable, secure, and automatic access to data distributed throughout the world. Increasingly these systems automatically design and manage access to the data. The next steps are to automate access to richer forms of data: images, sound, video, maps, and other media. A second major challenge is automatically summarizing and abstracting data in anticipation of user requests. These multi-media databases and tools to access them will be a cornerstone of our move to Cyberspace.
Ontology from Local Hierarchical Structure in Text
Venue: arXiv cs.IR 2007
Year: 2007

We study the notion of hierarchy in the context of visualizing textual data and navigating text collections. A formal framework for ``hierarchy'' is given by an ultrametric topology. This provides us with a theoretical foundation for concept hierarchy creation. A major objective is {\em scalable} annotation or labeling of concept maps. Serendipitously we pursue other objectives such as deriving common word pair (and triplet) phrases, i.e., word 2- and 3-grams. We evaluate our approach using (i) a collection of texts, (ii) a single text subdivided into successive parts (for which we provide an interactive demonstrator), and (iii) a text subdivided at the sentence or line level. While detailing a generic framework, a distinguishing feature of our work is that we focus on {\em locality} of hierarchic structure in order to extract semantic information.
Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
Venue: arXiv cs.SC 2007
Year: 2007

Block projections have been used, in [Eberly et al. 2006], to obtain an efficient algorithm to find solutions for sparse systems of linear equations. A bound of softO(n^(2.5)) machine operations is obtained assuming that the input matrix can be multiplied by a vector with constant-sized entries in softO(n) machine operations. Unfortunately, the correctness of this algorithm depends on the existence of efficient block projections, and this has been conjectured. In this paper we establish the correctness of the algorithm from [Eberly et al. 2006] by proving the existence of efficient block projections over sufficiently large fields. We demonstrate the usefulness of these projections by deriving improved bounds for the cost of several matrix problems, considering, in particular, ``sparse'' matrices that can be be multiplied by a vector using softO(n) field operations. We show how to compute the inverse of a sparse matrix over a field F using an expected number of softO(n^(2.27)) operations in F. A basis for the null space of a sparse matrix, and a certification of its rank, are obtained at the same cost. An application to Kaltofen and Villard's Baby-Steps/Giant-Steps algorithms for the determinant and Smith Form of an integer matrix yields algorithms requiring softO(n^(2.66)) machine operations. The derived algorithms are all probabilistic of the Las Vegas type.
The parallel implementation of the Astrée static analyzer
Venue: arXiv cs.PL 2007
Year: 2007

The Astrée static analyzer is a specialized tool that can prove the absence of runtime errors, including arithmetic overflows, in large critical programs. Keeping analysis times reasonable for industrial use is one of the design objectives. In this paper, we discuss the parallel implementation of the analysis.
Menzerath-Altmann Law for Syntactic Structures in Ukrainian
Venue: arXiv cs.CL 2007
Year: 2007

In the paper, the definition of clause suitable for an automated processing of a Ukrainian text is proposed. The Menzerath-Altmann law is verified on the sentence level and the parameters for the dependences of the clause length counted in words and syllables on the sentence length counted in clauses are calculated for "Perekhresni Stezhky" ("The Cross-Paths"), a novel by Ivan Franko.
One-bit Distributed Sensing and Coding for Field Estimation in Sensor Networks
Venue: arXiv cs.IT 2007
Year: 2007

This paper formulates and studies a general distributed field reconstruction problem using a dense network of noisy one-bit randomized scalar quantizers in the presence of additive observation noise of unknown distribution. A constructive quantization, coding, and field reconstruction scheme is developed and an upper-bound to the associated mean squared error (MSE) at any point and any snapshot is derived in terms of the local spatio-temporal smoothness properties of the underlying field. It is shown that when the noise, sensor placement pattern, and the sensor schedule satisfy certain weak technical requirements, it is possible to drive the MSE to zero with increasing sensor density at points of field continuity while ensuring that the per-sensor bitrate and sensing-related network overhead rate simultaneously go to zero. The proposed scheme achieves the order-optimal MSE versus sensor density scaling behavior for the class of spatially constant spatio-temporal fields.
A Virtual Logo Keyboard for People with Motor Disabilities
Venue: arXiv cs.HC 2007
Year: 2007

In our society, people with motor impairments are oftentimes socially excluded from their environment. This is unfortunate because every human being should have the possibility to obtain the necessary conditions to live a normal life. Although there is technology to assist people with motor impairments, few systems are targeted for programming environments. We have created a system, called Logo Keyboard, to assist people with motor disabilities to program with the Logo programming language. With this special keyboard we can help more people to get involved into computer programming and to develop projects in different areas.
Expert Programming Knowledge: a Schema-Based Approach
Venue: arXiv cs.HC 2007
Year: 2007

The topic of this chapter is the role of expert programming knowledge in the understanding activity. In the "schema-based approach", the role of semantic structures is emphasized whereas, in the "control-flow approach", the role of syntactic structures is emphasized. Data which support schema-based models of understanding are presented. Data which are more consistent with the "control-flow approach" allow to discuss the limits of the former kind of models.
Negotiation in collaborative assessment of design solutions: an empirical study on a Concurrent Engineering process
Venue: arXiv cs.HC 2007
Year: 2007

In Concurrent engineering, design solutions are not only produced by individuals specialized in a given field. Due to the team nature of the design activity, solutions are negotiated. Our objective is to analyse the argumentation processes leading to these negotiated solutions. These processes take place in the meetings which group together specialists with a co-design aim. We conducted cognitive ergonomics research work during the definition phase of an aeronautical design project in which the participants work in Concurrent Engineering. We recorded, retranscribed and analysed 7 multi-speciality meetings. These meetings were organised, as needed, to assess the integration of the solutions of each speciality into a global solution. We found that there are three main design proposal assessment modes which can be combined in these meetings: (a) analytical assessment mode, (b) comparative assessment mode (c) analogical assessment mode. Within these assessment modes, different types of arguments are used. Furthermore we found a typical temporal negotiation process.
On Evaluating the Rate-Distortion Function of Sources with Feed-Forward and the Capacity of Channels with Feedback
Venue: arXiv cs.IT 2007
Year: 2007

We study the problem of computing the rate-distortion function for sources with feed-forward and the capacity for channels with feedback. The formulas (involving directed information) for the optimal rate-distortion function with feed-forward and channel capacity with feedback are multi-letter expressions and cannot be computed easily in general. In this work, we derive conditions under which these can be computed for a large class of sources/channels with memory and distortion/cost measures. Illustrative examples are also provided.
Plagiarism Detection in arXiv
Venue: arXiv cs.DB 2007
Year: 2007

We describe a large-scale application of methods for finding plagiarism in research document collections. The methods are applied to a collection of 284,834 documents collected by arXiv.org over a 14 year period, covering a few different research disciplines. The methodology efficiently detects a variety of problematic author behaviors, and heuristics are developed to reduce the number of false positives. The methods are also efficient enough to implement as a real-time submission screen for a collection many times larger.
Construction of Minimal Tail-Biting Trellises for Codes over Finite Abelian Groups
Venue: arXiv cs.IT 2007
Year: 2007

A definition of atomic codeword for a group code is presented. Some properties of atomic codewords of group codes are investigated. Using these properties, it is shown that every minimal tail-biting trellis for a group code over a finite abelian group can be constructed from its characteristic generators, which extends the work of Koetter and Vardy who treated the case of a linear code over a field. We also present an efficient algorithm for constructing the minimal tail-biting trellis of a group code over a finite abelian group, given a generator matrix.
High-rate, Multi-Symbol-Decodable STBCs from Clifford Algebras
Venue: arXiv cs.IT 2007
Year: 2007

It is well known that Space-Time Block Codes (STBCs) obtained from Orthogonal Designs (ODs) are single-symbol-decodable (SSD) and from Quasi-Orthogonal Designs (QODs) are double-symbol decodable. However, there are SSD codes that are not obtainable from ODs and DSD codes that are not obtainable from QODs. In this paper a method of constructing $g$-symbol decodable ($g$-SD) STBCs using representations of Clifford algebras are presented which when specialized to $g=1,2$ gives SSD and DSD codes respectively. For the number of transmit antennas $2^a$ the rate (in complex symbols per channel use) of the $g$-SD codes presented in this paper is $\frac{a+1-g}{2^{a-g}}$. The maximum rate of the DSD STBCs from QODs reported in the literature is $\frac{a}{2^{a-1}}$ which is smaller than the rate $\frac{a-1}{2^{a-2}}$ of the DSD codes of this paper, for $2^a$ transmit antennas. In particular, the reported DSD codes for 8 and 16 transmit antennas offer rates 1 and 3/4 respectively whereas the known STBCs from QODs offer only 3/4 and 1/2 respectively. The construction of this paper is applicable for any number of transmit antennas.
Algebraic Signal Processing Theory: Cooley-Tukey Type Algorithms for DCTs and DSTs
Venue: arXiv cs.IT 2007
Year: 2007

This paper presents a systematic methodology based on the algebraic theory of signal processing to classify and derive fast algorithms for linear transforms. Instead of manipulating the entries of transform matrices, our approach derives the algorithms by stepwise decomposition of the associated signal models, or polynomial algebras. This decomposition is based on two generic methods or algebraic principles that generalize the well-known Cooley-Tukey FFT and make the algorithms' derivations concise and transparent. Application to the 16 discrete cosine and sine transforms yields a large class of fast algorithms, many of which have not been found before.
Quantized vs. Analog Feedback for the MIMO Downlink: A Comparison between Zero-Forcing Based Achievable Rates
Venue: arXiv cs.IT 2007
Year: 2007

We consider a MIMO fading broadcast channel and compare the achievable ergodic rates when the channel state information at the transmitter is provided by analog noisy feedback or by quantized (digital) feedback. The superiority of digital feedback is shown, with perfect or imperfect CSIR, whenever the number of feedback channel uses per channel coefficient is larger than 1. Also, we show that by proper design of the digital feedback link, errors in the feedback have a minor effect even by using very simple uncoded modulation. Finally, we show that analog feedback achieves a fraction 1 - 2F of the optimal multiplexing gain even in the presence of a feedback delay, when the fading belongs to the class of Doppler processes with normalized maximum Doppler frequency shift 0 <= F <= 1/2.
Noise Limited Computational Speed
Venue: arXiv cs.AR 2007
Year: 2007

In modern transistor based logic gates, the impact of noise on computation has become increasingly relevant since the voltage scaling strategy, aimed at decreasing the dissipated power, has increased the probability of error due to the reduced switching threshold voltages. In this paper we discuss the role of noise in a two state model that mimic the dynamics of standard logic gates and show that the presence of the noise sets a fundamental limit to the computing speed. An optimal idle time interval that minimizes the error probability, is derived.
Group characterizable entropy functions
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies properties of entropy functions that are induced by groups and subgroups. We showed that many information theoretic properties of those group induced entropy functions also have corresponding group theoretic interpretations. Then we propose an extension method to find outer bound for these group induced entropy functions.
The Haar Wavelet Transform of a Dendrogram: Additional Notes
Venue: arXiv cs.IR 2007
Year: 2007

We consider the wavelet transform of a finite, rooted, node-ranked, $p$-way tree, focusing on the case of binary ($p = 2$) trees. We study a Haar wavelet transform on this tree. Wavelet transforms allow for multiresolution analysis through translation and dilation of a wavelet function. We explore how this works in our tree context.
Logic Programming with Satisfiability
Venue: arXiv cs.PL 2007
Year: 2007

This paper presents a Prolog interface to the MiniSat satisfiability solver. Logic program- ming with satisfiability combines the strengths of the two paradigms: logic programming for encoding search problems into satisfiability on the one hand and efficient SAT solving on the other. This synergy between these two exposes a programming paradigm which we propose here as a logic programming pearl. To illustrate logic programming with SAT solving we give an example Prolog program which solves instances of Partial MAXSAT.
A Local Algorithm for Finding Dense Subgraphs
Venue: arXiv cs.DS 2007
Year: 2007

We present a local algorithm for finding dense subgraphs of bipartite graphs, according to the definition of density proposed by Kannan and Vinay. Our algorithm takes as input a bipartite graph with a specified starting vertex, and attempts to find a dense subgraph near that vertex. We prove that for any subgraph S with k vertices and density theta, there are a significant number of starting vertices within S for which our algorithm produces a subgraph S' with density theta / O(log n) on at most O(D k^2) vertices, where D is the maximum degree. The running time of the algorithm is O(D k^2), independent of the number of vertices in the graph.
A Note on the Periodicity and the Output Rate of Bit Search Type Generators
Venue: arXiv cs.CR 2007
Year: 2007

We investigate the bit-search type irregular decimation algorithms that are used within LFSR-based stream ciphers. In particular, we concentrate on BSG and ABSG, and consider two different setups for the analysis. In the first case, the input is assumed to be a m-sequence; we show that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, we prove that the cardinality of each of these sets is equal to the period of one of its elements and subsequently derive the first known bounds on the expected output period (assuming that no subperiods exist). In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent identically distributed Bernoulli process with probability 1/2). Under these assumptions, we derive closed-form expressions for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.
A Sum-Product Model as a Physical Basis for Shadow Fading
Venue: arXiv cs.OH 2007
Year: 2007

Shadow fading (slow fading) effects play a central role in mobile communication system design and analysis. Experimental evidence indicates that shadow fading exhibits log-normal power distribution almost universally, and yet it is still not well understood what causes this. In this paper, we propose a versatile sum-product signal model as a physical basis for shadow fading. Simulation results imply that the proposed model results in log-normally distributed local mean power regardless of the distributions of the interactions in the radio channel, and hence it is capable of explaining the log-normality in a wide variety of propagation scenarios. The sum-product model also includes as its special cases the conventional product model as well as the recently proposed sum model, and improves upon these by: a) being applicable in both global and local distance scales; b) being more plausible from physical point of view; c) providing better goodness-of-fit to log-normal distribution than either of these models.
A Class of Multi-Channel Cosine Modulated IIR Filter Banks
Venue: arXiv cs.IT 2007
Year: 2007

This paper presents a class of multi-channel cosine-modulated filter banks satisfying the perfect reconstruction (PR) property using an IIR prototype filter. By imposing a suitable structure on the polyphase filter coefficients, we show that it is possible to greatly simplify the PR condition, while preserving the causality and stability of the system. We derive closed-form expressions for the synthesis filters and also study the numerical stability of the filter bank using frame theoretic bounds. Further, we show that it is possible to implement this filter bank with much lower number of arithmetic operations when compared to FIR filter banks with comparable performance. The filter bank's modular structure also lends itself to efficient VLSI implementation.
On a family of strong geometric spanners that admit local routing strategies
Venue: arXiv cs.CG 2007
Year: 2007

We introduce a family of directed geometric graphs, denoted $\paz$, that depend on two parameters $λ$ and $θ$. For $0\leq θ<\fracπ{2}$ and ${1/2} < λ< 1$, the $\paz$ graph is a strong $t$-spanner, with $t=\frac{1}{(1-λ)\cosθ}$. The out-degree of a node in the $\paz$ graph is at most $\lfloor2π/\min(θ, \arccos\frac{1}{2λ})\rfloor$. Moreover, we show that routing can be achieved locally on $\paz$. Next, we show that all strong $t$-spanners are also $t$-spanners of the unit disk graph. Simulations for various values of the parameters $λ$ and $θ$ indicate that for random point sets, the spanning ratio of $\paz$ is better than the proven theoretical bounds.
Interpolation-based Decoding of Alternant Codes
Venue: arXiv cs.IT 2007
Year: 2007

We formulate the classical decoding algorithm of alternant codes afresh based on interpolation as in Sudan's list decoding of Reed-Solomon codes, and thus get rid of the key equation and the linear recurring sequences in the theory. The result is a streamlined exposition of the decoding algorithm using a bit of the theory of Groebner bases of modules.
On the Maximal Diversity Order of Spatial Multiplexing with Transmit Antenna Selection
Venue: arXiv cs.IT 2007
Year: 2007

Zhang et. al. recently derived upper and lower bounds on the achievable diversity of an N_R x N_T i.i.d. Rayleigh fading multiple antenna system using transmit antenna selection, spatial multiplexing and a linear receiver structure. For the case of L = 2 transmitting (out of N_T available) antennas the bounds are tight and therefore specify the maximal diversity order. For the general case with L <= min(N_R,N_T) transmitting antennas it was conjectured that the maximal diversity is (N_T-L+1)(N_R-L+1) which coincides with the lower bound. Herein, we prove this conjecture for the zero forcing and zero forcing decision feedback (with optimal detection ordering) receiver structures.
Attribute Value Reordering For Efficient Hybrid OLAP
Venue: arXiv cs.DB 2007
Year: 2007

The normalization of a data cube is the ordering of the attribute values. For large multidimensional arrays where dense and sparse chunks are stored differently, proper normalization can lead to improved storage efficiency. We show that it is NP-hard to compute an optimal normalization even for 1x3 chunks, although we find an exact algorithm for 1x2 chunks. When dimensions are nearly statistically independent, we show that dimension-wise attribute frequency sorting is an optimal normalization and takes time O(d n log(n)) for data cubes of size n^d. When dimensions are not independent, we propose and evaluate several heuristics. The hybrid OLAP (HOLAP) storage mechanism is already 19%-30% more efficient than ROLAP, but normalization can improve it further by 9%-13% for a total gain of 29%-44% over ROLAP.