OpenRaiser/Intern-Atlas huggingface dataset:
Deterministic Designs with Deterministic Guarantees: Toeplitz Compressed Sensing Matrices, Sequence Designs and System Identification
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we present a new family of discrete sequences having "random like" uniformly decaying auto-correlation properties. The new class of infinite length sequences are higher order chirps constructed using irrational numbers. Exploiting results from the theory of continued fractions and diophantine approximations, we show that the class of sequences so formed has the property that the worst-case auto-correlation coefficients for every finite length sequence decays at a polynomial rate. These sequences display doppler immunity as well. We also show that Toeplitz matrices formed from such sequences satisfy restricted-isometry-property (RIP), a concept that has played a central role recently in Compressed Sensing applications. Compressed sensing has conventionally dealt with sensing matrices with arbitrary components. Nevertheless, such arbitrary sensing matrices are not appropriate for linear system identification and one must employ Toeplitz structured sensing matrices. Linear system identification plays a central role in a wide variety of applications such as channel estimation for multipath wireless systems as well as control system applications. Toeplitz matrices are also desirable on account of their filtering structure, which allows for fast implementation together with reduced storage requirements.
Quantitative Paradigm of Software Reliability as Content Relevance
Venue: arXiv cs.SE 2008
Year: 2008

This paper presents a quantitative approach to software reliability and content relevance definitions validated by the systems' potential reliability law.Thus it is argued for the unified math nature or quantitative paradigm of software reliability and content relevance.
Graph Kernels
Venue: arXiv cs.LG 2008
Year: 2008

We present a unified framework to study graph kernels, special cases of which include the random walk graph kernel \citep{GaeFlaWro03,BorOngSchVisetal05}, marginalized graph kernel \citep{KasTsuIno03,KasTsuIno04,MahUedAkuPeretal04}, and geometric kernel on graphs \citep{Gaertner02}. Through extensions of linear algebra to Reproducing Kernel Hilbert Spaces (RKHS) and reduction to a Sylvester equation, we construct an algorithm that improves the time complexity of kernel computation from $O(n^6)$ to $O(n^3)$. When the graphs are sparse, conjugate gradient solvers or fixed-point iterations bring our algorithm into the sub-cubic domain. Experiments on graphs from bioinformatics and other application domains show that it is often more than a thousand times faster than previous approaches. We then explore connections between diffusion kernels \citep{KonLaf02}, regularization on graphs \citep{SmoKon03}, and graph kernels, and use these connections to propose new graph kernels. Finally, we show that rational kernels \citep{CorHafMoh02,CorHafMoh03,CorHafMoh04} when specialized to graphs reduce to the random walk graph kernel.
The Dynamics of Probabilistic Population Protocols
Venue: arXiv cs.DC 2008
Year: 2008

We study here the dynamics (and stability) of Probabilistic Population Protocols, via the differential equations approach. We provide a quite general model and we show that it includes the model of Angluin et. al. in the case of very large populations. For the general model we give a sufficient condition for stability that can be checked in polynomial time. We also study two interesting subcases: (a) protocols whose specifications (in our terms) are configuration independent. We show that they are always stable and that their eventual subpopulation percentages are actually a Markov Chain stationary distribution. (b) protocols that have dynamics resembling virus spread. We show that their dynamics are actually similar to the well-known Replicator Dynamics of Evolutionary Games. We also provide a sufficient condition for stability in this case.
Full Diversity Codes for MISO Systems Equipped with Linear or ML Detectors
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, a general criterion for space time block codes (STBC) to achieve full-diversity with a linear receiver is proposed for a wireless communication system having multiple transmitter and single receiver antennas (MISO). Particularly, the STBC with Toeplitz structure satisfies this criterion and therefore, enables full-diversity. Further examination of this Toeplitz STBC reveals the following important properties: a) The symbol transmission rate can be made to approach unity. b) Applying the Toeplitz code to any signalling scheme having nonzero distance between the nearest constellation points results in a non-vanishing determinant. In addition, if QAM is used as the signalling scheme, then for independent MISO flat fading channels, the Toeplitz codes is proved to approach the optimal diversity-vs-multiplexing tradeoff with a ZF receiver when the number of channel uses is large. This is, so far, the first non-orthogonal STBC shown to achieve the optimal tradeoff for such a receiver. On the other hand, when ML detection is employed in a MISO system, the Toeplitz STBC achieves the maximum coding gain for independent channels. When the channel fading coefficients are correlated, the inherent transmission matrix in the Toeplitz STBC can be designed to minimize the average worst case pair-wise error probability.
About the creation of a parallel bilingual corpora of web-publications
Venue: arXiv cs.CL 2008
Year: 2008

The algorithm of the creation texts parallel corpora was presented. The algorithm is based on the use of "key words" in text documents, and on the means of their automated translation. Key words were singled out by means of using Russian and Ukrainian morphological dictionaries, as well as dictionaries of the translation of nouns for the Russian and Ukrainianlanguages. Besides, to calculate the weights of the terms in the documents, empiric-statistic rules were used. The algorithm under consideration was realized in the form of a program complex, integrated into the content-monitoring InfoStream system. As a result, a parallel bilingual corpora of web-publications containing about 30 thousand documents, was created
Unveiling the mystery of visual information processing in human brain
Venue: arXiv cs.AI 2008
Year: 2008

It is generally accepted that human vision is an extremely powerful information processing system that facilitates our interaction with the surrounding world. However, despite extended and extensive research efforts, which encompass many exploration fields, the underlying fundamentals and operational principles of visual information processing in human brain remain unknown. We still are unable to figure out where and how along the path from eyes to the cortex the sensory input perceived by the retina is converted into a meaningful object representation, which can be consciously manipulated by the brain. Studying the vast literature considering the various aspects of brain information processing, I was surprised to learn that the respected scholarly discussion is totally indifferent to the basic keynote question: "What is information?" in general or "What is visual information?" in particular. In the old days, it was assumed that any scientific research approach has first to define its basic departure points. Why was it overlooked in brain information processing research remains a conundrum. In this paper, I am trying to find a remedy for this bizarre situation. I propose an uncommon definition of "information", which can be derived from Kolmogorov's Complexity Theory and Chaitin's notion of Algorithmic Information. Embracing this new definition leads to an inevitable revision of traditional dogmas that shape the state of the art of brain information processing research. I hope this revision would better serve the challenging goal of human visual information processing modeling.
On the complexity of finding a sun in a graph
Venue: arXiv cs.DM 2008
Year: 2008

The sun is the graph obtained from a cycle of length even and at least six by adding edges to make the even-indexed vertices pairwise adjacent. Suns play an important role in the study of strongly chordal graphs. A graph is chordal if it does not contain an induced cycle of length at least four. A graph is strongly chordal if it is chordal and every even cycle has a chord joining vertices whose distance on the cycle is odd. Farber proved that a graph is strongly chordal if and only if it is chordal and contains no induced suns. There are well known polynomial-time algorithms for recognizing a sun in a chordal graph. Recently, polynomial-time algorithms for finding a sun for a larger class of graphs, the so-called HHD-free graphs, have been discovered. In this paper, we prove the problem of deciding whether an arbitrary graph contains a sun in NP-complete.
An Improved Robust Fuzzy Extractor
Venue: arXiv cs.CR 2008
Year: 2008

We consider the problem of building robust fuzzy extractors, which allow two parties holding similar random variables W, W' to agree on a secret key R in the presence of an active adversary. Robust fuzzy extractors were defined by Dodis et al. in Crypto 2006 to be noninteractive, i.e., only one message P, which can be modified by an unbounded adversary, can pass from one party to the other. This allows them to be used by a single party at different points in time (e.g., for key recovery or biometric authentication), but also presents an additional challenge: what if R is used, and thus possibly observed by the adversary, before the adversary has a chance to modify P. Fuzzy extractors secure against such a strong attack are called post-application robust. We construct a fuzzy extractor with post-application robustness that extracts a shared secret key of up to (2m-n)/2 bits (depending on error-tolerance and security parameters), where n is the bit-length and m is the entropy of W. The previously best known result, also of Dodis et al., extracted up to (2m-n)/3 bits (depending on the same parameters).
On Wiretap Networks II
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of securing a multicast network against a wiretapper that can intercept the packets on a limited number of arbitrary network links of his choice. We assume that the network implements network coding techniques to simultaneously deliver all the packets available at the source to all the destinations. We show how this problem can be looked at as a network generalization of the Ozarow-Wyner Wiretap Channel of type II. In particular, we show that network security can be achieved by using the Ozarow-Wyner approach of coset coding at the source on top of the implemented network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretapped networks. We also derive new bounds on the required secure code alphabet size and an algorithm for code construction.
Session Initiation Protocol (SIP) Server Overload Control: Design and Evaluation
Venue: arXiv cs.NI 2008
Year: 2008

A Session Initiation Protocol (SIP) server may be overloaded by emergency-induced call volume, ``American Idol'' style flash crowd effects or denial of service attacks. The SIP server overload problem is interesting especially because the costs of serving or rejecting a SIP session can be similar. For this reason, the built-in SIP overload control mechanism based on generating rejection messages cannot prevent the server from entering congestion collapse under heavy load. The SIP overload problem calls for a pushback control solution in which the potentially overloaded receiving server may notify its upstream sending servers to have them send only the amount of load within the receiving server's processing capacity. The pushback framework can be achieved by either a rate-based feedback or a window-based feedback. The centerpiece of the feedback mechanism is the algorithm used to generate load regulation information. We propose three new window-based feedback algorithms and evaluate them together with two existing rate-based feedback algorithms. We compare the different algorithms in terms of the number of tuning parameters and performance under both steady and variable load. Furthermore, we identify two categories of fairness requirements for SIP overload control, namely, user-centric and provider-centric fairness. With the introduction of a new double-feed SIP overload control architecture, we show how the algorithms can meet those fairness criteria.
Restricted Mobility Improves Delay-Throughput Trade-offs in Mobile Ad-Hoc Networks
Venue: arXiv cs.PF 2008
Year: 2008

In this paper, we analyze asymptotic delay-throughput trade-offs in mobile ad-hoc networks comprising heterogeneous nodes with restricted mobility. We show that node spatial heterogeneity has the ability to drastically improve upon existing scaling laws established under the assumption that nodes are identical and uniformly visit the entire network area. In particular, we consider the situation in which each node moves around its own home-point according to a restricted mobility process which results into a spatial stationary distribution that decays as a power law of exponent delta with the distance from the home-point. For such restricted mobility model, we propose a novel class of scheduling and routing schemes, which significantly outperforms all delay-throughput results previously obtained in the case of identical nodes. In particular, for delta = 2 it is possible to achieve almost constant delay and almost constant per-node throughput (except for a poly-logarithmic factor) as the number of nodes increases, even without resorting to sophisticated coding or signal processing techniques.
On the Capacity of MIMO Interference Channels
Venue: arXiv cs.IT 2008
Year: 2008

The capacity region of a multiple-input-multiple-output interference channel (MIMO IC) where the channel matrices are square and invertible is studied. The capacity region for strong interference is established where the definition of strong interference parallels that of scalar channels. Moreover, the sum-rate capacity for Z interference, noisy interference, and mixed interference is established. These results generalize known results for the scalar Gaussian IC.
Resource Allocation Strategies for In-Network Stream Processing
Venue: arXiv cs.DC 2008
Year: 2008

In this paper we consider the operator mapping problem for in-network stream processing applications. In-network stream processing consists in applying a tree of operators in steady-state to multiple data objects that are continually updated at various locations on a network. Examples of in-network stream processing include the processing of data in a sensor network, or of continuous queries on distributed relational databases. We study the operator mapping problem in a ``constructive'' scenario, i.e., a scenario in which one builds a platform dedicated to the application buy purchasing processing servers with various costs and capabilities. The objective is to minimize the cost of the platform while ensuring that the application achieves a minimum steady-state throughput. The first contribution of this paper is the formalization of a set of relevant operator-placement problems as linear programs, and a proof that even simple versions of the problem are NP-complete. Our second contribution is the design of several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds for optimal solutions.
Intrusion Detection in Mobile Ad Hoc Networks Using Classification Algorithms
Venue: arXiv cs.CR 2008
Year: 2008

In this paper we present the design and evaluation of intrusion detection models for MANETs using supervised classification algorithms. Specifically, we evaluate the performance of the MultiLayer Perceptron (MLP), the Linear classifier, the Gaussian Mixture Model (GMM), the Naive Bayes classifier and the Support Vector Machine (SVM). The performance of the classification algorithms is evaluated under different traffic conditions and mobility patterns for the Black Hole, Forging, Packet Dropping, and Flooding attacks. The results indicate that Support Vector Machines exhibit high accuracy for almost all simulated attacks and that Packet Dropping is the hardest attack to detect.
Ranking Unit Squares with Few Visibilities
Venue: arXiv cs.CG 2008
Year: 2008

Given a set of n unit squares in the plane, the goal is to rank them in space in such a way that only few squares see each other vertically. We prove that ranking the squares according to the lexicographic order of their centers results in at most 3n-7 pairwise visibilities for n at least 4. We also show that this bound is best possible, by exhibiting a set of n squares with at least 3n-7 pairwise visibilities under any ranking.
Multihop Diversity in Wideband OFDM Systems: The Impact of Spatial Reuse and Frequency Selectivity
Venue: arXiv cs.IT 2008
Year: 2008

The goal of this paper is to establish which practical routing schemes for wireless networks are most suitable for wideband systems in the power-limited regime, which is, for example, a practically relevant mode of operation for the analysis of ultrawideband (UWB) mesh networks. For this purpose, we study the tradeoff between energy efficiency and spectral efficiency (known as the power-bandwidth tradeoff) in a wideband linear multihop network in which transmissions employ orthogonal frequency-division multiplexing (OFDM) modulation and are affected by quasi-static, frequency-selective fading. Considering open-loop (fixed-rate) and closed-loop (rate-adaptive) multihop relaying techniques, we characterize the impact of routing with spatial reuse on the statistical properties of the end-to-end conditional mutual information (conditioned on the specific values of the channel fading parameters and therefore treated as a random variable) and on the energy and spectral efficiency measures of the wideband regime. Our analysis particularly deals with the convergence of these end-to-end performance measures in the case of large number of hops, i.e., the phenomenon first observed in \cite{Oyman06b} and named as ``multihop diversity''. Our results demonstrate the realizability of the multihop diversity advantages in the case of routing with spatial reuse for wideband OFDM systems under wireless channel effects such as path-loss and quasi-static frequency-selective multipath fading.
On "Bit-Interleaved Coded Multiple Beamforming"
Venue: arXiv cs.IT 2008
Year: 2008

The interleaver design criteria described in [1] should take into account all error patterns of interest.
A Grateful Dead Analysis: The Relationship Between Concert and Listening Behavior
Venue: arXiv cs.CY 2008
Year: 2008

The Grateful Dead were an American band that was born out of the San Francisco, California psychedelic movement of the 1960s. The band played music together from 1965 to 1995 and is well known for concert performances containing extended improvisations and long and unique set lists. This article presents a comparative analysis between 1,590 of the Grateful Dead's concert set lists from 1972 to 1995 and 2,616,990 last.fm Grateful Dead listening events from August 2005 to October 2007. While there is a strong correlation between how songs were played in concert and how they are listened to by last.fm members, the outlying songs in this trend identify interesting aspects of the band and their fans 10 years after the band's dissolution.
Un cadre de conception pour réunir les modèles d'interaction et l'ingénierie des interfaces
Venue: arXiv cs.HC 2008
Year: 2008

We present HIC (Human-system Interaction Container), a general framework for the integration of advanced interaction in the software development process. We show how this framework allows to reconcile the software development methods (such MDA, MDE) with the architectural models of software design such as MVC or PAC. We illustrate our approach thanks to two different types of implementation for this concept in two different business areas: one software design pattern, MVIC (Model View Interaction Control) and one architectural model, IM (Interaction Middleware).
Group Divisible Codes and Their Application in the Construction of Optimal Constant-Composition Codes of Weight Three
Venue: arXiv cs.IT 2008
Year: 2008

The concept of group divisible codes, a generalization of group divisible designs with constant block size, is introduced in this paper. This new class of codes is shown to be useful in recursive constructions for constant-weight and constant-composition codes. Large classes of group divisible codes are constructed which enabled the determination of the sizes of optimal constant-composition codes of weight three (and specified distance), leaving only four cases undetermined. Previously, the sizes of constant-composition codes of weight three were known only for those of sufficiently large length.
Iterative ('Turbo') Multiuser Detectors For Impulse Radio Systems
Venue: arXiv cs.IT 2008
Year: 2008

In recent years, there has been a growing interest in multiple access communication systems that spread their transmitted energy over very large bandwidths. These systems, which are referred to as ultra wide-band (UWB) systems, have various advantages over narrow-band and conventional wide-band systems. The importance of multiuser detection for achieving high data or low bit error rates in these systems has already been established in several studies. This paper presents iterative ('turbo') multiuser detection for impulse radio (IR) UWB systems over multipath channels. While this approach is demonstrated for UWB signals, it can also be used in other systems that use similar types of signaling. When applied to the type of signals used by UWB systems, the complexity of the proposed detector can be quite low. Also, two very low complexity implementations of the iterative multiuser detection scheme are proposed based on Gaussian approximation and soft interference cancellation. The performance of these detectors is assessed using simulations that demonstrate their favorable properties.
The Transport Capacity of a Wireless Network is a Subadditive Euclidean Functional
Venue: arXiv cs.IT 2008
Year: 2008

The transport capacity of a dense ad hoc network with n nodes scales like \sqrt(n). We show that the transport capacity divided by \sqrt(n) approaches a non-random limit with probability one when the nodes are i.i.d. distributed on the unit square. We prove that the transport capacity under the protocol model is a subadditive Euclidean functional and use the machinery of subadditive functions in the spirit of Steele to show the existence of the limit.
Perturbed affine arithmetic for invariant computation in numerical program analysis
Venue: arXiv cs.LO 2008
Year: 2008

We completely describe a new domain for abstract interpretation of numerical programs. Fixpoint iteration in this domain is proved to converge to finite precise invariants for (at least) the class of stable linear recursive filters of any order. Good evidence shows it behaves well also for some non-linear schemes. The result, and the structure of the domain, rely on an interesting interplay between order and topology.
Reducing Spreadsheet Risk with FormulaDataSleuth
Venue: arXiv cs.HC 2008
Year: 2008

A new MS Excel application has been developed which seeks to reduce the risks associated with the development, operation and auditing of Excel spreadsheets. FormulaDataSleuth provides a means of checking spreadsheet formulas and data as they are developed or used, enabling the users to identify actual or potential errors quickly and thereby halt their propagation. In this paper, we will describe, with examples, how the application works and how it can be applied to reduce the risks associated with Excel spreadsheets.
Algorithmic randomness and splitting of supermartingales
Venue: arXiv cs.IT 2008
Year: 2008

Randomness in the sense of Martin-Löf can be defined in terms of lower semicomputable supermartingales. We show that such a supermartingale cannot be replaced by a pair of supermartingales that bet only on the even bits (the first one) and on the odd bits (the second one) knowing all preceding bits.