OpenRaiser/Intern-Atlas huggingface dataset:
Sorting by Transpositions is Difficult
Venue: arXiv cs.DS 2010
Year: 2010

In comparative genomics, a transposition is an operation that exchanges two consecutive sequences of genes in a genome. The transposition distance, that is, the minimum number of transpositions needed to transform a genome into another, is, according to numerous studies, a relevant evolutionary distance. The problem of computing this distance when genomes are represented by permutations, called the Sorting by Transpositions problem, has been introduced by Bafna and Pevzner in 1995. It has naturally been the focus of a number of studies, but the computational complexity of this problem has remained undetermined for 15 years. In this paper, we answer this long-standing open question by proving that the Sorting by Transpositions problem is NP-hard. As a corollary of our result, we also prove that the following problem is NP-hard: given a permutation pi, is it possible to sort pi using db(pi)/3 permutations, where db(pi) is the number of breakpoints of pi?
Adversarial Satisfiability Problem
Venue: arXiv cs.CC 2010
Year: 2010

We study the adversarial satisfiability problem, where the adversary can choose whether variables are negated in clauses or not in order to make the resulting formula unsatisfiable. This is one case of a general class of adversarial optimization problems that often arise in practice and are algorithmically much harder than the standard optimization problems. We use the cavity method to compute large deviations of the entropy in the random satisfiability problem with respect to the negation-configurations. We conclude that in the thermodynamic limit the best strategy the adversary can adopt is extremely close to simply balancing the number of times every variable is and is not negated. We also conduct a numerical study of the problem, and find that there are very strong pre-asymptotic effects that are due to the fact that for small sizes exponential and factorial growth is hardly distinguishable.
Transformation of Wiktionary entry structure into tables and relations in a relational database schema
Venue: arXiv cs.IR 2010
Year: 2010

This paper addresses the question of automatic data extraction from the Wiktionary, which is a multilingual and multifunctional dictionary. Wiktionary is a collaborative project working on the same principles as the Wikipedia. The Wiktionary entry is a plain text from the text processing point of view. Wiktionary guidelines prescribe the entry layout and rules, which should be followed by editors of the dictionary. The presence of the structure of a Wiktionary article and formatting rules allows transforming the Wiktionary entry structure into tables and relations in a relational database schema, which is a part of a machine-readable dictionary (MRD). The paper describes how the flat text of the Wiktionary entry was extracted, converted, and stored in the specially designed relational database. The MRD contains the definitions, semantic relations, and translations extracted from the English and Russian Wiktionaries. The parser software is released under the open source license agreement (GPL), to facilitate its dissemination, modification and upgrades, to draw researchers and programmers into parsing other Wiktionaries, not only Russian and English.
An Agent-Based Intrusion Detection System for Local Area Networks
Venue: arXiv cs.CR 2010
Year: 2010

Since it is impossible to predict and identify all the vulnerabilities of a network beforehand, and penetration into a system by malicious intruders cannot always be prevented, intrusion detection systems (IDSs) are essential entities to ensure the security of a networked system. To be effective in carrying out their functions, the IDSs need to be accurate, adaptive, and extensible. Given these stringent requirements and the high level of vulnerabilities of the current days' networks, the design of an IDS has become a very challenging task. Although, an extensive research has been done on intrusion detection in a distributed environment, distributed IDSs suffer from a number of drawbacks e.g., high rates of false positives, low detection efficiency etc. In this paper, the design of a distributed IDS is proposed that consists of a group of autonomous and cooperating agents. In addition to its ability to detect attacks, the system is capable of identifying and isolating compromised nodes in the network thereby introducing fault-tolerance in its operations. The experiments conducted on the system have shown that it has a high detection efficiency and low false positives compared to some of the currently existing systems.
An Algorithm for Detection of Selfish Nodes in Wireless Mesh Networks
Venue: arXiv cs.CR 2010
Year: 2010

Wireless mesh networks (WMNs) are evolving as a key technology for next-generation wireless networks showing raid progress and numerous applications. These networks have the potential to provide robust and high-throughput data delivery to wireless users. In a WMN, high speed routers equipped with advanced antennas, communicate with each other in a multi-hop fashion over wireless channels and form a broadband backhaul. However, the throughput of a WMN may be severely degraded due to presence of some selfish routers that avoid forwarding packets for other nodes even as they send their own traffic through the network. This paper presents an algorithm for detection of selfish nodes in a WMN. It uses statistical theory of inference for reliable clustering of the nodes and is based on local observations by the nodes. Simulation results show that the algorithm has a high detection rate while having a low rate of false positives.
Orbits of linear maps and regular languages
Venue: arXiv cs.FL 2010
Year: 2010

We settle the equivalence between the problem of hitting a polyhedral set by the orbit of a linear map and the intersection of a regular language and a language of permutations of binary words (the permutation filter realizability problem). The decidability of the both problems is presently unknown and the first one is a straightforward generalization of the famous Skolem problem and the nonnegativity problem in the theory of linear recurrent sequences. To show a `borderline' status of the permutation filter realizability problem with respect to computability we present some decidable and undecidable problems closely related to it.
Blackwell Approachability and Low-Regret Learning are Equivalent
Venue: arXiv cs.LG 2010
Year: 2010

We consider the celebrated Blackwell Approachability Theorem for two-player games with vector payoffs. We show that Blackwell's result is equivalent, via efficient reductions, to the existence of "no-regret" algorithms for Online Linear Optimization. Indeed, we show that any algorithm for one such problem can be efficiently converted into an algorithm for the other. We provide a useful application of this reduction: the first efficient algorithm for calibrated forecasting.
An Optimization-Based Framework for Automated Market-Making
Venue: arXiv cs.GT 2010
Year: 2010

Building on ideas from online convex optimization, we propose a general framework for the design of efficient securities markets over very large outcome spaces. The challenge here is computational. In a complete market, in which one security is offered for each outcome, the market institution can not efficiently keep track of the transaction history or calculate security prices when the outcome space is large. The natural solution is to restrict the space of securities to be much smaller than the outcome space in such a way that securities can be priced efficiently. Recent research has focused on searching for spaces of securities that can be priced efficiently by existing mechanisms designed for complete markets. While there have been some successes, much of this research has led to hardness results. In this paper, we take a drastically different approach. We start with an arbitrary space of securities with bounded payoff, and establish a framework to design markets tailored to this space. We prove that any market satisfying a set of intuitive conditions must price securities via a convex potential function and that the space of reachable prices must be precisely the convex hull of the security payoffs. We then show how the convex potential function can be defined in terms of an optimization over the convex hull of the security payoffs. The optimal solution to the optimization problem gives the security prices. Using this framework, we provide an efficient market for predicting the landing location of an object on a sphere. In addition, we show that we can relax our "no-arbitrage" condition to design a new efficient market maker for pair betting, which is known to be #P-hard to price using existing mechanisms. This relaxation also allows the market maker to charge transaction fees so that the depth of the market can be dynamically increased as the number of trades increases.
A lower bound for the tree-width of planar graphs with vital linkages
Venue: arXiv cs.DS 2010
Year: 2010

The disjoint paths problem asks, given an graph G and k + 1 pairs of terminals (s_0,t_0), ...,(s_k,t_k), whether there are k+1 pairwise disjoint paths P_0, ...,P_k, such that P_i connects s_i to t_i. Robertson and Seymour have proven that the problem can be solved in polynomial time if k is fixed. Nevertheless, the constants involved are huge, and the algorithm is far from implementable. The algorithm uses a bound on the tree-width of graphs with vital linkages, and deletion of irrelevant vertices. We give single exponential lower bounds both for the tree-width of planar graphs with vital linkages, and for the size of the grid necessary for finding irrelevant vertices.
On Reliability Function of BSC with Noisy Feedback
Venue: arXiv cs.IT 2010
Year: 2010

For information transmission a binary symmetric channel is used. There is also another noisy binary symmetric channel (feedback channel), and the transmitter observes without delay all the outputs of the forward channel via that feedback channel. The transmission of an exponential number of messages (i.e. the transmission rate is positive) is considered. The achievable decoding error exponent for such a combination of channels is investigated. It is shown that if the crossover probability of the feedback channel is less than a certain positive value, then the achievable error exponent is better than the decoding error exponent of the channel without feedback.
Introducing Business Language Driven Development
Venue: arXiv cs.SE 2010
Year: 2010

A classical problem in Software Engineering is how to certify that every system requirement is correctly implemented by source code. This problem, albeit well studied, can still be considered an open one, given the problems faced by software development organizations. Trying to solve this problem, Behavior-Driven Development (BDD) is a specification technique that automatically certifies that all functional requirements are treated properly by source code, through the connection of the textual description of these requirements to automated tests. However, in some areas, such as Enterprise Information Systems, requirements are identified by Business Process Modeling - which uses graphical notations of the underlying business processes. Therefore, the aim of this paper is to present Business Language Driven Development (BLDD), a method that aims to extend BDD, by connecting business process models directly to source code, while keeping the expressiveness of text descriptions when they are better fitted than graphical artifacts.
A New Algorithm for Inverting General Cyclic Heptadiagonal Matrices Recursively
Venue: arXiv cs.SC 2010
Year: 2010

In this paper, we describe a reliable symbolic computational algorithm for inverting general cyclic heptadiagonal matrices by using parallel computing along with recursion. The algorithm is implementable to the Computer Algebra System(CAS) such as MAPLE, Matlab and Mathematica . An example is presented for the sake of illustration.
Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
Venue: arXiv cs.DS 2010
Year: 2010

The celebrated dimension reduction lemma of Johnson and Lindenstrauss has numerous computational and other applications. Due to its application in practice, speeding up the computation of a Johnson-Lindenstrauss style dimension reduction is an important question. Recently, Dasgupta, Kumar, and Sarlos (STOC 2010) constructed such a transform that uses a sparse matrix. This is motivated by the desire to speed up the computation when applied to sparse input vectors, a scenario that comes up in applications. The sparsity of their construction was further improved by Kane and Nelson (ArXiv 2010). We improve the previous bound on the number of non-zero entries per column of Kane and Nelson from $O(1/ε\log(1/δ)\log(k/δ))$ (where the target dimension is $k$, the distortion is $1\pm ε$, and the failure probability is $δ$) to $$ O\left({1\overε} \left({\log(1/δ)\log\log\log(1/δ) \over \log\log(1/δ)}\right)^2\right). $$ We also improve the amount of randomness needed to generate the matrix. Our results are obtained by connecting the moments of an order 2 Rademacher chaos to the combinatorial properties of random Eulerian multigraphs. Estimating the chance that a random multigraph is composed of a given number of node-disjoint Eulerian components leads to a new tail bound on the chaos. Our estimates may be of independent interest, and as this part of the argument is decoupled from the analysis of the coefficients of the chaos, we believe that our methods can be useful in the analysis of other chaoses.
Efficient K-Nearest Neighbor Join Algorithms for High Dimensional Sparse Data
Venue: arXiv cs.DB 2010
Year: 2010

The K-Nearest Neighbor (KNN) join is an expensive but important operation in many data mining algorithms. Several recent applications need to perform KNN join for high dimensional sparse data. Unfortunately, all existing KNN join algorithms are designed for low dimensional data. To fulfill this void, we investigate the KNN join problem for high dimensional sparse data. In this paper, we propose three KNN join algorithms: a brute force (BF) algorithm, an inverted index-based(IIB) algorithm and an improved inverted index-based(IIIB) algorithm. Extensive experiments on both synthetic and real-world datasets were conducted to demonstrate the effectiveness of our algorithms for high dimensional sparse data.
A Distributed Clustering Algorithm for Dynamic Networks
Venue: arXiv cs.DC 2010
Year: 2010

We propose an algorithm that builds and maintains clusters over a network subject to mobility. This algorithm is fully decentralized and makes all the different clusters grow concurrently. The algorithm uses circulating tokens that collect data and move according to a random walk traversal scheme. Their task consists in (i) creating a cluster with the nodes it discovers and (ii) managing the cluster expansion; all decisions affecting the cluster are taken only by a node that owns the token. The size of each cluster is maintained higher than $m$ nodes ($m$ is a parameter of the algorithm). The obtained clustering is locally optimal in the sense that, with only a local view of each clusters, it computes the largest possible number of clusters (\emph{ie} the sizes of the clusters are as close to $m$ as possible). This algorithm is designed as a decentralized control algorithm for large scale networks and is mobility-adaptive: after a series of topological changes, the algorithm converges to a clustering. This recomputation only affects nodes in clusters in which topological changes happened, and in adjacent clusters.
The Hamiltonian Syllogistic
Venue: arXiv cs.LO 2010
Year: 2010

This paper undertakes a re-examination of Sir William Hamilton's doctrine of the quantification of the predicate. Hamilton's doctrine comprises two theses. First, the predicates of traditional syllogistic sentence-forms contain implicit existential quantifiers, so that, for example, "All p are q" is to be understood as "All p are some q". Second, these implicit quantifiers can be meaningfully dualized to yield novel sentence-forms, such as, for example, "All p are all q". Hamilton attempted to provide a deductive system for his language, along the lines of the classical syllogisms. We show, using techniques unavailable to Hamilton, that such a system does exist, though with qualifications that distinguish it from its classical counterpart.
Cyber-Physical Control over Wireless Sensor and Actuator Networks with Packet Loss
Venue: arXiv cs.NI 2010
Year: 2010

There is a growing interest in design and implementation of cyber-physical control systems over wireless sensor and actuator networks (WSANs). Thanks to the use of wireless communications and distributed architectures, these systems encompass many advantages as compared to traditional networked control systems using hard wirelines. While WSANs are enabling a new generation of control systems, they also introduce considerable challenges for quality-of-service (QoS) provisioning. In this chapter we examine some of the major QoS challenges raised by WSANs, including resource constraints, platform heterogeneity, dynamic network topology, and mixed traffic. These challenges make it difficult to fulfill the requirements of cyber-physical control in terms of reliability and real-time. The focus of this chapter is on addressing the problem of network reliability. Specifically, we analyze the behavior of wireless channels via simulations based on a realistic link-layer model. Packet loss rate (PLR) is taken as a major metric for the analysis. The results confirm the unreliability of wireless communications and the uncertainty of packet loss over WSANs. To tackle packet loss, we present a simple solution that can take advantage of existing prediction algorithms. Simulations are conducted to evaluate the performance of several classical prediction algorithms used for packet loss compensation. The results give some insights into how to deal with packet loss in cyber-physical control systems over unreliable WSANs.
An Adaptive Fault-Tolerant Communication Scheme for Body Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

A high degree of reliability for critical data transmission is required in body sensor networks (BSNs). However, BSNs are usually vulnerable to channel impairments due to body fading effect and RF interference, which may potentially cause data transmission to be unreliable. In this paper, an adaptive and flexible fault-tolerant communication scheme for BSNs, namely AFTCS, is proposed. AFTCS adopts a channel bandwidth reservation strategy to provide reliable data transmission when channel impairments occur. In order to fulfill the reliability requirements of critical sensors, fault-tolerant priority and queue are employed to adaptively adjust the channel bandwidth allocation. Simulation results show that AFTCS can alleviate the effect of channel impairments, while yielding lower packet loss rate and latency for critical sensors at runtime.
Reducing the Number of Annotations in a Verification-oriented Imperative Language
Venue: arXiv cs.PL 2010
Year: 2010

Automated software verification is a very active field of research which has made enormous progress both in theoretical and practical aspects. Recently, an important amount of research effort has been put into applying these techniques on top of mainstream programming languages. These languages typically provide powerful features such as reflection, aliasing and polymorphism which are handy for practitioners but, in contrast, make verification a real challenge. In this work we present Pest, a simple experimental, while-style, multiprocedural, imperative programming language which was conceived with verifiability as one of its main goals. This language forces developers to concurrently think about both the statements needed to implement an algorithm and the assertions required to prove its correctness. In order to aid programmers, we propose several techniques to reduce the number and complexity of annotations required to successfully verify their programs. In particular, we show that high-level iteration constructs may alleviate the need for providing complex loop annotations.
Non-Existence of Linear Universal Drift Functions
Venue: arXiv cs.NE 2010
Year: 2010

Drift analysis has become a powerful tool to prove bounds on the runtime of randomized search heuristics. It allows, for example, fairly simple proofs for the classical problem how the (1+1) Evolutionary Algorithm (EA) optimizes an arbitrary pseudo-Boolean linear function. The key idea of drift analysis is to measure the progress via another pseudo-Boolean function (called drift function) and use deeper results from probability theory to derive from this a good bound for the runtime of the EA. Surprisingly, all these results manage to use the same drift function for all linear objective functions. In this work, we show that such universal drift functions only exist if the mutation probability is close to the standard value of $1/n$.
Overlay Protection Against Link Failures Using Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

This paper introduces a network coding-based protection scheme against single and multiple link failures. The proposed strategy ensures that in a connection, each node receives two copies of the same data unit: one copy on the working circuit, and a second copy that can be extracted from linear combinations of data units transmitted on a shared protection path. This guarantees instantaneous recovery of data units upon the failure of a working circuit. The strategy can be implemented at an overlay layer, which makes its deployment simple and scalable. While the proposed strategy is similar in spirit to the work of Kamal '07 & '10, there are significant differences. In particular, it provides protection against multiple link failures. The new scheme is simpler, less expensive, and does not require the synchronization required by the original scheme. The sharing of the protection circuit by a number of connections is the key to the reduction of the cost of protection. The paper also conducts a comparison of the cost of the proposed scheme to the 1+1 and shared backup path protection (SBPP) strategies, and establishes the benefits of our strategy.
Fast GPGPU Data Rearrangement Kernels using CUDA
Venue: arXiv cs.DC 2010
Year: 2010

Many high performance-computing algorithms are bandwidth limited, hence the need for optimal data rearrangement kernels as well as their easy integration into the rest of the application. In this work, we have built a CUDA library of fast kernels for a set of data rearrangement operations. In particular, we have built generic kernels for rearranging m dimensional data into n dimensions, including Permute, Reorder, Interlace/De-interlace, etc. We have also built kernels for generic Stencil computations on a two-dimensional data using templates and functors that allow application developers to rapidly build customized high performance kernels. All the kernels built achieve or surpass best-known performance in terms of bandwidth utilization.