OpenRaiser/Intern-Atlas huggingface dataset:
An Optimal Dynamic Mechanism for Multi-Armed Bandit Processes
Venue: arXiv cs.GT 2010
Year: 2010

We consider the problem of revenue-optimal dynamic mechanism design in settings where agents' types evolve over time as a function of their (both public and private) experience with items that are auctioned repeatedly over an infinite horizon. A central question here is understanding what natural restrictions on the environment permit the design of optimal mechanisms (note that even in the simpler static setting, optimal mechanisms are characterized only under certain restrictions). We provide a {\em structural characterization} of a natural "separable: multi-armed bandit environment (where the evolution and incentive structure of the a-priori type is decoupled from the subsequent experience in a precise sense) where dynamic optimal mechanism design is possible. Here, we present the Virtual Index Mechanism, an optimal dynamic mechanism, which maximizes the (long term) {\em virtual surplus} using the classical Gittins algorithm. The mechanism optimally balances exploration and exploitation, taking incentives into account.
Evasiveness and the Distribution of Prime Numbers
Venue: arXiv cs.CC 2010
Year: 2010

We confirm the eventual evasiveness of several classes of monotone graph properties under widely accepted number theoretic hypotheses. In particular we show that Chowla's conjecture on Dirichlet primes implies that (a) for any graph $H$, "forbidden subgraph $H$" is eventually evasive and (b) all nontrivial monotone properties of graphs with $\le n^{3/2-ε}$ edges are eventually evasive. ($n$ is the number of vertices.) While Chowla's conjecture is not known to follow from the Extended Riemann Hypothesis (ERH, the Riemann Hypothesis for Dirichlet's $L$ functions), we show (b) with the bound $O(n^{5/4-ε})$ under ERH. We also prove unconditional results: (a$'$) for any graph $H$, the query complexity of "forbidden subgraph $H$" is $\binom{n}{2} - O(1)$; (b$'$) for some constant $c>0$, all nontrivial monotone properties of graphs with $\le cn\log n+O(1)$ edges are eventually evasive. Even these weaker, unconditional results rely on deep results from number theory such as Vinogradov's theorem on the Goldbach conjecture. Our technical contribution consists in connecting the topological framework of Kahn, Saks, and Sturtevant (1984), as further developed by Chakrabarti, Khot, and Shi (2002), with a deeper analysis of the orbital structure of permutation groups and their connection to the distribution of prime numbers. Our unconditional results include stronger versions and generalizations of some result of Chakrabarti et al.
The WebContent XML Store
Venue: arXiv cs.DB 2010
Year: 2010

In this article, we describe the XML storage system used in the WebContent project. We begin by advocating the use of an XML database in order to store WebContent documents, and we present two different ways of storing and querying these documents : the use of a centralized XML database and the use of a P2P XML database.
Some Algebraic Properties of a Subclass of Finite Normal Form Games
Venue: arXiv cs.GT 2010
Year: 2010

We study the problem of computing all Nash equilibria of a subclass of finite normal form games. With algebraic characterization of the games, we present a method for computing all its Nash equilibria. Further, we present a method for deciding membership to the class of games with its related results. An appendix, containing an example to show working of each of the presented methods, concludes the work.
RFID Key Establishment Against Active Adversaries
Venue: arXiv cs.CR 2010
Year: 2010

We present a method to strengthen a very low cost solution for key agreement with a RFID device. Starting from a work which exploits the inherent noise on the communication link to establish a key by public discussion, we show how to protect this agreement against active adversaries. For that purpose, we unravel integrity $(I)$-codes suggested by Cagalj et al. No preliminary key distribution is required.
Toward a Compositional Theory of Leftist Grammars and Transformations
Venue: arXiv cs.FL 2010
Year: 2010

Leftist grammars [Motwani et al., STOC 2000] are special semi-Thue systems where symbols can only insert or erase to their left. We develop a theory of leftist grammars seen as word transformers as a tool toward rigorous analyses of their computational power. Our main contributions in this first paper are (1) constructions proving that leftist transformations are closed under compositions and transitive closures, and (2) a proof that bounded reachability is NP-complete even for leftist grammars with acyclic rules.
Design of Run time Architectures for Real time UML Models an Actor Centric Approach
Venue: arXiv cs.SE 2010
Year: 2010

Although a lot of research has taken place in Object Oriented Design of software for Real Time systems and mapping of design models to implementation models, these methodologies are applicable to systems which are less complex and small in source code size. However, in practice, the size of the software for real time applications is growing. The run time architecture of real time applications is becoming increasingly complex. In this paper, we present a generic approach for mapping the design models to run time architectures resulting in combination of processes and threads. This method is applied in development of a communication subsystem of C4I complex and shall be presented as a case study.
Directional Dynamics along Arbitrary Curves in Cellular Automata
Venue: arXiv cs.DM 2010
Year: 2010

This paper studies directional dynamics in cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behaviour of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviours inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space-time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers.
Genetic algorithm for robotic telescope scheduling
Venue: arXiv cs.AI 2010
Year: 2010

This work was inspired by author experiences with a telescope scheduling. Author long time goal is to develop and further extend software for an autonomous observatory. The software shall provide users with all the facilities they need to take scientific images of the night sky, cooperate with other autonomous observatories, and possibly more. This works shows how genetic algorithm can be used for scheduling of a single observatory, as well as network of observatories.
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits
Venue: arXiv cs.CC 2010
Year: 2010

We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem improves the known deterministic d^{k^k}-time black-box identity test over rationals (Kayal-Saraf, FOCS 2009) to one that takes d^{k^2}-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem settles affirmatively the stronger rank conjectures posed by Dvir-Shpilka (STOC 2005) and Kayal-Saraf (FOCS 2009). Our techniques provide a unified framework that actually beats all known rank bounds and hence gives the best running time (for every field) for black-box identity tests. Our main theorem (almost optimally) pins down the relation between higher dimensional Sylvester-Gallai theorems and the rank of depth-3 identities in a very transparent manner. The existence of this was hinted at by Dvir-Shpilka (STOC 2005), but first proven, for reals, by Kayal-Saraf (FOCS 2009). We introduce the concept of Sylvester-Gallai rank bounds for any field, and show the intimate connection between this and depth-3 identity rank bounds. We also prove the first ever theorem about high dimensional Sylvester-Gallai configurations over any field. Our proofs and techniques are very different from previous results and devise a very interesting ensemble of combinatorics and algebra. The latter concepts are ideal theoretic and involve a new Chinese remainder theorem. Our proof methods explain the structure of any depth-3 identity C: there is a nucleus of C that forms a low rank identity, while the remainder is a high dimensional Sylvester-Gallai configuration.
Optimal and Cut-free Tableaux for Propositional Dynamic Logic with Converse
Venue: arXiv cs.LO 2010
Year: 2010

We give an optimal (EXPTIME), sound and complete tableau-based algorithm for deciding satisfiability for propositional dynamic logic with converse (CPDL) which does not require the use of analytic cut. Our main contribution is a sound methodto combine our previous optimal method for tracking least fix-points in PDL with our previous optimal method for handling converse in the description logic ALCI. The extension is non-trivial as the two methods cannot be combined naively. We give sufficient details to enable an implementation by others. Our OCaml implementation seems to be the first theorem prover for CPDL.
Logical Evaluation of Consciousness: For Incorporating Consciousness into Machine Architecture
Venue: arXiv cs.AI 2010
Year: 2010

Machine Consciousness is the study of consciousness in a biological, philosophical, mathematical and physical perspective and designing a model that can fit into a programmable system architecture. Prime objective of the study is to make the system architecture behave consciously like a biological model does. Present work has developed a feasible definition of consciousness, that characterizes consciousness with four parameters i.e., parasitic, symbiotic, self referral and reproduction. Present work has also developed a biologically inspired consciousness architecture that has following layers: quantum layer, cellular layer, organ layer and behavioral layer and traced the characteristics of consciousness at each layer. Finally, the work has estimated physical and algorithmic architecture to devise a system that can behave consciously.
A proposition of 3D inertial tolerancing to consider the statistical combination of the location and orientation deviations
Venue: arXiv cs.OH 2010
Year: 2010

Tolerancing of assembly mechanisms is a major interest in the product life cycle. One can distinguish several models with growing complexity, from 1-dimensional (1D) to 3-dimensional (3D) (including form deviations), and two main tolerancing assumptions, the worst case and the statistical hypothesis. This paper presents an approach to 3D statistical tolerancing using a new acceptance criterion. Our approach is based on the 1D inertial acceptance criterion that is extended to 3D and form acceptance. The modal characterisation is used to describe the form deviation of a geometry as the combination of elementary deviations (location, orientation and form). The proposed 3D statistical tolerancing is applied on a simple mechanism with lever arm. It is also compared to the traditional worst-case tolerancing using a tolerance zone.
On lifting perfect codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we consider completely regular codes, obtained from perfect (Hamming) codes by lifting the ground field. More exactly, for a given perfect code C of length n=(q^m-1)/(q-1) over F_q with a parity check matrix H_m, we define a new code C_{(m,r)} of length n over F_{q^r}, r > 1, with this parity check matrix H_m. The resulting code C_{(m,r)} is completely regular with covering radius R = min{r,m}. We compute the intersection numbers of such codes and, finally, we prove that Hamming codes are the only codes that, after lifting the ground field, result in completely regular codes.
A Data Capsule Framework For Web Services: Providing Flexible Data Access Control To Users
Venue: arXiv cs.CR 2010
Year: 2010

This paper introduces the notion of a secure data capsule, which refers to an encapsulation of sensitive user information (such as a credit card number) along with code that implements an interface suitable for the use of such information (such as charging for purchases) by a service (such as an online merchant). In our capsule framework, users provide their data in the form of such capsules to web services rather than raw data. Capsules can be deployed in a variety of ways, either on a trusted third party or the user's own computer or at the service itself, through the use of a variety of hardware or software modules, such as a virtual machine monitor or trusted platform module: the only requirement is that the deployment mechanism must ensure that the user's data is only accessed via the interface sanctioned by the user. The framework further allows an user to specify policies regarding which services or machines may host her capsule, what parties are allowed to access the interface, and with what parameters. The combination of interface restrictions and policy control lets us bound the impact of an attacker who compromises the service to gain access to the user's capsule or a malicious insider at the service itself.
Face Recognition by Fusion of Local and Global Matching Scores using DS Theory: An Evaluation with Uni-classifier and Multi-classifier Paradigm
Venue: arXiv cs.CV 2010
Year: 2010

Faces are highly deformable objects which may easily change their appearance over time. Not all face areas are subject to the same variability. Therefore decoupling the information from independent areas of the face is of paramount importance to improve the robustness of any face recognition technique. This paper presents a robust face recognition technique based on the extraction and matching of SIFT features related to independent face areas. Both a global and local (as recognition from parts) matching strategy is proposed. The local strategy is based on matching individual salient facial SIFT features as connected to facial landmarks such as the eyes and the mouth. As for the global matching strategy, all SIFT features are combined together to form a single feature. In order to reduce the identification errors, the Dempster-Shafer decision theory is applied to fuse the two matching techniques. The proposed algorithms are evaluated with the ORL and the IITK face databases. The experimental results demonstrate the effectiveness and potential of the proposed face recognition techniques also in the case of partially occluded faces or with missing information.
Cooperative Algorithms for MIMO Interference Channels
Venue: arXiv cs.IT 2010
Year: 2010

Interference alignment is a transmission technique for exploiting all available degrees of freedom in the interference channel with an arbitrary number of users. Most prior work on interference alignment, however, neglects interference from other nodes in the network not participating in the alignment operation. This paper proposes three generalizations of interference alignment for the multiple-antenna interference channel with multiple users that account for colored noise, which models uncoordinated interference. First, a minimum interference-plus-noise leakage algorithm is presented, and shown to be equivalent to previous subspace methods when noise is spatially white or negligible. A joint minimum mean squared error design is then proposed that jointly optimizes the transmit precoders and receive spatial filters, whereas previous designs neglect the receive spatial filter. This algorithm is shown to be a generalization of previous joint MMSE designs for other system configurations such as the broadcast channel. Finally, a maximum signal-to-interference-plus-noise ratio algorithm is developed that is proven to converge, unlike previous maximum SINR algorithms. The latter two designs are shown to have increased complexity due to non-orthogonal precoders, more required iterations, or more channel state knowledge than the min INL or subspace methods. The sum throughput performance of these algorithms is simulated in the context of a network with uncoordinated co-channel interferers not participating in the alignment protocol. It is found that a network with cochannel interference can benefit from employing precoders designed to consider that interference, but in some cases, ignoring the co-channel interference is advantageous.
Detecting Motifs in System Call Sequences
Venue: arXiv cs.AI 2010
Year: 2010

The search for patterns or motifs in data represents an area of key interest to many researchers. In this paper we present the Motif Tracking Algorithm, a novel immune inspired pattern identification tool that is able to identify unknown motifs which repeat within time series data. The power of the algorithm is derived from its use of a small number of parameters with minimal assumptions. The algorithm searches from a completely neutral perspective that is independent of the data being analysed, and the underlying motifs. In this paper the motif tracking algorithm is applied to the search for patterns within sequences of low level system calls between the Linux kernel and the operating system's user space. The MTA is able to compress data found in large system call data sets to a limited number of motifs which summarise that data. The motifs provide a resource from which a profile of executed processes can be built. The potential for these profiles and new implications for security research are highlighted. A higher level call system language for measuring similarity between patterns of such calls is also suggested.
Some improved results on communication between information systems
Venue: arXiv cs.AI 2010
Year: 2010

To study the communication between information systems, Wang et al. [C. Wang, C. Wu, D. Chen, Q. Hu, and C. Wu, Communicating between information systems, Information Sciences 178 (2008) 3228-3239] proposed two concepts of type-1 and type-2 consistent functions. Some properties of such functions and induced relation mappings have been investigated there. In this paper, we provide an improvement of the aforementioned work by disclosing the symmetric relationship between type-1 and type-2 consistent functions. We present more properties of consistent functions and induced relation mappings and improve upon several deficient assertions in the original work. In particular, we unify and extend type-1 and type-2 consistent functions into the so-called neighborhood-consistent functions. This provides a convenient means for studying the communication between information systems based on various neighborhoods.
Miniaturized wireless sensor network
Venue: arXiv cs.NI 2010
Year: 2010

This paper addresses an overview of the wireless sensor networks. It is shown that MEMS/NEMS technologies and SIP concept are well suited for advanced architectures. It is also shown analog architectures have to be compatible with digital signal techniques to develop smart network of microsystem.
Minimum and maximum against k lies
Venue: arXiv cs.DS 2010
Year: 2010

A neat 1972 result of Pohl asserts that [3n/2]-2 comparisons are sufficient, and also necessary in the worst case, for finding both the minimum and the maximum of an n-element totally ordered set. The set is accessed via an oracle for pairwise comparisons. More recently, the problem has been studied in the context of the Renyi-Ulam liar games, where the oracle may give up to k false answers. For large k, an upper bound due to Aigner shows that (k+O(\sqrt{k}))n comparisons suffice. We improve on this by providing an algorithm with at most (k+1+C)n+O(k^3) comparisons for some constant C. The known lower bounds are of the form (k+1+c_k)n-D, for some constant D, where c_0=0.5, c_1=23/32=0.71875, and c_k=Ω(2^{-5k/4}) as k goes to infinity.
Homomorphisms between fuzzy information systems revisited
Venue: arXiv cs.AI 2010
Year: 2010

Recently, Wang et al. discussed the properties of fuzzy information systems under homomorphisms in the paper [C. Wang, D. Chen, L. Zhu, Homomorphisms between fuzzy information systems, Applied Mathematics Letters 22 (2009) 1045-1050], where homomorphisms are based upon the concepts of consistent functions and fuzzy relation mappings. In this paper, we classify consistent functions as predecessor-consistent and successor-consistent, and then proceed to present more properties of consistent functions. In addition, we improve some characterizations of fuzzy relation mappings provided by Wang et al.
Finding Sequential Patterns from Large Sequence Data
Venue: arXiv cs.DB 2010
Year: 2010

Data mining is the task of discovering interesting patterns from large amounts of data. There are many data mining tasks, such as classification, clustering, association rule mining, and sequential pattern mining. Sequential pattern mining finds sets of data items that occur together frequently in some sequences. Sequential pattern mining, which extracts frequent subsequences from a sequence database, has attracted a great deal of interest during the recent data mining research because it is the basis of many applications, such as: web user analysis, stock trend prediction, DNA sequence analysis, finding language or linguistic patterns from natural language texts, and using the history of symptoms to predict certain kind of disease. The diversity of the applications may not be possible to apply a single sequential pattern model to all these problems. Each application may require a unique model and solution. A number of research projects were established in recent years to develop meaningful sequential pattern models and efficient algorithms for mining these patterns. In this paper, we theoretically provided a brief overview three types of sequential patterns model.
Realistic Approach towards Quantitative Analysis and Simulation of EEHC-Based Routing for Wireless Sensor Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper presents the realistic approach towards the quantitative analysis and simulation of Energy Efficient Hierarchical Cluster (EEHC)-based routing for wireless sensor networks. Here the efforts have been done to combine analytical hardware model with the modified EEHC-based routing model. The dependence of various performance metrics like: optimum number of clusters, Energy Consumption, and Energy consumed per round etc. based on analytical hardware sensor model and EEHC model has been presented.
Node Disjoint Multipath Routing Considering Link and Node Stability protocol: A characteristic Evaluation
Venue: arXiv cs.NI 2010
Year: 2010

Mobile Ad hoc Networks are highly dynamic networks. Quality of Service (QoS) routing in such networks is usually limited by the network breakage due to either node mobility or energy depletion of the mobile nodes. Also, to fulfill certain quality parameters, presence of multiple node-disjoint paths becomes essential. Such paths aid in the optimal traffic distribution and reliability in case of path breakages. Thus, to cater various challenges in QoS routing in Mobile Add hoc Networks, a Node Disjoint Multipath Routing Considering Link and Node Stability (NDMLNR) protocol has been proposed by the authors. The metric used to select the paths takes into account the stability of the nodes and the corresponding links. This paper studies various challenges in the QoS routing and presents the characteristic evaluation of NDMLNR w.r.t various existing protocols in this area.