OpenRaiser/Intern-Atlas huggingface dataset:
Joint Range of Rényi Entropies
Venue: arXiv cs.IT 2009
Year: 2009

The exact range of the joined values of several Rényi entropies is determined. The method is based on topology with special emphasis on the orientation of the objects studied. Like in the case when only two orders of Rényi entropies are studied one can parametrize upper and lower bounds but an explicit formula for a tight upper or lower bound cannot be given.
Disproof of the Neighborhood Conjecture with Implications to SAT
Venue: arXiv cs.GT 2009
Year: 2009

We study a Maker/Breaker game described by Beck. As a result we disprove a conjecture of Beck on positional games, establish a connection between this game and SAT and construct an unsatisfiable k-CNF formula with few occurrences per variable, thereby improving a previous result by Hoory and Szeider and showing that the bound obtained from the Lovasz Local Lemma is tight up to a constant factor. The Maker/Breaker game we study is as follows. Maker and Breaker take turns in choosing vertices from a given n-uniform hypergraph F, with Maker going first. Maker's goal is to completely occupy a hyperedge and Breaker tries to avoid this. Beck conjectures that if the maximum neighborhood size of F is at most 2^(n-1) then Breaker has a winning strategy. We disprove this conjecture by establishing an n-uniform hypergraph with maximum neighborhood size 3*2^(n - 3) where Maker has a winning strategy. Moreover, we show how to construct an n-uniform hypergraph with maximum degree (2^(n-1))/n where maker has a winning strategy. Finally, we establish a connection between SAT and the Maker/Breaker game we study. We can use this connection to derive new results in SAT. Kratochvil, Savicky and Tuza showed that for every k >= 3 there is an integer f(k) such that every (k,f(k))-formula is satisfiable, but (k,f(k) + 1)-SAT is already NP-complete (it is not known whether f(k) is computable). Kratochvil, Savicky and Tuza also gave the best known lower bound f(k) = Omega(2^k/k), which is a consequence of the Lovasz Local Lemma. We prove that, in fact, f(k) = Theta(2^k/k), improving upon the best known upper bound O((log k) * 2^k/k) by Hoory and Szeider.
PTAS for k-tour cover problem on the plane for moderately large values of k
Venue: arXiv cs.DS 2009
Year: 2009

Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The k-tour cover problem is known to be NP-hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, i.e., k=O(log n / log log n). We significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2^{log^δn}, where δ= δ(ε). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with O((k/ε)^O(1)) points.
Detection, Understanding, and Prevention of Traceroute Measurement Artifacts
Venue: arXiv cs.NI 2009
Year: 2009

Traceroute is widely used: from the diagnosis of network problems to the assemblage of internet maps. Unfortu- nately, there are a number of problems with traceroute methodology, which lead to the inference of erroneous routes. This paper studies particular structures arising in nearly all traceroute measurements. We characterize them as "loops", "cycles", and "diamonds". We iden- tify load balancing as a possible cause for the appear- ance of false loops, cycles and diamonds, i.e., artifacts that do not represent the internet topology. We pro- vide a new publicly-available traceroute, called Paris traceroute, which, by controlling the packet header con- tents, provides a truer picture of the actual routes that packets follow. We performed measurements, from the perspective of a single source tracing towards multiple destinations, and Paris traceroute allowed us to show that many of the particular structures we observe are indeed traceroute measurement artifacts.
Non Homogeneous Poisson Process Model based Optimal Modular Software Testing using Fault Tolerance
Venue: arXiv cs.SE 2009
Year: 2009

In software development process we come across various modules. Which raise the idea of priority of the different modules of a software so that important modules are tested on preference. This approach is desirable because it is not possible to test each module regressively due to time and cost constraints. This paper discuss on some parameters, required to prioritize several modules of a software and provides measure of optimal time and cost for testing based on non homogeneous Poisson process.
Decomposition width - a new width parameter for matroids
Venue: arXiv cs.DM 2009
Year: 2009

We introduce a new width parameter for matroids called decomposition width and prove that every matroid property expressible in the monadic second order logic can be computed in linear time for matroids with bounded decomposition width if their decomposition is given. Since decompositions of small width for our new notion can be computed in polynomial time for matroids of bounded branch-width represented over finite fields, our results include recent algorithmic results of Hlineny [J. Combin. Theory Ser. B 96 (2006), 325-351] in this area and extend his results to matroids not necessarily representable over finite fields.
Inter-Session Network Coding with Strategic Users: A Game-Theoretic Analysis of Network Coding
Venue: arXiv cs.IT 2009
Year: 2009

A common assumption in the existing network coding literature is that the users are cooperative and non-selfish. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network using game theory. We assume selfish users acting strategically to maximize their own utility, leading to a resource allocation game among users. In particular, we study the well-known butterfly network topology where a bottleneck link is shared by several network coding and routing flows. We prove the existence of a Nash equilibrium for a wide range of utility functions. We show that the number of Nash equilibria can be large (even infinite) for certain choices of system parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding where the Nash equilibrium is always unique. We then characterize the worst-case efficiency bounds, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a novel discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA. However, regardless of the discriminatory pricing scheme being used, the PoA is still worse than for the case when network coding is not applied. This implies that, although inter-session network coding can improve performance compared to ordinary routing, it is significantly more sensitive to users' strategic behaviour. For example, in a butterfly network where the side links have zero cost, the efficiency can be as low as 25%. If the side links have non-zero cost, then the efficiency can further reduce to only 20%. These results generalize the well-known result of guaranteed 67% worst-case efficiency for traditional packet forwarding networks.
Counting Paths and Packings in Halves
Venue: arXiv cs.DS 2009
Year: 2009

It is shown that one can count $k$-edge paths in an $n$-vertex graph and $m$-set $k$-packings on an $n$-element universe, respectively, in time ${n \choose k/2}$ and ${n \choose mk/2}$, up to a factor polynomial in $n$, $k$, and $m$; in polynomial space, the bounds hold if multiplied by $3^{k/2}$ or $5^{mk/2}$, respectively. These are implications of a more general result: given two set families on an $n$-element universe, one can count the disjoint pairs of sets in the Cartesian product of the two families with $\nO(n \ell)$ basic operations, where $\ell$ is the number of members in the two families and their subsets.
On the distributed evaluation of recursive queries over graphs
Venue: arXiv cs.LO 2009
Year: 2009

Logical formalisms such as first-order logic (FO) and fixpoint logic (FP) are well suited to express in a declarative manner fundamental graph functionalities required in distributed systems. We show that these logics constitute good abstractions for programming distributed systems as a whole, since they can be evaluated in a fully distributed manner with reasonable complexity upper-bounds. We first prove that FO and FP can be evaluated with a polynomial number of messages of logarithmic size. We then show that the (global) logical formulas can be translated into rule programs describing the local behavior of the nodes of the distributed system, which compute equivalent results. Finally, we introduce local fragments of these logics, which preserve as much as possible the locality of their distributed computation, while offering a rich expressive power for networking functionalities. We prove that they admit tighter upper-bounds with bounded number of messages of bounded size. Finally, we show that the semantics and the complexity of the local fragments are preserved over locally consistent networks as well as anonymous networks, thus showing the robustness of the proposed local logical formalisms.
Fast Algorithms for Mining Interesting Frequent Itemsets without Minimum Support
Venue: arXiv cs.DB 2009
Year: 2009

Real world datasets are sparse, dirty and contain hundreds of items. In such situations, discovering interesting rules (results) using traditional frequent itemset mining approach by specifying a user defined input support threshold is not appropriate. Since without any domain knowledge, setting support threshold small or large can output nothing or a large number of redundant uninteresting results. Recently a novel approach of mining only N-most/Top-K interesting frequent itemsets has been proposed, which discovers the top N interesting results without specifying any user defined support threshold. However, mining interesting frequent itemsets without minimum support threshold are more costly in terms of itemset search space exploration and processing cost. Thereby, the efficiency of their mining highly depends upon three main factors (1) Database representation approach used for itemset frequency counting, (2) Projection of relevant transactions to lower level nodes of search space and (3) Algorithm implementation technique. Therefore, to improve the efficiency of mining process, in this paper we present two novel algorithms called (N-MostMiner and Top-K-Miner) using the bit-vector representation approach which is very efficient in terms of itemset frequency counting and transactions projection. In addition to this, several efficient implementation techniques of N-MostMiner and Top-K-Miner are also present which we experienced in our implementation. Our experimental results on benchmark datasets suggest that the NMostMiner and Top-K-Miner are very efficient in terms of processing time as compared to current best algorithms BOMO and TFP.
Identity Based Strong Designated Verifier Parallel Multi-Proxy Signature Scheme
Venue: arXiv cs.CR 2009
Year: 2009

This paper presents a new identity based strong designated verifier parallel multi-proxy signature scheme. Multi-Proxy signatures allow the original signer to delegate his signing power to a group of proxy signers. In our scheme, the designated verifier can only validate proxy signatures created by a group of proxy signer.
Comment to "Coverage by Randomly Deployed Wireless Sensor Networks"
Venue: arXiv cs.IT 2009
Year: 2009

It is a correction paper on "P.J. Wan and C.W. Yi, "Coverage by Randomly Deployed Wireless Sensor Networks", IEEE Transaction On Information Theory, vol.52, No.6, June 2006." In the above paper, Lemma (4), on page 2659 play the key role for deriving the main results in the paper. The statement as well as the proof of Lemma (4), page $2659,$ is not correct. We have given the correct version of Lemma. This change in Lemma leads a drastic change in all the result derived in the above paper.
On the Complexity of Searching in Trees: Average-case Minimization
Venue: arXiv cs.DS 2009
Year: 2009

We focus on the average-case analysis: A function w : V -> Z+ is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper, very little was known about this natural question and the complexity of the problem had remained so far an open question. We close this question and prove that the above tree search problem is NP-complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 the problem can be shown to be polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP-complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O(|V| log|V|) time for trees with degree at most 2 (paths). We match the above complexity results with a tight algorithmic analysis. We first show that a natural greedy algorithm attains a 2-approximation. Furthermore, for the bounded degree instances, we show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O(Δ(T) (log |V| + log w(T))) queries in the worst case, where w(T) is the sum of the likelihoods of the nodes of T and Δ(T) is the maximum degree of T. We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree.
Les technologies de l'information et de la communication au niveau mondial et en Roumanie dans les dernieres annees
Venue: arXiv cs.OH 2009
Year: 2009

The level of development of the electronic communication market and of the information technology, the indicators regarding the penetration of Internet and the level of penetration of the connections in wide band, the integration degree of the Tic application in the business area are crucial for the development of an informational society and for the creation of a society based on knowledge. Though the levels are still reduced their positive evolution reflects the attenuation of the gaps by Romania, comparatively to other countries.
The use of invariant moments in hand-written character recognition
Venue: arXiv cs.NE 2009
Year: 2009

The goal of this paper is to present the implementation of a Radial Basis Function neural network with built-in knowledge to recognize hand-written characters. The neural network includes in its architecture gates controlled by an attraction/repulsion system of coefficients. These coefficients are derived from a preprocessing stage which groups the characters according to their ascendant, central, or descendent components. The neural network is trained using data from invariant moment functions. Results are compared with those obtained using a K nearest neighbor method on the same moment data.
Better Global Polynomial Approximation for Image Rectification
Venue: arXiv cs.CV 2009
Year: 2009

When using images to locate objects, there is the problem of correcting for distortion and misalignment in the images. An elegant way of solving this problem is to generate an error correcting function that maps points in an image to their corrected locations. We generate such a function by fitting a polynomial to a set of sample points. The objective is to identify a polynomial that passes "sufficiently close" to these points with "good" approximation of intermediate points. In the past, it has been difficult to achieve good global polynomial approximation using only sample points. We report on the development of a global polynomial approximation algorithm for solving this problem. Key Words: Polynomial approximation, interpolation, image rectification.
Denial of service attack in the Internet: agent-based intrusion detection and reaction
Venue: arXiv cs.NI 2009
Year: 2009

This paper deals with denial of service attack. Overview of the existing attacks and methods is proposed. Classification scheme is presented for a different denial of service attacks. There is considered agent-based intrusion detection systems architecture. Considered main components and working principles for a systems of such kind.
Opportunistic Spatial Orthogonalization and Its Application in Fading Cognitive Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

Opportunistic Spatial Orthogonalization (OSO) is a cognitive radio scheme that allows the existence of secondary users and hence increases the system throughput, even if the primary user occupies all the frequency bands all the time. Notably, this throughput advantage is obtained without sacrificing the performance of the primary user, if the interference margin is carefully chosen. The key idea is to exploit the spatial dimensions to orthogonalize users and hence minimize interference. However, unlike the time and frequency dimensions, there is no universal basis for the set of all multi-dimensional spatial channels, which motivated the development of OSO. On one hand, OSO can be viewed as a multi-user diversity scheme that exploits the channel randomness and independence. On the other hand, OSO can be interpreted as an opportunistic interference alignment scheme, where the interference from multiple secondary users is opportunistically aligned at the direction that is orthogonal to the primary user's signal space. In the case of multiple-input multiple-output (MIMO) channels, the OSO scheme can be interpreted as "riding the peaks" over the eigen-channels, and ill-conditioned MIMO channel, which is traditionally viewed as detrimental, is shown to be beneficial with respect to the sum throughput. Throughput advantages are thoroughly studied, both analytically and numerically.
Temporal data mining for root-cause analysis of machine faults in automotive assembly lines
Venue: arXiv cs.LG 2009
Year: 2009

Engine assembly is a complex and heavily automated distributed-control process, with large amounts of faults data logged everyday. We describe an application of temporal data mining for analyzing fault logs in an engine assembly plant. Frequent episode discovery framework is a model-free method that can be used to deduce (temporal) correlations among events from the logs in an efficient manner. In addition to being theoretically elegant and computationally efficient, frequent episodes are also easy to interpret in the form actionable recommendations. Incorporation of domain-specific information is critical to successful application of the method for analyzing fault logs in the manufacturing domain. We show how domain-specific knowledge can be incorporated using heuristic rules that act as pre-filters and post-filters to frequent episode discovery. The system described here is currently being used in one of the engine assembly plants of General Motors and is planned for adaptation in other plants. To the best of our knowledge, this paper presents the first real, large-scale application of temporal data mining in the manufacturing domain. We believe that the ideas presented in this paper can help practitioners engineer tools for analysis in other similar or related application domains as well.
Quality Classifiers for Open Source Software Repositories
Venue: arXiv cs.SE 2009
Year: 2009

Open Source Software (OSS) often relies on large repositories, like SourceForge, for initial incubation. The OSS repositories offer a large variety of meta-data providing interesting information about projects and their success. In this paper we propose a data mining approach for training classifiers on the OSS meta-data provided by such data repositories. The classifiers learn to predict the successful continuation of an OSS project. The `successfulness' of projects is defined in terms of the classifier confidence with which it predicts that they could be ported in popular OSS projects (such as FreeBSD, Gentoo Portage).
Models and theories of lambda calculus
Venue: arXiv cs.LO 2009
Year: 2009

In this paper we briefly summarize the contents of Manzonetto's PhD thesis which concerns denotational semantics and equational/order theories of the pure untyped lambda-calculus. The main research achievements include: (i) a general construction of lambda-models from reflexive objects in (possibly non-well-pointed) categories; (ii) a Stone-style representation theorem for combinatory algebras; (iii) a proof that no effective lambda-model can have lambda-beta or lambda-beta-eta as its equational theory (this can be seen as a partial answer to an open problem introduced by Honsell-Ronchi Della Rocca in 1984).
FaceBots: Steps Towards Enhanced Long-Term Human-Robot Interaction by Utilizing and Publishing Online Social Information
Venue: arXiv cs.RO 2009
Year: 2009

Our project aims at supporting the creation of sustainable and meaningful longer-term human-robot relationships through the creation of embodied robots with face recognition and natural language dialogue capabilities, which exploit and publish social information available on the web (Facebook). Our main underlying experimental hypothesis is that such relationships can be significantly enhanced if the human and the robot are gradually creating a pool of shared episodic memories that they can co-refer to (shared memories), and if they are both embedded in a social web of other humans and robots they both know and encounter (shared friends). In this paper, we are presenting such a robot, which as we will see achieves two significant novelties.
Hiding Information in Retransmissions
Venue: arXiv cs.CR 2009
Year: 2009

The paper presents a new steganographic method called RSTEG (Retransmission Steganography), which is intended for a broad class of protocols that utilises retransmission mechanisms. The main innovation of RSTEG is to not acknowledge a successfully received packet in order to intentionally invoke retransmission. The retransmitted packet carries a steganogram instead of user data in the payload field. RSTEG is presented in the broad context of network steganography, and the utilisation of RSTEG for TCP (Transport Control Protocol) retransmission mechanisms is described in detail. Simulation results are also presented with the main aim to measure and compare the steganographic bandwidth of the proposed method for different TCP retransmission mechanisms as well as to determine the influence of RSTEG on the network retransmissions level.
WinBioinfTools: Bioinformatics Tools for Windows High Performance Computing Server 2008
Venue: arXiv cs.MS 2009
Year: 2009

Open source bioinformatics tools running under MS Windows are rare to find, and those running under Windows HPC cluster are almost non-existing. This is despite the fact that the Windows is the most popular operating system used among life scientists. Therefore, we introduce in this initiative WinBioinfTools, a toolkit containing a number of bioinformatics tools running under Windows High Performance Computing Server 2008. It is an open source code package, where users and developers can share and add to. We currently start with three programs from the area of sequence analysis: 1) CoCoNUT for pairwise genome comparison, 2) parallel BLAST for biological database search, and 3) parallel global pairwise sequence alignment. In this report, we focus on technical aspects concerning how some components of these tools were ported from Linux/Unix environment to run under Windows. We also show the advantages of using the Windows HPC Cluster 2008. We demonstrate by experiments the performance gain achieved when using a computer cluster against a single machine. Furthermore, we show the results of comparing the performance of WinBioinfTools on the Windows and Linux Cluster.