OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Filtering of Malicious IP Sources
Venue: arXiv cs.NI 2008
Year: 2008

How can we protect the network infrastructure from malicious traffic, such as scanning, malicious code propagation, and distributed denial-of-service (DDoS) attacks? One mechanism for blocking malicious traffic is filtering: access control lists (ACLs) can selectively block traffic based on fields of the IP header. Filters (ACLs) are already available in the routers today but are a scarce resource because they are stored in the expensive ternary content addressable memory (TCAM). In this paper, we develop, for the first time, a framework for studying filter selection as a resource allocation problem. Within this framework, we study five practical cases of source address/prefix filtering, which correspond to different attack scenarios and operator's policies. We show that filter selection optimization leads to novel variations of the multidimensional knapsack problem and we design optimal, yet computationally efficient, algorithms to solve them. We also evaluate our approach using data from Dshield.org and demonstrate that it brings significant benefits in practice. Our set of algorithms is a building block that can be immediately used by operators and manufacturers to block malicious traffic in a cost-efficient way.
On the Complexity of Matroid Isomorphism Problem
Venue: arXiv cs.CC 2008
Year: 2008

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in $Σ_2^p$. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be $Σ_2^p$-complete and is $\co\NP$-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism. We give a polynomial time Turing reduction from graphic matroid isomorphism problem to the graph isomorphism problem. Using this, we are able to show that graphic matroid isomorphism testing for planar graphs can be done in deterministic polynomial time. We then give a polynomial time many-one reduction from bounded rank matroid isomorphism problem to graphic matroid isomorphism, thus showing that all the above problems are polynomial time equivalent. Further, for linear and graphic matroids, we prove that the automorphism problem is polynomial time equivalent to the corresponding isomorphism problems. In addition, we give a polynomial time membership test algorithm for the automorphism group of a graphic matroid.
LACK - a VoIP Steganographic Method
Venue: arXiv cs.CR 2008
Year: 2008

The paper presents a new steganographic method called LACK (Lost Audio PaCKets Steganography) which is intended mainly for VoIP. The method is presented in a broader context of network steganography and of VoIP steganography in particular. The analytical results presented in the paper concern the influence of LACK's hidden data insertion procedure on the method's impact on quality of voice transmission and its resistance to steganalysis.
Two Models for Noisy Feedback in MIMO Channels
Venue: arXiv cs.IT 2008
Year: 2008

Two distinct models of feedback, suited for FDD (Frequency Division Duplex) and TDD (Frequency Division Duplex) systems respectively, have been widely studied in the literature. In this paper, we compare these two models of feedback in terms of the diversity multiplexing tradeoff for varying amount of channel state information at the terminals. We find that, when all imperfections are accounted for, the maximum achievable diversity order in FDD systems matches the diversity order in TDD systems. TDD systems achieve better diversity order at higher multiplexing gains. In FDD systems, the maximum diversity order can be achieved with just a single bit of feedback. Additional bits of feedback (perfect or imperfect) do not affect the diversity order if the receiver does not know the channel state information.
Dynamic Indexability: The Query-Update Tradeoff for One-Dimensional Range Queries
Venue: arXiv cs.DS 2008
Year: 2008

The B-tree is a fundamental secondary index structure that is widely used for answering one-dimensional range reporting queries. Given a set of $N$ keys, a range query can be answered in $O(\log_B \nm + \frac{K}{B})$ I/Os, where $B$ is the disk block size, $K$ the output size, and $M$ the size of the main memory buffer. When keys are inserted or deleted, the B-tree is updated in $O(\log_B N)$ I/Os, if we require the resulting changes to be committed to disk right away. Otherwise, the memory buffer can be used to buffer the recent updates, and changes can be written to disk in batches, which significantly lowers the amortized update cost. A systematic way of batching up updates is to use the logarithmic method, combined with fractional cascading, resulting in a dynamic B-tree that supports insertions in $O(\frac{1}{B}\log\nm)$ I/Os and queries in $O(\log\nm + \frac{K}{B})$ I/Os. Such bounds have also been matched by several known dynamic B-tree variants in the database literature. In this paper, we prove that for any dynamic one-dimensional range query index structure with query cost $O(q+\frac{K}{B})$ and amortized insertion cost $O(u/B)$, the tradeoff $q\cdot \log(u/q) = Ω(\log B)$ must hold if $q=O(\log B)$. For most reasonable values of the parameters, we have $\nm = B^{O(1)}$, in which case our query-insertion tradeoff implies that the bounds mentioned above are already optimal. Our lower bounds hold in a dynamic version of the {\em indexability model}, which is of independent interests.
Ergodic Capacity Analysis of Amplify-and-Forward MIMO Dual-Hop Systems
Venue: arXiv cs.IT 2008
Year: 2008

This paper presents an analytical characterization of the ergodic capacity of amplify-and-forward (AF) MIMO dual-hop relay channels, assuming that the channel state information is available at the destination terminal only. In contrast to prior results, our expressions apply for arbitrary numbers of antennas and arbitrary relay configurations. We derive an expression for the exact ergodic capacity, simplified closed-form expressions for the high SNR regime, and tight closed-form upper and lower bounds. These results are made possible to employing recent tools from finite-dimensional random matrix theory to derive new closed-form expressions for various statistical properties of the equivalent AF MIMO dual-hop relay channel, such as the distribution of an unordered eigenvalue and certain random determinant properties. Based on the analytical capacity expressions, we investigate the impact of the system and channel characteristics, such as the antenna configuration and the relay power gain. We also demonstrate a number of interesting relationships between the dual-hop AF MIMO relay channel and conventional point-to-point MIMO channels in various asymptotic regimes.
Trellis-coded quantization for public-key steganography
Venue: arXiv cs.MM 2008
Year: 2008

This paper deals with public-key steganography in the presence of a passive warden. The aim is to hide secret messages within cover-documents without making the warden suspicious, and without any preliminar secret key sharing. Whereas a practical attempt has been already done to provide a solution to this problem, it suffers of poor flexibility (since embedding and decoding steps highly depend on cover-signals statistics) and of little capacity compared to recent data hiding techniques. Using the same framework, this paper explores the use of trellis-coded quantization techniques (TCQ and turbo TCQ) to design a more efficient public-key scheme. Experiments on audio signals show great improvements considering Cachin's security criterion.
Optimal Tracking of Distributed Heavy Hitters and Quantiles
Venue: arXiv cs.DS 2008
Year: 2008

We consider the the problem of tracking heavy hitters and quantiles in the distributed streaming model. The heavy hitters and quantiles are two important statistics for characterizing a data distribution. Let $A$ be a multiset of elements, drawn from the universe $U=\{1,...,u\}$. For a given $0 \le ϕ\le 1$, the $ϕ$-heavy hitters are those elements of $A$ whose frequency in $A$ is at least $ϕ|A|$; the $ϕ$-quantile of $A$ is an element $x$ of $U$ such that at most $ϕ|A|$ elements of $A$ are smaller than $A$ and at most $(1-ϕ)|A|$ elements of $A$ are greater than $x$. Suppose the elements of $A$ are received at $k$ remote {\em sites} over time, and each of the sites has a two-way communication channel to a designated {\em coordinator}, whose goal is to track the set of $ϕ$-heavy hitters and the $ϕ$-quantile of $A$ approximately at all times with minimum communication. We give tracking algorithms with worst-case communication cost $O(k/\eps \cdot \log n)$ for both problems, where $n$ is the total number of items in $A$, and $\eps$ is the approximation error. This substantially improves upon the previous known algorithms. We also give matching lower bounds on the communication costs for both problems, showing that our algorithms are optimal. We also consider a more general version of the problem where we simultaneously track the $ϕ$-quantiles for all $0 \le ϕ\le 1$.
Block-Sparsity: Coherence and Efficient Recovery
Venue: arXiv cs.IT 2008
Year: 2008

We consider compressed sensing of block-sparse signals, i.e., sparse signals that have nonzero coefficients occuring in clusters. Based on an uncertainty relation for block-sparse signals, we define a block-coherence measure and we show that a block-version of the orthogonal matching pursuit algorithm recovers block k-sparse signals in no more than k steps if the block-coherence is sufficiently small. The same condition on block-sparsity is shown to guarantee successful recovery through a mixed l2/l1 optimization approach. The significance of the results lies in the fact that making explicit use of block-sparsity can yield better reconstruction properties than treating the signal as being sparse in the conventional sense thereby ignoring the additional structure in the problem.
Which notes are Vadi-Samvadi in Raga Rageshree?
Venue: arXiv cs.SD 2008
Year: 2008

The notes which play the most important and second most important roles in expressing a raga are called Vadi and Samvadi swars respectively in (North) Indian Classical music. Like Bageshree, Bhairavi, Shankara, Hamir and Kalingra, Rageshree is another controversial raga so far as the choice of Vadi-Samvadi selection is concerned where there are two different opinions. In the present work, a two minute vocal recording of raga Rageshree is subjected to a careful statistical analysis. Our analysis is broken into three phases: first half, middle half and last half. Under a multinomial model set up holding appreciably in the first two phases, only one opinion is found acceptable. In the last phase the distribution seems to be quasi multinomial, characterized by an unstable nature of relative occurrence of pitch of all the notes and although the note whose relative occurrence of pitch suddenly shoots is the Vadi swar selected from our analysis of the first two phases, we take it as an outlier demanding a separate treatment like any other in statistics. Selection of Vadi-Samvadi notes in a quasi-multinomial set up is still an open research problem. An interesting musical cocktail is proposed, however, embedding several ideas like melodic property of notes, note combinations and pitch movements between notes, using some weighted combination of psychological and statistical stability of notes along with watching carefully the sudden shoot of one or more notes whenever there is enough evidence that multinomial model has broken down.
Stroke Fragmentation based on Geometry Features and HMM
Venue: arXiv cs.HC 2008
Year: 2008

Stroke fragmentation is one of the key steps in pen-based interaction. In this letter, we present a unified HMM-based stroke fragmentation technique that can do segment point location and primitive type determination simultaneously. The geometry features included are used to evaluate local features, and the HMM model is utilized to measure the global drawing context. Experiments prove that the model can efficiently represent smooth curves as well as strokes made up of arbitrary lines and circular arcs.
Graph Polynomials: From Recursive Definitions To Subset Expansion Formulas
Venue: arXiv cs.LO 2008
Year: 2008

Many graph polynomials, such as the Tutte polynomial, the interlace polynomial and the matching polynomial, have both a recursive definition and a defining subset expansion formula. In this paper we present a general, logic-based framework which gives a precise meaning to recursive definitions of graph polynomials. We then prove that in this framework every recursive definition of a graph polynomial can be converted into a subset expansion formula.
Stability of Curvature Measures
Venue: arXiv cs.CG 2008
Year: 2008

We address the problem of curvature estimation from sampled compact sets. The main contribution is a stability result: we show that the gaussian, mean or anisotropic curvature measures of the offset of a compact set K with positive $μ$-reach can be estimated by the same curvature measures of the offset of a compact set K' close to K in the Hausdorff sense. We show how these curvature measures can be computed for finite unions of balls. The curvature measures of the offset of a compact set with positive $μ$-reach can thus be approximated by the curvature measures of the offset of a point-cloud sample. These results can also be interpreted as a framework for an effective and robust notion of curvature.
Pilot-Symbol-Assisted Communications with Noncausal and Causal Wiener Filters
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, pilot-assisted transmission over time-selective flat fading channels is studied. It is assumed that noncausal and causal Wiener filters are employed at the receiver to perform channel estimation with the aid of training symbols sent periodically by the transmitter. For both filters, the variances of estimate errors are obtained from the Doppler power spectrum of the channel. Subsequently, achievable rate expressions are provided. The training period, and data and training power allocations are jointly optimized by maximizing the achievable rate expressions. Numerical results are obtained by modeling the fading as a Gauss-Markov process. The achievable rates of causal and noncausal filtering approaches are compared. For the particular ranges of parameters considered in the paper, the performance loss incurred by using a causal filter as opposed to a noncausal filter is shown to be small. The impact of aliasing that occurs in the undersampled version of the channel Doppler spectrum due to fast fading is analyzed. Finally, energy-per-bit requirements are investigated in the presence of noncausal and causal Wiener filters.
Fast phylogeny reconstruction through learning of ancestral sequences
Venue: arXiv cs.DS 2008
Year: 2008

Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have been two approaches to this problem: reconstructing partial but reliable information about the tree (\cite{Mo07, DMR08,DHJ06,GMS08}), and reaching "deeper" in the tree through reconstruction of ancestral sequences. In the latter category, \cite{DMR06} settled an important conjecture of M.Steel, showing that, under the CFN model of evolution, all trees on $n$ leaves with edge lengths bounded by the Ising model phase transition can be recovered with high probability from genomes of length $O(\log n)$ with a polynomial time algorithm. Their methods had a running time of $O(n^{10})$. Here we enhance our methods from \cite{DHJ06} with the learning of ancestral sequences and provide an algorithm for reconstructing a sub-forest of the tree which is reliable given available data, without requiring a-priori known bounds on the edge lengths of the tree. Our methods are based on an intuitive minimum spanning tree approach and run in $O(n^3)$ time. For the case of full reconstruction of trees with edges under the phase transition, we maintain the same sequence length requirements as \cite{DMR06}, despite the considerably faster running time.
Two Dimensional Connectivity for Vehicular Ad-Hoc Networks
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, we focus on two-dimensional connectivity in sparse vehicular ad hoc networks (VANETs). In this respect, we find thresholds for the arrival rates of vehicles at entrances of a block of streets such that the connectivity is guaranteed for any desired probability. To this end, we exploit a mobility model recently proposed for sparse VANETs, based on BCMP open queuing networks and solve the related traffic equations to find the traffic characteristics of each street and use the results to compute the exact probability of connectivity along these streets. Then, we use the results from percolation theory and the proposed fast algorithms for evaluation of bond percolation problem in a random graph corresponding to the block of the streets. We then find sufficiently accurate two dimensional connectivity-related parameters, such as the average number of intersections connected to each other and the size of the largest set of inter-connected intersections. We have also proposed lower bounds for the case of heterogeneous network with two transmission ranges. In the last part of the paper, we apply our method to several numerical examples and confirm our results by simulations.
Performance of a greedy algorithm for edge covering by cliques in interval graphs
Venue: arXiv cs.DM 2008
Year: 2008

In this paper a greedy algorithm to detect conflict cliques in interval graphs and circular-arc graphs is analyzed. In a graph, a stable set requires that at most one vertex is chosen for each edge. It is equivalent to requiring that at most one vertex for each maximal clique is chosen. We show that this algorithm finds all maximal cliques for interval graphs, i.e. it can compute the convex hull of the stable set polytope. In case of circular-arc graphs, the algorithm is not able to detect all maximal cliques, yet remaining correct. This problem occurs in the context of railway scheduling. A train requests the allocation of a railway infrastructure resource for a specific time interval. As one is looking for conflict-free train schedules, the used resource allocation intervals in a schedule must not overlap. The conflict-free choices of used intervals for each resource correspond to stable sets in the interval graph associated to the allocation time intervals.
Optimization of Decentralized Scheduling for Physic Applications in Grid Environments
Venue: arXiv cs.DC 2008
Year: 2008

This paper presents a scheduling framework that is configured for, and used in physic systems. Our work addresses the problem of scheduling various computationally intensive and data intensive applications that are required for extracting information from satellite images. The proposed solution allows mapping of image processing applications onto available resources. The scheduling is done at the level of groups of concurrent applications. It demonstrates a very good behavior for scheduling and executing groups of applications, while also achieving a near-optimal utilization of the resources.
An Efficient PTAS for Two-Strategy Anonymous Games
Venue: arXiv cs.GT 2008
Year: 2008

We present a novel polynomial time approximation scheme for two-strategy anonymous games, in which the players' utility functions, although potentially different, do not differentiate among the identities of the other players. Our algorithm computes an $eps$-approximate Nash equilibrium of an $n$-player 2-strategy anonymous game in time $poly(n) (1/eps)^{O(1/eps^2)}$, which significantly improves upon the running time $n^{O(1/eps^2)}$ required by the algorithm of Daskalakis & Papadimitriou, 2007. The improved running time is based on a new structural understanding of approximate Nash equilibria: We show that, for any $eps$, there exists an $eps$-approximate Nash equilibrium in which either only $O(1/eps^3)$ players randomize, or all players who randomize use the same mixed strategy. To show this result we employ tools from the literature on Stein's Method.
Congestion Control Protocol for Wireless Sensor Networks Handling Prioritized Heterogeneous Traffic
Venue: arXiv cs.NI 2008
Year: 2008

Heterogeneous applications could be assimilated within the same wireless sensor network with the aid of modern motes that have multiple sensor boards on a single radio board. Different types of data generated from such types of motes might have different transmission characteristics in terms of priority, transmission rate, required bandwidth, tolerable packet loss, delay demands etc. Considering a sensor network consisting of such multi-purpose nodes, in this paper we propose Prioritized Heterogeneous Traffic-oriented Congestion Control Protocol (PHTCCP) which ensures efficient rate control for prioritized heterogeneous traffic. Our protocol uses intra-queue and inter-queue priorities for ensuring feasible transmission rates of heterogeneous data. It also guarantees efficient link utilization by using dynamic transmission rate adjustment. Detailed analysis and simulation results are presented along with the description of our protocol to demonstrate its effectiveness in handling prioritized heterogeneous traffic in wireless sensor networks.
A New Trend in Optimization on Multi Overcomplete Dictionary toward Inpainting
Venue: arXiv cs.MM 2008
Year: 2008

Recently, great attention was intended toward overcomplete dictionaries and the sparse representations they can provide. In a wide variety of signal processing problems, sparsity serves a crucial property leading to high performance. Inpainting, the process of reconstructing lost or deteriorated parts of images or videos, is an interesting application which can be handled by suitably decomposition of an image through combination of overcomplete dictionaries. This paper addresses a novel technique of such a decomposition and investigate that through inpainting of images. Simulations are presented to demonstrate the validation of our approach.
Probabilistic SVM/GMM Classifier for Speaker-Independent Vowel Recognition in Continues Speech
Venue: arXiv cs.MM 2008
Year: 2008

In this paper, we discuss the issues in automatic recognition of vowels in Persian language. The present work focuses on new statistical method of recognition of vowels as a basic unit of syllables. First we describe a vowel detection system then briefly discuss how the detected vowels can feed to recognition unit. According to pattern recognition, Support Vector Machines (SVM) as a discriminative classifier and Gaussian mixture model (GMM) as a generative model classifier are two most popular techniques. Current state-ofthe- art systems try to combine them together for achieving more power of classification and improving the performance of the recognition systems. The main idea of the study is to combine probabilistic SVM and traditional GMM pattern classification with some characteristic of speech like band-pass energy to achieve better classification rate. This idea has been analytically formulated and tested on a FarsDat based vowel recognition system. The results show inconceivable increases in recognition accuracy. The tests have been carried out by various proposed vowel recognition algorithms and the results have been compared.
On the statistical physics of directed polymers in a random medium and their relation to tree codes
Venue: arXiv cs.IT 2008
Year: 2008

Using well-known results from statistical physics, concerning the almost-sure behavior of the free energy of directed polymers in a random medium, we prove that random tree codes achieve the distortion-rate function almost surely under a certain symmetry condition.