OpenRaiser/Intern-Atlas huggingface dataset:
Complexity Classifications for Propositional Abduction in Post's Framework
Venue: arXiv cs.CC 2010
Year: 2010

In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining the world's behavior it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be \SigPtwo-complete in general. We focus on formulae in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants we obtain a complexity classification for all possible sets of Boolean functions. In this way, we identify easier cases, namely \NP-complete, \coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
A Virtual Queue Approach for Online Estimation of Loss Probability Based on MVA Theory
Venue: arXiv cs.NI 2010
Year: 2010

In network quality of service provisioning, premium services generally require to keep a very small loss probability, which is infeasible to measure directly. The proposed virtual queue scheme estimates the small packet loss probability of a real queueing system by measuring queue statistics in a set of separate virtual queues. A novel scaling property between the real queue and the virtual queues is deduced on the basis of the maximum variance asymptotic (MVA) theory. The new scheme retains the high accuracy and wide applicability of the MVA method for aggregated traffic while avoiding the high computational complexity in a direct application of the original MVA analysis in real time. This makes it suitable for online measurement applications such as network performance monitoring and measurement-based admission control.
Artificial Immune Systems (2010)
Venue: arXiv cs.AI 2010
Year: 2010

The human immune system has numerous properties that make it ripe for exploitation in the computational domain, such as robustness and fault tolerance, and many different algorithms, collectively termed Artificial Immune Systems (AIS), have been inspired by it. Two generations of AIS are currently in use, with the first generation relying on simplified immune models and the second generation utilising interdisciplinary collaboration to develop a deeper understanding of the immune system and hence produce more complex models. Both generations of algorithms have been successfully applied to a variety of problems, including anomaly detection, pattern recognition, optimisation and robotics. In this chapter an overview of AIS is presented, its evolution is discussed, and it is shown that the diversification of the field is linked to the diversity of the immune system itself, leading to a number of algorithms as opposed to one archetypal system. Two case studies are also presented to help provide insight into the mechanisms of AIS; these are the idiotypic network approach and the Dendritic Cell Algorithm.
Large scale link based latent Dirichlet allocation for web document classification
Venue: arXiv cs.IR 2010
Year: 2010

In this paper we demonstrate the applicability of latent Dirichlet allocation (LDA) for classifying large Web document collections. One of our main results is a novel influence model that gives a fully generative model of the document content taking linkage into account. In our setup, topics propagate along links in such a way that linked documents directly influence the words in the linking document. As another main contribution we develop LDA specific boosting of Gibbs samplers resulting in a significant speedup in our experiments. The inferred LDA model can be applied for classification as dimensionality reduction similarly to latent semantic indexing. In addition, the model yields link weights that can be applied in algorithms to process the Web graph; as an example we deploy LDA link weights in stacked graphical learning. By using Weka's BayesNet classifier, in terms of the AUC of classification, we achieve 4% improvement over plain LDA with BayesNet and 18% over tf.idf with SVM. Our Gibbs sampling strategies yield about 5-10 times speedup with less than 1% decrease in accuracy in terms of likelihood and AUC of classification.
Link creation and profile alignment in the aNobii social network
Venue: arXiv cs.CY 2010
Year: 2010

The present work investigates the structural and dynamical properties of aNobii\footnote{http://www.anobii.com/}, a social bookmarking system designed for readers and book lovers. Users of aNobii provide information about their library, reading interests and geographical location, and they can establish typed social links to other users. Here, we perform an in-depth analysis of the system's social network and its interplay with users' profiles. We describe the relation of geographic and interest-based factors to social linking. Furthermore, we perform a longitudinal analysis to investigate the interplay of profile similarity and link creation in the social network, with a focus on triangle closure. We report a reciprocal causal connection: profile similarity of users drives the subsequent closure in the social network and, reciprocally, closure in the social network induces subsequent profile alignment. Access to the dynamics of the social network also allows us to measure quantitative indicators of preferential linking.
GraphLab: A New Framework for Parallel Machine Learning
Venue: arXiv cs.LG 2010
Year: 2010

Designing and implementing efficient, provably correct parallel machine learning (ML) algorithms is challenging. Existing high-level parallel abstractions like MapReduce are insufficiently expressive while low-level tools like MPI and Pthreads leave ML experts repeatedly solving the same design challenges. By targeting common patterns in ML, we developed GraphLab, which improves upon abstractions like MapReduce by compactly expressing asynchronous iterative algorithms with sparse computational dependencies while ensuring data consistency and achieving a high degree of parallel performance. We demonstrate the expressiveness of the GraphLab framework by designing and implementing parallel versions of belief propagation, Gibbs sampling, Co-EM, Lasso and Compressed Sensing. We show that using GraphLab we can achieve excellent parallel performance on large scale real-world problems.
Performance evaluation for ML sequence detection in ISI channels with Gauss Markov Noise
Venue: arXiv cs.IT 2010
Year: 2010

Inter-symbol interference (ISI) channels with data dependent Gauss Markov noise have been used to model read channels in magnetic recording and other data storage systems. The Viterbi algorithm can be adapted for performing maximum likelihood sequence detection in such channels. However, the problem of finding an analytical upper bound on the bit error rate of the Viterbi detector in this case has not been fully investigated. Current techniques rely on an exhaustive enumeration of short error events and determine the BER using a union bound. In this work, we consider a subset of the class of ISI channels with data dependent Gauss-Markov noise. We derive an upper bound on the pairwise error probability (PEP) between the transmitted bit sequence and the decoded bit sequence that can be expressed as a product of functions depending on current and previous states in the (incorrect) decoded sequence and the (correct) transmitted sequence. In general, the PEP is asymmetric. The average BER over all possible bit sequences is then determined using a pairwise state diagram. Simulations results which corroborate the analysis of upper bound, demonstrate that analytic bound on BER is tight in high SNR regime. In the high SNR regime, our proposed upper bound obviates the need for computationally expensive simulation.
Algorithmic Solutions for Several Offline Constrained Resource Processing and Data Transfer Multicriteria Optimization Problems
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we present novel algorithmic solutions for several resource processing and data transfer multicriteria optimization problems. The results of most of the presented techniques are strategies which solve the considered problems (almost) optimally. Thus, the developed algorithms construct intelligent strategies which can be implemented by agents in specific situations. All the described solutions make use of the properties of the considered problems and, thus, they are not applicable to a very general class of problems. However, by considering the specific details of each problem, we were able to obtain very efficient results.
Optimal Bandwidth and Power Allocation for Sum Ergodic Capacity under Fading Channels in Cognitive Radio Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies optimal bandwidth and power allocation in a cognitive radio network where multiple secondary users (SUs) share the licensed spectrum of a primary user (PU) under fading channels using the frequency division multiple access scheme. The sum ergodic capacity of all the SUs is taken as the performance metric of the network. Besides all combinations of the peak/average transmit power constraints at the SUs and the peak/average interference power constraint imposed by the PU, total bandwidth constraint of the licensed spectrum is also taken into account. Optimal bandwidth allocation is derived in closed-form for any given power allocation. The structures of optimal power allocations are also derived under all possible combinations of the aforementioned power constraints. These structures indicate the possible numbers of users that transmit at nonzero power but below their corresponding peak powers, and show that other users do not transmit or transmit at their corresponding peak power. Based on these structures, efficient algorithms are developed for finding the optimal power allocations.
Approximate Testing Equivalence Based on Time, Probability, and Observed Behavior
Venue: arXiv cs.LO 2010
Year: 2010

Several application domains require formal but flexible approaches to the comparison problem. Different process models that cannot be related by behavioral equivalences should be compared via a quantitative notion of similarity, which is usually achieved through approximation of some equivalence. While in the literature the classical equivalence subject to approximation is bisimulation, in this paper we propose a novel approach based on testing equivalence. As a step towards flexibility and usability, we study different relaxations taking into account orthogonal aspects of the process observations: execution time, event probability, and observed behavior. In this unifying framework, both interpretation of the measures and decidability of the verification algorithms are discussed.
Optimal Time-Abstract Schedulers for CTMDPs and Markov Games
Venue: arXiv cs.FL 2010
Year: 2010

We study time-bounded reachability in continuous-time Markov decision processes for time-abstract scheduler classes. Such reachability problems play a paramount role in dependability analysis and the modelling of manufacturing and queueing systems. Consequently, their analysis has been studied intensively, and techniques for the approximation of optimal control are well understood. From a mathematical point of view, however, the question of approximation is secondary compared to the fundamental question whether or not optimal control exists. We demonstrate the existence of optimal schedulers for the time-abstract scheduler classes for all CTMDPs. Our proof is constructive: We show how to compute optimal time-abstract strategies with finite memory. It turns out that these optimal schedulers have an amazingly simple structure - they converge to an easy-to-compute memoryless scheduling policy after a finite number of steps. Finally, we show that our argument can easily be lifted to Markov games: We show that both players have a likewise simple optimal strategy in these more general structures.
Design of Simple and Efficient Revocation List Distribution in Urban areas for VANET's
Venue: arXiv cs.NI 2010
Year: 2010

Vehicular Ad hoc Networks is one of the most challenging research area in the field of Mobile Ad Hoc Networks, in this research we propose a flexible, simple, and scalable design for revocation list distribution in VANET, which will reduce channel overhead and eliminate the use of CRL. Also it will increase the security of the network and helps in identifying the adversary vehicles.
Design specifications of the Human Robotic interface for the biomimetic underwater robot "yellow submarine project"
Venue: arXiv cs.MA 2010
Year: 2010

This paper describes the design of a web based multi agent design for a collision avoidance auto navigation biomimetic submarine for submarine hydroelectricity. The paper describes the nature of the map - topology interface for river bodies and the design of interactive agents for the control of the robotic submarine. The agents are migratory on the web and are designed in XML/html interface with both interactive capabilities and visibility on a map. The paper describes mathematically the user interface and the map definition languages used for the multi agent description
Control-theoretic Approach to Communication with Feedback: Fundamental Limits and Code Design
Venue: arXiv cs.IT 2010
Year: 2010

Feedback communication is studied from a control-theoretic perspective, mapping the communication problem to a control problem in which the control signal is received through the same noisy channel as in the communication problem, and the (nonlinear and time-varying) dynamics of the system determine a subclass of encoders available at the transmitter. The MMSE capacity is defined to be the supremum exponential decay rate of the mean square decoding error. This is upper bounded by the information-theoretic feedback capacity, which is the supremum of the achievable rates. A sufficient condition is provided under which the upper bound holds with equality. For the special class of stationary Gaussian channels, a simple application of Bode's integral formula shows that the feedback capacity, recently characterized by Kim, is equal to the maximum instability that can be tolerated by the controller under a given power constraint. Finally, the control mapping is generalized to the N-sender AWGN multiple access channel. It is shown that Kramer's code for this channel, which is known to be sum rate optimal in the class of generalized linear feedback codes, can be obtained by solving a linear quadratic Gaussian control problem.
A Multi-Core Processor Platform for Open Embedded Systems
Venue: arXiv cs.DC 2010
Year: 2010

Recent proliferation of embedded systems has generated a bold new paradigm, known as open embedded systems. While traditional embedded systems provide only closed base applications (natively-installed software) to users, open embedded systems allow the users to freely execute open applications (additionally-installed software) in order to meet various user requirements, such as user personalization and device coordination. Key to the success of platforms required for open embedded systems is the achievement of both the scalable extension of base applications and the secure execution of open applications. Most existing platforms, however, have focused on either scalable or secure execution, limiting their applicability. This dissertation presents a new secure platform using multi-core processors, which achieves both scalability and security. Four techniques feature the new platform: (1) seamless communication, by which legacy applications designed for a single processor make it possible to be executed on multiple processors without any software modifications; (2) secure processor partitioning with hardware support, by which Operating Systems (OSs) required for base and open applications are securely executed on separate processors; (3) asymmetric virtualization, by which many OSs over the number of processors are securely executed under secure processor partitioning; and (4) secure dynamic partitioning, by which the number of processors allocated to individual OSs makes it possible to be dynamically changed under secure processor partitioning.
A Reflective Approach to Providing Flexibility in Application Distribution
Venue: arXiv cs.DC 2010
Year: 2010

Current middleware systems suffer from drawbacks. Often one is forced to make decisions early in the design process about which classes may participate in inter-machine communication. Further, application level and middleware specific semantics cannot be separated forcing an unnatural design. The RAFDA project proposes to adress these deficiencies by creating an adaptive, reflective framework that enables the transformation of non-distributed applications into isomorphic applications whose distribution architecture is flexible. This paper describes the code transformation techniques that have been developed as part of the project. The system enables the distribution of a program according to a flexible configuration without user intervention. Proxy objects can then be substituted, permitting cross-address space communication. The distributed program can adapt to its environment by dynamically altering its distribution boundaries.
Critical Success factors for Enterprise Resource Planning implementation in Indian Retail Industry: An Exploratory study
Venue: arXiv cs.OH 2010
Year: 2010

Enterprise resource Planning (ERP) has become a key business driver in today's world. Retailers are also trying to reap in the benefits of the ERP. In most large Indian Retail Industry ERP systems have replaced nonintegrated information systems with integrated and maintainable software. Retail ERP solution integrates demand and supply effectively to help improve bottom line. The implementation of ERP systems in such firms is a difficult task. So far, ERP implementations have yielded more failures than successes. Very few implementation failures are recorded in the literature because few companies wish to publicize their implementation failure. This paper explores and validates the existing literature empirically to find out the critical success factors that lead to the success of ERP in context to Indian retail industry. The findings of the results provide valuable insights for the researchers and practitioners who are interested in implementing Enterprise Resource Planning systems in retail industry, how best they can utilize their limited resources and to pay adequate attention to those factors that are most likely to have an impact upon the implementation of the ERP system.
Approximate Robotic Mapping from sonar data by modeling Perceptions with Antonyms
Venue: arXiv cs.RO 2010
Year: 2010

This work, inspired by the idea of "Computing with Words and Perceptions" proposed by Zadeh in 2001, focuses on how to transform measurements into perceptions for the problem of map building by Autonomous Mobile Robots. We propose to model the perceptions obtained from sonar-sensors as two grid maps: one for obstacles and another for empty spaces. The rules used to build and integrate these maps are expressed by linguistic descriptions and modeled by fuzzy rules. The main difference of this approach from other studies reported in the literature is that the method presented here is based on the hypothesis that the concepts "occupied" and "empty" are antonyms rather than complementary (as it happens in probabilistic approaches), or independent (as it happens in the previous fuzzy models). Controlled experimentation with a real robot in three representative indoor environments has been performed and the results presented. We offer a qualitative and quantitative comparison of the estimated maps obtained by the probabilistic approach, the previous fuzzy method and the new antonyms-based fuzzy approach. It is shown that the maps obtained with the antonyms-based approach are better defined, capture better the shape of the walls and of the empty-spaces, and contain less errors due to rebounds and short-echoes. Furthermore, in spite of noise and low resolution inherent to the sonar-sensors used, the maps obtained are accurate and tolerant to imprecision.
Comments on Five Smart Card Based Password Authentication Protocols
Venue: arXiv cs.CR 2010
Year: 2010

In this paper, we use the ten security requirements proposed by Liao et al. for a smart card based authentication protocol to examine five recent work in this area. After analyses, we found that the protocols of Juang et al.'s , Hsiang et al.'s, Kim et al.'s, and Li et al.'s all suffer from offline password guessing attack if the smart card is lost, and the protocol of Xu et al.'s is subjected to an insider impersonation attack.
A Taxonomy and Survey of Energy-Efficient Data Centers and Cloud Computing Systems
Venue: arXiv cs.DC 2010
Year: 2010

Traditionally, the development of computing systems has been focused on performance improvements driven by the demand of applications from consumer, scientific and business domains. However, the ever increasing energy consumption of computing systems has started to limit further performance growth due to overwhelming electricity bills and carbon dioxide footprints. Therefore, the goal of the computer system design has been shifted to power and energy efficiency. To identify open challenges in the area and facilitate future advancements it is essential to synthesize and classify the research on power and energy-efficient design conducted to date. In this work we discuss causes and problems of high power / energy consumption, and present a taxonomy of energy-efficient design of computing systems covering the hardware, operating system, virtualization and data center levels. We survey various key works in the area and map them to our taxonomy to guide future design and development efforts. This chapter is concluded with a discussion of advancements identified in energy-efficient computing and our vision on future research directions.
On Pairs of $f$-divergences and their Joint Range
Venue: arXiv cs.IT 2010
Year: 2010

We compare two f-divergences and prove that their joint range is the convex hull of the joint range for distributions supported on only two points. Some applications of this result are given.
Empowering Collections with Swarm Behavior
Venue: arXiv cs.PL 2010
Year: 2010

Often, when modelling a system there are properties and operations that are related to a group of objects rather than to a single object. In this paper we extend Java with Swarm Behavior, a new composition operator that associates behavior with a collection of instances. The lookup resolution of swarm behavior is based on the element type of a collection and is thus orthogonal to the collection hierarchy.