OpenRaiser/Intern-Atlas huggingface dataset:
Remarks on the Criteria of Constructing MIMO-MAC DMT Optimal Codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we investigate the criteria proposed by Coronel et al. for constructing MIMO MAC-DMT optimal codes over several classes of fading channels. We first give a counterexample showing their DMT result is not correct when the channel is frequency-selective. For the case of symmetric MIMO-MAC flat fading channels, their DMT result reduces to exactly the same as that derived by Tse et al., and we therefore focus on their criteria for constructing MAC-DMT optimal codes, especially when the number of receive antennas is sufficiently large. In such case, we show their criterion is equivalent to requiring the codes of any subset of users to satisfy a joint non-vanishing determinant criterion when the system operates in the antenna pooling regime. Finally an upper bound on the product of minimum eigenvalues of the difference matrices is provided, and is used to show any MIMO-MAC codes satisfying their criterion can possibly exist only when the target multiplexing gain is small.
Exact generation of acyclic deterministic finite automata
Venue: arXiv cs.FL 2009
Year: 2009

We give a canonical representation for trim acyclic deterministic finite automata (Adfa) with n states over an alphabet of k symbols. Using this normal form, we present a backtracking algorithm for the exact generation of Adfas. This algorithm is a non trivial adaptation of the algorithm for the exact generation of minimal acyclic deterministic finite automata, presented by Almeida et al.
Multipath Wireless Network Coding: A Population Game Perspective
Venue: arXiv cs.GT 2009
Year: 2009

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and ask the question: how do we attain the lowest possible number of transmissions to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the ``reverse carpooling'' advantage of network coding in order to decrease the number of transmissions used. We call such coded hops as ``hyper-links''. With the reverse carpooling technique longer paths might be cheaper than shorter ones. However, there is a prisoners dilemma type situation among sources -- the network coding advantage is realized only if there is traffic in both directions of a shared path. We develop a two-level distributed control scheme that decouples user choices from each other by declaring a hyper-link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. We show that such a controller is stable, and verify our analytical insights by simulation.
Geometric Analysis of the Conformal Camera for Intermediate-Level Vision and Perisaccadic Perception
Venue: arXiv cs.CV 2009
Year: 2009

A binocular system developed by the author in terms of projective Fourier transform (PFT) of the conformal camera, which numerically integrates the head, eyes, and visual cortex, is used to process visual information during saccadic eye movements. Although we make three saccades per second at the eyeball's maximum speed of 700 deg/sec, our visual system accounts for these incisive eye movements to produce a stable percept of the world. This visual constancy is maintained by neuronal receptive field shifts in various retinotopically organized cortical areas prior to saccade onset, giving the brain access to visual information from the saccade's target before the eyes' arrival. It integrates visual information acquisition across saccades. Our modeling utilizes basic properties of PFT. First, PFT is computable by FFT in complex logarithmic coordinates that approximate the retinotopy. Second, a translation in retinotopic (logarithmic) coordinates, modeled by the shift property of the Fourier transform, remaps the presaccadic scene into a postsaccadic reference frame. It also accounts for the perisaccadic mislocalization observed by human subjects in laboratory experiments. Because our modeling involves cross-disciplinary areas of conformal geometry, abstract and computational harmonic analysis, computational vision, and visual neuroscience, we include the corresponding background material and elucidate how these different areas interwove in our modeling of primate perception. In particular, we present the physiological and behavioral facts underlying the neural processes related to our modeling. We also emphasize the conformal camera's geometry and discuss how it is uniquely useful in the intermediate-level vision computational aspects of natural scene understanding.
Construction of Hilbert Transform Pairs of Wavelet Bases and Gabor-like Transforms
Venue: arXiv cs.IT 2009
Year: 2009

We propose a novel method for constructing Hilbert transform (HT) pairs of wavelet bases based on a fundamental approximation-theoretic characterization of scaling functions--the B-spline factorization theorem. In particular, starting from well-localized scaling functions, we construct HT pairs of biorthogonal wavelet bases of L^2(R) by relating the corresponding wavelet filters via a discrete form of the continuous HT filter. As a concrete application of this methodology, we identify HT pairs of spline wavelets of a specific flavor, which are then combined to realize a family of complex wavelets that resemble the optimally-localized Gabor function for sufficiently large orders. Analytic wavelets, derived from the complexification of HT wavelet pairs, exhibit a one-sided spectrum. Based on the tensor-product of such analytic wavelets, and, in effect, by appropriately combining four separable biorthogonal wavelet bases of L^2(R^2), we then discuss a methodology for constructing 2D directional-selective complex wavelets. In particular, analogous to the HT correspondence between the components of the 1D counterpart, we relate the real and imaginary components of these complex wavelets using a multi-dimensional extension of the HT--the directional HT. Next, we construct a family of complex spline wavelets that resemble the directional Gabor functions proposed by Daugman. Finally, we present an efficient FFT-based filterbank algorithm for implementing the associated complex wavelet transform.
On the Shiftability of Dual-Tree Complex Wavelet Transforms
Venue: arXiv cs.IT 2009
Year: 2009

The dual-tree complex wavelet transform (DT-CWT) is known to exhibit better shift-invariance than the conventional discrete wavelet transform. We propose an amplitude-phase representation of the DT-CWT which, among other things, offers a direct explanation for the improvement in the shift-invariance. The representation is based on the shifting action of the group of fractional Hilbert transform (fHT) operators, which extends the notion of arbitrary phase-shifts from sinusoids to finite-energy signals (wavelets in particular). In particular, we characterize the shiftability of the DT-CWT in terms of the shifting property of the fHTs. At the heart of the representation are certain fundamental invariances of the fHT group, namely that of translation, dilation, and norm, which play a decisive role in establishing the key properties of the transform. It turns out that these fundamental invariances are exclusive to this group. Next, by introducing a generalization of the Bedrosian theorem for the fHT operator, we derive an explicitly understanding of the shifting action of the fHT for the particular family of wavelets obtained through the modulation of lowpass functions (e.g., the Shannon and Gabor wavelet). This, in effect, links the corresponding dual-tree transform with the framework of windowed-Fourier analysis. Finally, we extend these ideas to the multi-dimensional setting by introducing a directional extension of the fHT, the fractional directional Hilbert transform. In particular, we derive a signal representation involving the superposition of direction-selective wavelets with appropriate phase-shifts, which helps explain the improved shift-invariance of the transform along certain preferential directions.
Cognitive Dimensions Analysis of Interfaces for Information Seeking
Venue: arXiv cs.HC 2009
Year: 2009

Cognitive Dimensions is a framework for analyzing human-computer interaction. It is used for meta-analysis, that is, for talking about characteristics of systems without getting bogged down in details of a particular implementation. In this paper, I discuss some of the dimensions of this theory and how they can be applied to analyze information seeking interfaces. The goal of this analysis is to introduce a useful vocabulary that practitioners and researchers can use to describe systems, and to guide interface design toward more usable and useful systems
Level Crossing Rate and Average Fade Duration of the Double Nakagami-m Random Process and Application in MIMO Keyhole Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

We present novel exact expressions and accurate closed-form approximations for the level crossing rate (LCR) and the average fade duration (AFD) of the double Nakagami-m random process. These results are then used to study the second order statistics of multiple input multiple output (MIMO) keyhole fading channels with space-time block coding. Numerical and computer simulation examples validate the accuracy of the presented mathematical analysis and show the tightness of the proposed approximations.
Level Crossing Rate and Average Fade Duration of EGC Systems with Cochannel Interference in Rayleigh Fading
Venue: arXiv cs.IT 2009
Year: 2009

Both the first-order signal statistics (e.g. the outage probability) and the second-order signal statistics (e.g. the average level crossing rate, LCR, and the average fade duration, AFD) are important design criteria and performance measures for the wireless communication systems, including the equal gain combining (EGC) systems in presence of the cochannel interference (CCI). Although the analytical expressions for the outage probability of the coherent EGC systems exposed to CCI and various fading channels are already known, the respective ones for the average LCR and the AFD are not available in the literature. This paper presents such analytical expressions for the Rayleigh fading channel, which are obtained by utilizing a novel analytical approach that does not require the explicit expression for the joint PDF of the instantaneous output signal-to-interference ratio (SIR) and its time derivative. Applying the characteristic function method and the Beaulieu series, we determined the average LCR and the AFD at the output of an interference-limited EGC system with an arbitrary diversity order and an arbitrary number of cochannel interferers in forms of an infinite integral and an infinite series. For the dual diversity case, the respective expressions are derived in closed forms in terms of the gamma and the beta functions.
Tracing Technique for Blaster Attack
Venue: arXiv cs.CR 2009
Year: 2009

Blaster worm of 2003 is still persistent, the infection appears to have successfully transitioned to new hosts as the original systems are cleaned or shut off, suggesting that the Blaster worm, and other similar worms, will remain significant Internet threats for many years after their initial release. This paper is to propose technique on tracing the Blaster attack from various logs in different OSI layers based on fingerprint of Blaster attack on victim logs, attacker logs and IDS alert log. The researchers intended to do a preliminary investigation upon this particular attack so that it can be used for further research in alert correlation and computer forensic investigation.
A DHT Based Measure of Randomness
Venue: arXiv cs.CR 2009
Year: 2009

This paper presents a new discrete Hilbert transform (DHT) based measure of randomness for discrete sequences. The measure has been used to test three different classes of sequences with satisfactory results.
Cooperative Routing for Wireless Networks using Mutual-Information Accumulation
Venue: arXiv cs.IT 2009
Year: 2009

Cooperation between the nodes of wireless multihop networks can increase communication reliability, reduce energy consumption, and decrease latency. The possible improvements are even greater when nodes perform mutual information accumulation using rateless codes. In this paper, we investigate routing problems in such networks. Given a network, a source, and a destination, our objective is to minimize end-to-end transmission delay under energy and bandwidth constraints. We provide an algorithm that determines which nodes should participate in forwarding the message and what resources (time, energy, bandwidth) should be allocated to each. Our approach factors into two sub-problems, each of which can be solved efficiently. For any transmission order we show that solving for the optimum resource allocation can be formulated as a linear programming problem. We then show that the transmission order can be improved systematically by swapping nodes based on the solution of the linear program. Solving a sequence of linear programs leads to a locally optimal solution in a very efficient manner. In comparison to the proposed cooperative routing solution, it is observed that conventional shortest path multihop routing typically incurs additional delays and energy expenditures on the order of 70%. Our first algorithm is centralized, assuming that routing computations can be done at a central processor with full access to channel state information for the entire system. We also design two distributed routing algorithms that require only local channel state information. We provide simulations showing that for the same networks the distributed algorithms find routes that are only about two to five percent less efficient than the centralized algorithm.
On the Expressiveness of Line Drawings
Venue: arXiv cs.OH 2009
Year: 2009

Can expressiveness of a drawing be traced with a computer? In this study a neural network (perceptron) and a support vector machine are used to classify line drawings. To do this the line drawings are attributed values according to a kinematic model and a diffusion model for the lines they consist of. The values for both models are related to looking times. Extreme values according to these models, that is both extremely short and extremely long looking times, are interpreted as indicating expressiveness. The results strongly indicate that expressiveness in this sense can be detected, at least with a neural network.
Graph-Theoretic Solutions to Computational Geometry Problems
Venue: arXiv cs.CG 2009
Year: 2009

Many problems in computational geometry are not stated in graph-theoretic terms, but can be solved efficiently by constructing an auxiliary graph and performing a graph-theoretic algorithm on it. Often, the efficiency of the algorithm depends on the special properties of the graph constructed in this way. We survey the art gallery problem, partition into rectangles, minimum-diameter clustering, rectilinear cartogram construction, mesh stripification, angle optimization in tilings, and metric embedding from this perspective.
SocialFilter: Collaborative Spam Mitigation using Social Networks
Venue: arXiv cs.CR 2009
Year: 2009

Spam mitigation can be broadly classified into two main approaches: a) centralized security infrastructures that rely on a limited number of trusted monitors to detect and report malicious traffic; and b) highly distributed systems that leverage the experiences of multiple nodes within distinct trust domains. The first approach offers limited threat coverage and slow response times, and it is often proprietary. The second approach is not widely adopted, partly due to the lack of guarantees regarding the trustworthiness of nodes that comprise the system. Our proposal, SocialFilter, aims to achieve the trustworthiness of centralized security services and the wide coverage, responsiveness and inexpensiveness of large-scale collaborative spam mitigation. We propose a large-scale distributed system that enables clients with no email classification functionality to query the network on the behavior of a host. A SocialFilter node builds trust for its peers by auditing their behavioral reports and by leveraging the social network of SocialFilter administrators. The node combines the confidence its peers have in their own reports and the trust it places on its peers to derive the likelihood that a host is spamming. The simulation-based evaluation of our approach indicates its potential under a real-world deployment: during a simulated spam campaign, SocialFilternodes characterized 92% of spam bot connections with confidence greater than 50%, while yielding no false positives
Enhancing XML Data Warehouse Query Performance by Fragmentation
Venue: arXiv cs.DB 2009
Year: 2009

XML data warehouses form an interesting basis for decision-support applications that exploit heterogeneous data from multiple sources. However, XML-native database systems currently suffer from limited performances in terms of manageable data volume and response time for complex analytical queries. Fragmenting and distributing XML data warehouses (e.g., on data grids) allow to address both these issues. In this paper, we work on XML warehouse fragmentation. In relational data warehouses, several studies recommend the use of derived horizontal fragmentation. Hence, we propose to adapt it to the XML context. We particularly focus on the initial horizontal fragmentation of dimensions' XML documents and exploit two alternative algorithms. We experimentally validate our proposal and compare these alternatives with respect to a unified XML warehouse model we advocate for.
On Relating Edges in Graphs without Cycles of Length 4
Venue: arXiv cs.DM 2009
Year: 2009

An edge xy is relating in the graph G if there is an independent set S, containing neither x nor y, such that S_{x} and S_{y} are both maximal independent sets in G. It is an NP-complete problem to decide whether an edge is relating (Brown, Nowakowski, Zverovich, 2007). We show that the problem remains NP-complete even for graphs without cycles of length 4 and 5. On the other hand, for graphs without cycles of length 4 and 6, the problem can be solved in polynomial time.
Complexity of Planar Embeddability of Trees inside Simple Polygons
Venue: arXiv cs.CG 2009
Year: 2009

Geometric embedding of graphs in a point set in the plane is a well known problem. In this paper, the complexity of a variant of this problem, where the point set is bounded by a simple polygon, is considered. Given a point set in the plane bounded by a simple polygon and a free tree, we show that deciding whether there is a planar straight-line embedding of the tree on the point set inside the simple polygon is NP-complete. This implies that the straight-line constrained point-set embedding of trees is also NP-complete, which was posed as an open problem in [8].
Channel Protection: Random Coding Meets Sparse Channels
Venue: arXiv cs.IT 2009
Year: 2009

Multipath interference is an ubiquitous phenomenon in modern communication systems. The conventional way to compensate for this effect is to equalize the channel by estimating its impulse response by transmitting a set of training symbols. The primary drawback to this type of approach is that it can be unreliable if the channel is changing rapidly. In this paper, we show that randomly encoding the signal can protect it against channel uncertainty when the channel is sparse. Before transmission, the signal is mapped into a slightly longer codeword using a random matrix. From the received signal, we are able to simultaneously estimate the channel and recover the transmitted signal. We discuss two schemes for the recovery. Both of them exploit the sparsity of the underlying channel. We show that if the channel impulse response is sufficiently sparse, the transmitted signal can be recovered reliably.
Algorithms for Placing Monitors in a Flow Network
Venue: arXiv cs.DS 2009
Year: 2009

In the Flow Edge-Monitor Problem, we are given an undirected graph G=(V,E), an integer k > 0 and some unknown circulation ψon G. We want to find a set of k edges in G, so that if we place k monitors on those edges to measure the flow along them, the total number of edges for which the flow can be uniquely determined is maximized. In this paper, we first show that the Flow Edge-Monitor Problem is NP-hard, and then we give two approximation algorithms: a 3-approximation algorithm with running time O((m+n)^2) and a 2-approximation algorithm with running time O((m+n)^3), where n = |V| and m=|E|.
Learning, complexity and information density
Venue: arXiv cs.IT 2009
Year: 2009

What is the relationship between the complexity of a learner and the randomness of his mistakes? This question was posed in \cite{rat0903} who showed that the more complex the learner the higher the possibility that his mistakes deviate from a true random sequence. In the current paper we report on an empirical investigation of this problem. We investigate two characteristics of randomness, the stochastic and algorithmic complexity of the binary sequence of mistakes. A learner with a Markov model of order $k$ is trained on a finite binary sequence produced by a Markov source of order $k^{*}$ and is tested on a different random sequence. As a measure of learner's complexity we define a quantity called the \emph{sysRatio}, denoted by $ρ$, which is the ratio between the compressed and uncompressed lengths of the binary string whose $i^{th}$ bit represents the maximum \emph{a posteriori} decision made at state $i$ of the learner's model. The quantity $ρ$ is a measure of information density. The main result of the paper shows that this ratio is crucial in answering the above posed question. The result indicates that there is a critical threshold $ρ^{*}$ such that when $ρ\leqρ^{*}$ the sequence of mistakes possesses the following features: (1)\emph{}low divergence $Δ$ from a random sequence, (2) low variance in algorithmic complexity. When $ρ>ρ^{*}$, the characteristics of the mistake sequence changes sharply towards a\emph{}high\emph{$Δ$} and high variance in algorithmic complexity.
Hardware Virtualization Support In INTEL, AMD And IBM Power Processors
Venue: arXiv cs.AR 2009
Year: 2009

At present, the mostly used and developed mechanism is hardware virtualization which provides a common platform to run multiple operating systems and applications in independent partitions. More precisely, it is all about resource virtualization as the term hardware virtualization is emphasized. In this paper, the aim is to find out the advantages and limitations of current virtualization techniques, analyze their cost and performance and also depict which forthcoming hardware virtualization techniques will able to provide efficient solutions for multiprocessor operating systems. This is done by making a methodical literature survey and statistical analysis of the benchmark reports provided by SPEC (Standard Performance Evaluation Corporation) and TPC (Transaction processing Performance Council). Finally, this paper presents the current aspects of hardware virtualization which will help the IT managers of the large organizations to take effective decision while choosing server with virtualization support. Again, the future works described in section 4 of this paper focuses on some real world challenges such as abstraction of multiple servers, language level virtualization, pre-virtualization etc. which may be point of great interest for the researchers.