OpenRaiser/Intern-Atlas huggingface dataset:
Quantum Cyclic Code
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we define and study \emph{quantum cyclic codes}, a generalisation of cyclic codes to the quantum setting. Previously studied examples of quantum cyclic codes were all quantum codes obtained from classical cyclic codes via the CSS construction. However, the codes that we study are much more general. In particular, we construct cyclic stabiliser codes with parameters $[[5,1,3]]$, $[[17,1,7]]$ and $[[17,9,3]]$, all of which are \emph{not} CSS. The $[[5,1,3]]$ code is the well known Laflamme code and to the best of our knowledge the other two are new examples. Our definition of cyclicity applies to non-stabiliser codes as well; in fact we show that the $((5,6,2))$ nonstabiliser first constructed by Rains\etal~ cite{rains97nonadditive} and latter by Arvind \etal~\cite{arvind:2004:nonstabilizer} is cyclic. We also study stabiliser codes of length $4^m +1$ over $\mathbb{F}_2$ for which we define a notation of BCH distance. Much like the Berlekamp decoding algorithm for classical BCH codes, we give efficient quantum algorithms to correct up to $\floor{\frac{d-1}{2}}$ errors when the BCH distance is $d$.
A Study on the Effectiveness of Different Patch Size and Shape for Eyes and Mouth Detection
Venue: arXiv cs.CV 2010
Year: 2010

Template matching is one of the simplest methods used for eyes and mouth detection. However, it can be modified and extended to become a powerful tool. Since the patch itself plays a significant role in optimizing detection performance, a study on the influence of patch size and shape is carried out. The optimum patch size and shape is determined using the proposed method. Usually, template matching is also combined with other methods in order to improve detection accuracy. Thus, in this paper, the effectiveness of two image processing methods i.e. grayscale and Haar wavelet transform, when used with template matching are analyzed.
StochKit-FF: Efficient Systems Biology on Multicore Architectures
Venue: arXiv cs.CE 2010
Year: 2010

The stochastic modelling of biological systems is an informative, and in some cases, very adequate technique, which may however result in being more expensive than other modelling approaches, such as differential equations. We present StochKit-FF, a parallel version of StochKit, a reference toolkit for stochastic simulations. StochKit-FF is based on the FastFlow programming toolkit for multicores and exploits the novel concept of selective memory. We experiment StochKit-FF on a model of HIV infection dynamics, with the aim of extracting information from efficiently run experiments, here in terms of average and variance and, on a longer term, of more structured data.
Multimode Control Attacks on Elections
Venue: arXiv cs.GT 2010
Year: 2010

In 1992, Bartholdi, Tovey, and Trick opened the study of control attacks on elections---attempts to improve the election outcome by such actions as adding/deleting candidates or voters. That work has led to many results on how algorithms can be used to find attacks on elections and how complexity-theoretic hardness results can be used as shields against attacks. However, all the work in this line has assumed that the attacker employs just a single type of attack. In this paper, we model and study the case in which the attacker launches a multipronged (i.e., multimode) attack. We do so to more realistically capture the richness of real-life settings. For example, an attacker might simultaneously try to suppress some voters, attract new voters into the election, and introduce a spoiler candidate. Our model provides a unified framework for such varied attacks, and by constructing polynomial-time multiprong attack algorithms we prove that for various election systems even such concerted, flexible attacks can be perfectly planned in deterministic polynomial time.
What's wrong with Phong - Designers' appraisal of shading in CAD-systems
Venue: arXiv cs.GR 2010
Year: 2010

The Phong illumination model is still widely used in realtime 3D visualization systems. The aim of this article is to document problems with the Phong illumination model that are encountered by an important professional user group, namely digital designers. This leads to a visual evaluation of Phong illumination, which at least in this condensed form seems still to be missing in the literature. It is hoped that by explicating these flaws, awareness about the limitations and interdependencies of the model will increase, both among fellow users, and among researchers and developers.
Darknet-Based Inference of Internet Worm Temporal Characteristics
Venue: arXiv cs.CR 2010
Year: 2010

Internet worm attacks pose a significant threat to network security and management. In this work, we coin the term Internet worm tomography as inferring the characteristics of Internet worms from the observations of Darknet or network telescopes that monitor a routable but unused IP address space. Under the framework of Internet worm tomography, we attempt to infer Internet worm temporal behaviors, i.e., the host infection time and the worm infection sequence, and thus pinpoint patient zero or initially infected hosts. Specifically, we introduce statistical estimation techniques and propose method of moments, maximum likelihood, and linear regression estimators. We show analytically and empirically that our proposed estimators can better infer worm temporal characteristics than a naive estimator that has been used in the previous work. We also demonstrate that our estimators can be applied to worms using different scanning strategies such as random scanning and localized scanning.
A Note on Semantic Web Services Specification and Composition in Constructive Description Logics
Venue: arXiv cs.AI 2010
Year: 2010

The idea of the Semantic Web is to annotate Web content and services with computer interpretable descriptions with the aim to automatize many tasks currently performed by human users. In the context of Web services, one of the most interesting tasks is their composition. In this paper we formalize this problem in the framework of a constructive description logic. In particular we propose a declarative service specification language and a calculus for service composition. We show by means of an example how this calculus can be used to define composed Web services and we discuss the problem of automatic service synthesis.
XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme
Venue: arXiv cs.DS 2010
Year: 2010

Query evaluation in an XML database requires reconstructing XML subtrees rooted at nodes found by an XML query. Since XML subtree reconstruction can be expensive, one approach to improve query response time is to use reconstruction views - materialized XML subtrees of an XML document, whose nodes are frequently accessed by XML queries. For this approach to be efficient, the principal requirement is a framework for view selection. In this work, we are the first to formalize and study the problem of XML reconstruction view selection. The input is a tree $T$, in which every node $i$ has a size $c_i$ and profit $p_i$, and the size limitation $C$. The target is to find a subset of subtrees rooted at nodes $i_1,\cdots, i_k$ respectively such that $c_{i_1}+\cdots +c_{i_k}\le C$, and $p_{i_1}+\cdots +p_{i_k}$ is maximal. Furthermore, there is no overlap between any two subtrees selected in the solution. We prove that this problem is NP-hard and present a fully polynomial-time approximation scheme (FPTAS) as a solution.
Channel Sounding for the Masses: Low Complexity GNU 802.11b Channel Impulse Response Estimation
Venue: arXiv cs.OH 2010
Year: 2010

New techniques in cross-layer wireless networks are building demand for ubiquitous channel sounding, that is, the capability to measure channel impulse response (CIR) with any standard wireless network and node. Towards that goal, we present a software-defined IEEE 802.11b receiver and CIR estimation system with little additional computational complexity compared to 802.11b reception alone. The system implementation, using the universal software radio peripheral (USRP) and GNU Radio, is described and compared to previous work. By overcoming computational limitations and performing direct-sequence spread-spectrum (DS-SS) matched filtering on the USRP, we enable high-quality yet inexpensive CIR estimation. We validate the channel sounder and present a drive test campaign which measures hundreds of channels between WiFi access points and an in-vehicle receiver in urban and suburban areas.
Min st-Cut of a Planar Graph in O(n loglog n) Time
Venue: arXiv cs.DM 2010
Year: 2010

Given a planar undirected n-vertex graph G with non-negative edge weights, we show how to compute, for given vertices s and t in G, a min st-cut in G in O(n loglog n) time and O(n) space. The previous best time bound was O(n log n).
Mobile Web Service Discovery in Peer to Peer Networks
Venue: arXiv cs.DC 2010
Year: 2010

The advanced features of today's smart phones and hand held devices, like the increased memory and processing capabilities, allowed them to act even as information providers. Thus a smart phone hosting web services is not a fancy anymore. But the relevant discovery of these services provided by the smart phones has became quite complex, because of the volume of services possible with each Mobile Host providing some services. Centralized registries have severe drawbacks in such a scenario and alternate means of service discovery are to be addressed. P2P domain with it resource sharing capabilities comes quite handy and here in this paper we provide an alternate approach to UDDI registry for discovering mobile web services. The services are published into the P2P network as JXTA modules and the discovery issues of these module advertisements are addressed. The approach also provides alternate means of identifying the Mobile Host.
Alternatives to Mobile Keypad Design: Improved Text Feed
Venue: arXiv cs.HC 2010
Year: 2010

In this paper we tried to focus on some of the problems with the mobile keypad and text entering in these devices, and tried to give some possible suggestions. We mainly took some of the basic Human Computer Interaction principles and some general issues into consideration.
Secure Communication and Access Control for Mobile Web Service Provisioning
Venue: arXiv cs.DC 2010
Year: 2010

It is now feasible to host basic web services on a smart phone due to the advances in wireless devices and mobile communication technologies. While the applications are quite welcoming, the ability to provide secure and reliable communication in the vulnerable and volatile mobile ad-hoc topologies is vastly becoming necessary. The paper mainly addresses the details and issues in providing secured communication and access control for the mobile web service provisioning domain. While the basic message-level security can be provided, providing proper access control mechanisms for the Mobile Host still poses a great challenge. This paper discusses details of secure communication and proposes the distributed semantics-based authorization mechanism.
A decidable subclass of finitary programs
Venue: arXiv cs.AI 2010
Year: 2010

Answer set programming - the most popular problem solving paradigm based on logic programs - has been recently extended to support uninterpreted function symbols. All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 programs enjoy the following unique combination of properties: (i) the ability of expressing predicates with infinite extensions; (ii) full support for predicates with arbitrary arity; (iii) decidability of FP2 membership checking; (iv) decidability of skeptical and credulous stable model reasoning for call-safe queries. Odd cycles are supported by composing FP2 programs with argument restricted programs.
Scheduling to Minimize Energy and Flow Time in Broadcast Scheduling
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we initiate the study of minimizing power consumption in the broadcast scheduling model. In this setting there is a wireless transmitter. Over time requests arrive at the transmitter for pages of information. Multiple requests may be for the same page. When a page is transmitted, all requests for that page receive the transmission simulteneously. The speed the transmitter sends data at can be dynamically scaled to conserve energy. We consider the problem of minimizing flow time plus energy, the most popular scheduling metric considered in the standard scheduling model when the scheduler is energy aware. We will assume that the power consumed is modeled by an arbitrary convex function. For this problem there is a $Ω(n)$ lower bound. Due to the lower bound, we consider the resource augmentation model of Gupta \etal \cite{GuptaKP10}. Using resource augmentation, we give a scalable algorithm. Our result also gives a scalable non-clairvoyant algorithm for minimizing weighted flow time plus energy in the standard scheduling model.
A thermodynamic framework to develop rate-type models for fluids without instantaneous elasticity
Venue: arXiv cs.NA 2010
Year: 2010

In this paper, we apply the thermodynamic framework recently put into place by Rajagopal and co-workers, to develop rate-type models for viscoelastic fluids which do not possess instantaneous elasticity. To illustrate the capabilities of such models we make a specific choice for the specific Helmholtz potential and the rate of dissipation and consider the creep and stress relaxation response associated with the model. Given specific forms for the Helmholtz potential and the rate of dissipation, the rate of dissipation is maximized with the constraint that the difference between the stress power and the rate of change of Helmholtz potential is equal to the rate of dissipation and any other constraint that may be applicable such as incompressibility. We show that the model that is developed exhibits fluid-like characteristics and is incapable of instantaneous elastic response. It also includes Maxwell-like and Kelvin-Voigt-like viscoelastic materials (when certain material moduli take special values).
New Results for the MAP Problem in Bayesian Networks
Venue: arXiv cs.AI 2010
Year: 2010

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
Venue: arXiv cs.GT 2010
Year: 2010

We present a direct reduction from k-player games to 2-player games that preserves approximate Nash equilibrium. Previously, the computational equivalence of computing approximate Nash equilibrium in k-player and 2-player games was established via an indirect reduction. This included a sequence of works defining the complexity class PPAD, identifying complete problems for this class, showing that computing approximate Nash equilibrium for k-player games is in PPAD, and reducing a PPAD-complete problem to computing approximate Nash equilibrium for 2-player games. Our direct reduction makes no use of the concept of PPAD, thus eliminating some of the difficulties involved in following the known indirect reduction.
Disjunctive ASP with Functions: Decidable Queries and Effective Computation
Venue: arXiv cs.LO 2010
Year: 2010

Querying over disjunctive ASP with functions is a highly undecidable task in general. In this paper we focus on disjunctive logic programs with stratified negation and functions under the stable model semantics (ASP^{fs}). We show that query answering in this setting is decidable, if the query is finitely recursive (ASP^{fs}_{fr}). Our proof yields also an effective method for query evaluation. It is done by extending the magic set technique to ASP^{fs}_{fr}. We show that the magic-set rewritten program is query equivalent to the original one (under both brave and cautious reasoning). Moreover, we prove that the rewritten program is also finitely ground, implying that it is decidable. Importantly, finitely ground programs are evaluable using existing ASP solvers, making the class of ASP^{fs}_{fr} queries usable in practice.
Reinforcement Learning in BitTorrent Systems
Venue: arXiv cs.NI 2010
Year: 2010

Recent research efforts have shown that the popular BitTorrent protocol does not provide fair resource reciprocation and may allow free-riding. In this paper, we propose a BitTorrent-like protocol that replaces the peer selection mechanisms in the regular BitTorrent protocol with a novel reinforcement learning (RL) based mechanism. Due to the inherent opration of P2P systems, which involves repeated interactions among peers over a long period of time, the peers can efficiently identify free-riders as well as desirable collaborators by learning the behavior of their associated peers. Thus, it can help peers improve their download rates and discourage free-riding, while improving fairness in the system. We model the peers' interactions in the BitTorrent-like network as a repeated interaction game, where we explicitly consider the strategic behavior of the peers. A peer, which applies the RL-based mechanism, uses a partial history of the observations on associated peers' statistical reciprocal behaviors to determine its best responses and estimate the corresponding impact on its expected utility. The policy determines the peer's resource reciprocations with other peers, which would maximize the peer's long-term performance, thereby making foresighted decisions. We have implemented the proposed reinforcement-learning based mechanism and incorporated it into an existing BitTorrent client. We have performed extensive experiments on a controlled Planetlab test bed. Our results confirm that our proposed protocol (1) promotes fairness in terms of incentives to each peer's contribution e.g. high capacity peers improve their download completion time by up to 33\%, (2) improves the system stability and robustness e.g. reducing the peer selection luctuations by 57\%, and (3) discourages free-riding e.g. peers reduce by 64\% their upload to \FR, in comparison to the regular \BT~protocol.
Clustering Unstructured Data (Flat Files) - An Implementation in Text Mining Tool
Venue: arXiv cs.IR 2010
Year: 2010

With the advancement of technology and reduced storage costs, individuals and organizations are tending towards the usage of electronic media for storing textual information and documents. It is time consuming for readers to retrieve relevant information from unstructured document collection. It is easier and less time consuming to find documents from a large collection when the collection is ordered or classified by group or category. The problem of finding best such grouping is still there. This paper discusses the implementation of k-Means clustering algorithm for clustering unstructured text documents that we implemented, beginning with the representation of unstructured text and reaching the resulting set of clusters. Based on the analysis of resulting clusters for a sample set of documents, we have also proposed a technique to represent documents that can further improve the clustering result.
A Hybrid Model for Disease Spread and an Application to the SARS Pandemic
Venue: arXiv cs.MA 2010
Year: 2010

Pandemics can cause immense disruption and damage to communities and societies. Thus far, modeling of pandemics has focused on either large-scale difference equation models like the SIR and the SEIR models, or detailed micro-level simulations, which are harder to apply at a global scale. This paper introduces a hybrid model for pandemics considering both global and local spread of infections. We hypothesize that the spread of an infectious disease between regions is significantly influenced by global traffic patterns and the spread within a region is influenced by local conditions. Thus we model the spread of pandemics considering the connections between regions for the global spread of infection and population density based on the SEIR model for the local spread of infection. We validate our hybrid model by carrying out a simulation study for the spread of SARS pandemic of 2002-2003 using available data on population, population density, and traffic networks between different regions. While it is well-known that international relationships and global traffic patterns significantly influence the spread of pandemics, our results show that integrating these factors into relatively simple models can greatly improve the results of modeling disease spread.
CapEst: A Measurement-based Approach to Estimating Link Capacity in Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

Estimating link capacity in a wireless network is a complex task because the available capacity at a link is a function of not only the current arrival rate at that link, but also of the arrival rate at links which interfere with that link as well as of the nature of interference between these links. Models which accurately characterize this dependence are either too computationally complex to be useful or lack accuracy. Further, they have a high implementation overhead and make restrictive assumptions, which makes them inapplicable to real networks. In this paper, we propose CapEst, a general, simple yet accurate, measurement-based approach to estimating link capacity in a wireless network. To be computationally light, CapEst allows inaccuracy in estimation; however, using measurements, it can correct this inaccuracy in an iterative fashion and converge to the correct estimate. Our evaluation shows that CapEst always converged to within 5% of the correct value in less than 18 iterations. CapEst is model-independent, hence, is applicable to any MAC/PHY layer and works with auto-rate adaptation. Moreover, it has a low implementation overhead, can be used with any application which requires an estimate of residual capacity on a wireless link and can be implemented completely at the network layer without any support from the underlying chipset.
Predicting Suicide Attacks: A Fuzzy Soft Set Approach
Venue: arXiv cs.AI 2010
Year: 2010

This paper models a decision support system to predict the occurance of suicide attack in a given collection of cities. The system comprises two parts. First part analyzes and identifies the factors which affect the prediction. Admitting incomplete information and use of linguistic terms by experts, as two characteristic features of this peculiar prediction problem we exploit the Theory of Fuzzy Soft Sets. Hence the Part 2 of the model is an algorithm vz. FSP which takes the assessment of factors given in Part 1 as its input and produces a possibility profile of cities likely to receive the accident. The algorithm is of O(2^n) complexity. It has been illustrated by an example solved in detail. Simulation results for the algorithm have been presented which give insight into the strengths and weaknesses of FSP. Three different decision making measures have been simulated and compared in our discussion.