OpenRaiser/Intern-Atlas huggingface dataset:
Towards P = NP via k-SAT: A k-SAT Algorithm Using Linear Algebra on Finite Fields
Venue: arXiv cs.DS 2011
Year: 2011

The problem of P vs. NP is very serious, and solutions to the problem can help save lives. This article is an attempt at solving the problem using a computer algorithm. It is presented in a fashion that will hopefully allow for easy understanding for many people and scientists from many diverse fields. In technical terms, a novel method for solving k-SAT is explained. This method is primarily based on linear algebra and finite fields. Evidence is given that this method may require rougly O(n^3) time and space for deterministic models. More specifically the algorithm runs in time O(P V(n+V)^2) with mistaking satisfiable Boolean expressions as unsatisfiable with an approximate probablity 1 / Θ(V(n+V)^2)^P, where n is the number of clauses and V is the number of variables. It's concluded that significant evidence exists that P=NP. There is a forum devoted to this paper at http://482527.ForumRomanum.com. All are invited to correspond here and help with the analysis of the algorithm. Source code for the associated algorithm can be found at https://sourceforge.net/p/la3sat.
Actor-network procedures: Modeling multi-factor authentication, device pairing, social interactions
Venue: arXiv cs.CR 2011
Year: 2011

As computation spreads from computers to networks of computers, and migrates into cyberspace, it ceases to be globally programmable, but it remains programmable indirectly: network computations cannot be controlled, but they can be steered by local constraints on network nodes. The tasks of "programming" global behaviors through local constraints belong to the area of security. The "program particles" that assure that a system of local interactions leads towards some desired global goals are called security protocols. As computation spreads beyond cyberspace, into physical and social spaces, new security tasks and problems arise. As networks are extended by physical sensors and controllers, including the humans, and interlaced with social networks, the engineering concepts and techniques of computer security blend with the social processes of security. These new connectors for computational and social software require a new "discipline of programming" of global behaviors through local constraints. Since the new discipline seems to be emerging from a combination of established models of security protocols with older methods of procedural programming, we use the name procedures for these new connectors, that generalize protocols. In the present paper we propose actor-networks as a formal model of computation in heterogenous networks of computers, humans and their devices; and we introduce Procedure Derivation Logic (PDL) as a framework for reasoning about security in actor-networks. On the way, we survey the guiding ideas of Protocol Derivation Logic (also PDL) that evolved through our work in security in last 10 years. Both formalisms are geared towards graphic reasoning and tool support. We illustrate their workings by analysing a popular form of two-factor authentication, and a multi-channel device pairing procedure, devised for this occasion.
Efficient Reinforcement Learning Using Recursive Least-Squares Methods
Venue: arXiv cs.LG 2011
Year: 2011

The recursive least-squares (RLS) algorithm is one of the most well-known algorithms used in adaptive filtering, system identification and adaptive control. Its popularity is mainly due to its fast convergence speed, which is considered to be optimal in practice. In this paper, RLS methods are used to solve reinforcement learning problems, where two new reinforcement learning algorithms using linear value function approximators are proposed and analyzed. The two algorithms are called RLS-TD(lambda) and Fast-AHC (Fast Adaptive Heuristic Critic), respectively. RLS-TD(lambda) can be viewed as the extension of RLS-TD(0) from lambda=0 to general lambda within interval [0,1], so it is a multi-step temporal-difference (TD) learning algorithm using RLS methods. The convergence with probability one and the limit of convergence of RLS-TD(lambda) are proved for ergodic Markov chains. Compared to the existing LS-TD(lambda) algorithm, RLS-TD(lambda) has advantages in computation and is more suitable for online learning. The effectiveness of RLS-TD(lambda) is analyzed and verified by learning prediction experiments of Markov chains with a wide range of parameter settings. The Fast-AHC algorithm is derived by applying the proposed RLS-TD(lambda) algorithm in the critic network of the adaptive heuristic critic method. Unlike conventional AHC algorithm, Fast-AHC makes use of RLS methods to improve the learning-prediction efficiency in the critic. Learning control experiments of the cart-pole balancing and the acrobot swing-up problems are conducted to compare the data efficiency of Fast-AHC with conventional AHC. From the experimental results, it is shown that the data efficiency of learning control can also be improved by using RLS methods in the learning-prediction process of the critic. The performance of Fast-AHC is also compared with that of the AHC method using LS-TD(lambda). Furthermore, it is demonstrated in the experiments that different initial values of the variance matrix in RLS-TD(lambda) are required to get better performance not only in learning prediction but also in learning control. The experimental results are analyzed based on the existing theoretical work on the transient phase of forgetting factor RLS methods.
A Dual Approach for Solving Nonlinear Infinite-Norm Minimization Problems with Applications in Separable Cases
Venue: arXiv cs.CC 2011
Year: 2011

In this paper, we focus on nonlinear infinite-norm minimization problems that have many applications, especially in computer science and operations research. We set a reliable Lagrangian dual aproach for solving this kind of problems in general, and based on this method, we propose an algorithm for the mixed linear and nonlinear infinite-norm minimization cases with numerical results.
Secure Deletion on Log-structured File Systems
Venue: arXiv cs.CR 2011
Year: 2011

We address the problem of secure data deletion on log-structured file systems. We focus on the YAFFS file system, widely used on Android smartphones. We show that these systems provide no temporal guarantees on data deletion and that deleted data still persists for nearly 44 hours with average phone use and indefinitely if the phone is not used after the deletion. Furthermore, we show that file overwriting and encryption, methods commonly used for secure deletion on block-structured file systems, do not ensure data deletion in log-structured file systems. We propose three mechanisms for secure deletion on log-structured file systems. Purging is a user-level mechanism that guarantees secure deletion at the cost of negligible device wear. Ballooning is a user-level mechanism that runs continuously and gives probabilistic improvements to secure deletion. Zero overwriting is a kernel-level mechanism that guarantees immediate secure deletion without device wear. We implement these mechanisms on Nexus One smartphones and show that they succeed in secure deletion and neither prohibitively reduce the longevity of the flash memory nor noticeably reduce the device's battery lifetime. These techniques provide mobile phone users more confidence that data they delete from their phones are indeed deleted.
A Game-Theoretic approach to Fault Diagnosis of Hybrid Systems
Venue: arXiv cs.FL 2011
Year: 2011

Physical systems can fail. For this reason the problem of identifying and reacting to faults has received a large attention in the control and computer science communities. In this paper we study the fault diagnosis problem for hybrid systems from a game-theoretical point of view. A hybrid system is a system mixing continuous and discrete behaviours that cannot be faithfully modeled neither by using a formalism with continuous dynamics only nor by a formalism including only discrete dynamics. We use the well known framework of hybrid automata for modeling hybrid systems, and we define a Fault Diagnosis Game on them, using two players: the environment and the diagnoser. The environment controls the evolution of the system and chooses whether and when a fault occurs. The diagnoser observes the external behaviour of the system and announces whether a fault has occurred or not. Existence of a winning strategy for the diagnoser implies that faults can be detected correctly, while computing such a winning strategy corresponds to implement a diagnoser for the system. We will show how to determine the existence of a winning strategy, and how to compute it, for some decidable classes of hybrid automata like o-minimal hybrid automata.
Towards Efficient Exact Synthesis for Linear Hybrid Systems
Venue: arXiv cs.LO 2011
Year: 2011

We study the problem of automatically computing the controllable region of a Linear Hybrid Automaton, with respect to a safety objective. We describe the techniques that are needed to effectively and efficiently implement a recently-proposed solution procedure, based on polyhedral abstractions of the state space. Supporting experimental results are presented, based on an implementation of the proposed techniques on top of the tool PHAVer.
Optimal Repair of MDS Codes in Distributed Storage via Subspace Interference Alignment
Venue: arXiv cs.IT 2011
Year: 2011

It is well known that an (n,k) code can be used to store 'k' units of information in 'n' unit-capacity disks of a distributed data storage system. If the code used is maximum distance separable (MDS), then the system can tolerate any (n-k) disk failures, since the original information can be recovered from any k surviving disks. The focus of this paper is the design of a systematic MDS code with the additional property that a single disk failure can be repaired with minimum repair bandwidth, i.e., with the minimum possible amount of data to be downloaded for recovery of the failed disk. Previously, a lower bound of (n-1)/(n-k) units has been established by Dimakis et. al, on the repair bandwidth for a single disk failure in an (n,k) MDS code . Recently, the existence of asymptotic codes achieving this lower bound for arbitrary (n,k) has been established by drawing connections to interference alignment. While the existence of asymptotic constructions achieving this lower bound have been shown, finite code constructions achieving this lower bound existed in previous literature only for the special (high-redundancy) scenario where $k \leq \max(n/2,3)$. The question of existence of finite codes for arbitrary values of (n,k) achieving the lower bound on the repair bandwidth remained open. In this paper, by using permutation coding sub-matrices, we provide the first known finite MDS code which achieves the optimal repair bandwidth of (n-1)/(n-k) for arbitrary (n,k), for recovery of a failed systematic disk. We also generalize our permutation matrix based constructions by developing a novel framework for repair-bandwidth-optimal MDS codes based on the idea of subspace interference alignment - a concept previously introduced by Suh and Tse the context of wireless cellular networks.
Traffic Performance Analysis of Manet Routing Protocol
Venue: arXiv cs.DC 2011
Year: 2011

The primary objective of this research work is to study and investigate the performance measures of Gossip Routing protocol and Energy Efficient and Reliable Adaptive Gossip routing protocols. We use TCP and CBR based traffic models to analyze the performance of above mentioned protocols based on the parameters of Packet Delivery Ratio, Average End-to-End Delay and Throughput. We will investigate the effect of change in the simulation time and Number of nodes for the MANET routing protocols. For Simulation, we have used ns-2 simulator.
Exact Free Distance and Trapping Set Growth Rates for LDPC Convolutional Codes
Venue: arXiv cs.IT 2011
Year: 2011

Ensembles of (J,K)-regular low-density parity-check convolutional (LDPCC) codes are known to be asymptotically good, in the sense that the minimum free distance grows linearly with the constraint length. In this paper, we use a protograph-based analysis of terminated LDPCC codes to obtain an upper bound on the free distance growth rate of ensembles of periodically time-varying LDPCC codes. This bound is compared to a lower bound and evaluated numerically. It is found that, for a sufficiently large period, the bounds coincide. This approach is then extended to obtain bounds on the trapping set numbers, which define the size of the smallest, non-empty trapping sets, for these asymptotically good, periodically time-varying LDPCC code ensembles.
Consistent Query Answering under Spatial Semantic Constraints
Venue: arXiv cs.DB 2011
Year: 2011

Consistent query answering is an inconsistency tolerant approach to obtaining semantically correct answers from a database that may be inconsistent with respect to its integrity constraints. In this work we formalize the notion of consistent query answer for spatial databases and spatial semantic integrity constraints. In order to do this, we first characterize conflicting spatial data, and next, we define admissible instances that restore consistency while staying close to the original instance. In this way we obtain a repair semantics, which is used as an instrumental concept to define and possibly derive consistent query answers. We then concentrate on a class of spatial denial constraints and spatial queries for which there exists an efficient strategy to compute consistent query answers. This study applies inconsistency tolerance in spatial databases, rising research issues that shift the goal from the consistency of a spatial database to the consistency of query answering.
Towards OWL-based Knowledge Representation in Petrology
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents our work on development of OWL-driven systems for formal representation and reasoning about terminological knowledge and facts in petrology. The long-term aim of our project is to provide solid foundations for a large-scale integration of various kinds of knowledge, including basic terms, rock classification algorithms, findings and reports. We describe three steps we have taken towards that goal here. First, we develop a semi-automated procedure for transforming a database of igneous rock samples to texts in a controlled natural language (CNL), and then a collection of OWL ontologies. Second, we create an OWL ontology of important petrology terms currently described in natural language thesauri. We describe a prototype of a tool for collecting definitions from domain experts. Third, we present an approach to formalization of current industrial standards for classification of rock samples, which requires linear equations in OWL 2. In conclusion, we discuss a range of opportunities arising from the use of semantic technologies in petrology and outline the future work in this area.
A Neural Network Model for Construction Projects Site Overhead Cost Estimating in Egypt
Venue: arXiv cs.NE 2011
Year: 2011

Estimating of the overhead costs of building construction projects is an important task in the management of these projects. The quality of construction management depends heavily on their accurate cost estimation. Construction costs prediction is a very difficult and sophisticated task especially when using manual calculation methods. This paper uses Artificial Neural Network (ANN) approach to develop a parametric cost-estimating model for site overhead cost in Egypt. Fifty-two actual real-life cases of building projects constructed in Egypt during the seven year period 2002-2009 were used as training materials. The neural network architecture is presented for the estimation of the site overhead costs as a percentage from the total project price.
Improving Web Page Readability by Plain Language
Venue: arXiv cs.HC 2011
Year: 2011

In today's world anybody who wants to access any information the first choice is to use the web because it is the only source to provide easy and instant access to information. However web readers face many hurdles from web which includes load of web pages, text size, finding related information, spelling and grammar etc. However understanding of web pages written in English language creates great problems for non native readers who have basic knowledge of English. In this paper, we propose a plain language for a local language (Urdu) using English alphabets for web pages in Pakistan. For this purpose we developed two websites, one with a normal English fonts and other in a local language text scheme using English alphabets. We also conducted a questionnaire from 40 different users with a different level of English language fluency in Pakistan to gain the evidence of the practicality of our approach. The result shows that the proposed plain language text scheme using English alphabets improved the reading comprehension for non native English speakers in Pakistan.
Predicting growth fluctuation in network economy
Venue: arXiv cs.AI 2011
Year: 2011

This study presents a method to predict the growth fluctuation of firms interdependent in a network economy. The risk of downward growth fluctuation of firms is calculated from the statistics on Japanese industry.
Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks
Venue: arXiv cs.AI 2011
Year: 2011

This paper discusses a system that accelerates reinforcement learning by using transfer from related tasks. Without such transfer, even if two tasks are very similar at some abstract level, an extensive re-learning effort is required. The system achieves much of its power by transferring parts of previously learned solutions rather than a single complete solution. The system exploits strong features in the multi-dimensional function produced by reinforcement learning in solving a particular task. These features are stable and easy to recognize early in the learning process. They generate a partitioning of the state space and thus the function. The partition is represented as a graph. This is used to index and compose functions stored in a case base to form a close approximation to the solution of the new task. Experiments demonstrate that function composition often produces more than an order of magnitude increase in learning rate compared to a basic reinforcement learning algorithm.
Inducing Interpretable Voting Classifiers without Trading Accuracy for Simplicity: Theoretical Results, Approximation Algorithms
Venue: arXiv cs.AI 2011
Year: 2011

Recent advances in the study of voting classification algorithms have brought empirical and theoretical results clearly showing the discrimination power of ensemble classifiers. It has been previously argued that the search of this classification power in the design of the algorithms has marginalized the need to obtain interpretable classifiers. Therefore, the question of whether one might have to dispense with interpretability in order to keep classification strength is being raised in a growing number of machine learning or data mining papers. The purpose of this paper is to study both theoretically and empirically the problem. First, we provide numerous results giving insight into the hardness of the simplicity-accuracy tradeoff for voting classifiers. Then we provide an efficient "top-down and prune" induction heuristic, WIDC, mainly derived from recent results on the weak learning and boosting frameworks. It is to our knowledge the first attempt to build a voting classifier as a base formula using the weak learning framework (the one which was previously highly successful for decision tree induction), and not the strong learning framework (as usual for such classifiers with boosting-like approaches). While it uses a well-known induction scheme previously successful in other classes of concept representations, thus making it easy to implement and compare, WIDC also relies on recent or new results we give about particular cases of boosting known as partition boosting and ranking loss boosting. Experimental results on thirty-one domains, most of which readily available, tend to display the ability of WIDC to produce small, accurate, and interpretable decision committees.
Collective Intelligence, Data Routing and Braess' Paradox
Venue: arXiv cs.AI 2011
Year: 2011

We consider the problem of designing the the utility functions of the utility-maximizing agents in a multi-agent system so that they work synergistically to maximize a global utility. The particular problem domain we explore is the control of network routing by placing agents on all the routers in the network. Conventional approaches to this task have the agents all use the Ideal Shortest Path routing Algorithm (ISPA). We demonstrate that in many cases, due to the side-effects of one agent's actions on another agent's performance, having agents use ISPA's is suboptimal as far as global aggregate cost is concerned, even when they are only used to route infinitesimally small amounts of traffic. The utility functions of the individual agents are not "aligned" with the global utility, intuitively speaking. As a particular example of this we present an instance of Braess' paradox in which adding new links to a network whose agents all use the ISPA results in a decrease in overall throughput. We also demonstrate that load-balancing, in which the agents' decisions are collectively made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to 'side-effects', in this case of current routing decision on future traffic. The mathematics of Collective Intelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects in multi-agent systems, both over time and space. We present key concepts from that mathematics and use them to derive an algorithm whose ideal version should have better performance than that of having all agents use the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated via empirical means (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm almost always avoids Braess' paradox.
Intelligent decision: towards interpreting the Pe Algorithm
Venue: arXiv cs.AI 2011
Year: 2011

The human intelligence lies in the algorithm, the nature of algorithm lies in the classification, and the classification is equal to outlier detection. A lot of algorithms have been proposed to detect outliers, meanwhile a lot of definitions. Unsatisfying point is that definitions seem vague, which makes the solution an ad hoc one. We analyzed the nature of outliers, and give two clear definitions. We then develop an efficient RDD algorithm, which converts outlier problem to pattern and degree problem. Furthermore, a collapse mechanism was introduced by IIR algorithm, which can be united seamlessly with the RDD algorithm and serve for the final decision. Both algorithms are originated from the study on general AI. The combined edition is named as Pe algorithm, which is the basis of the intelligent decision. Here we introduce longest k-turn subsequence problem and corresponding solution as an example to interpret the function of Pe algorithm in detecting curve-type outliers. We also give a comparison between IIR algorithm and Pe algorithm, where we can get a better understanding at both algorithms. A short discussion about intelligence is added to demonstrate the function of the Pe algorithm. Related experimental results indicate its robustness.