OpenRaiser/Intern-Atlas huggingface dataset:
Mechanical generation of networks with surplus complexity
Venue: arXiv cs.IT 2014
Year: 2014

In previous work I examined an information based complexity measure of networks with weighted links. The measure was compared with that obtained from by randomly shuffling the original network, forming an Erdos-Renyi random network preserving the original link weight distribution. It was found that real world networks almost invariably had higher complexity than their shuffled counterparts, whereas networks mechanically generated via preferential attachment did not. The same experiment was performed on foodwebs generated by an artificial life system, Tierra, and a couple of evolutionary ecology systems, EcoLab and WebWorld. These latter systems often exhibited the same complexity excess shown by real world networks, suggesting that the complexity surplus indicates the presence of evolutionary dynamics. In this paper, I report on a mechanical network generation system that does produce this complexity surplus. The heart of the idea is to construct the network of state transitions of a chaotic dynamical system, such as the Lorenz equation. This indicates that complexity surplus is a more fundamental trait than that of being an evolutionary system.
Choreographies and Behavioural Contracts on the Way to Dynamic Updates
Venue: arXiv cs.LO 2014
Year: 2014

We survey our work on choreographies and behavioural contracts in multiparty interactions. In particular theories of behavioural contracts are presented which enable reasoning about correct service composition (contract compliance) and service substitutability (contract refinement preorder) under different assumptions concerning service communication: synchronous address or name based communication with patient non-preemptable or impatient invocations, or asynchronous communication. Correspondingly relations between behavioural contracts and choreographic descriptions are considered, where a contract for each communicating party is, e.g., derived by projection. The considered relations are induced as the maximal preoders which preserve contract compliance and global traces: we show maximality to hold (permitting services to be discovered/substituted independently for each party) when contract refinement preorders with all the above asymmetric communication means are considered and, instead, not to hold if the standard symmetric CCS/pi-calculus communication is considered (or when directly relating choreographies to behavioral contracts via a preorder, no matter the communication mean). The obtained maximal preorders are then characterized in terms of a new form of testing, called compliance testing, where not only tests must succeed but also the system under test (thus relating to controllability theory), and compared with classical preorders such as may/must testing, trace inclusion, etc. Finally, recent work about adaptable choreographies and behavioural contracts is presented, where the theory above is extended to update mechanisms allowing choreographies/contracts to be modified at run-time by internal (self-adaptation) or external intervention.
An Approach to Model Checking of Multi-agent Data Analysis
Venue: arXiv cs.AI 2014
Year: 2014

The paper presents an approach to verification of a multi-agent data analysis algorithm. We base correct simulation of the multi-agent system by a finite integer model. For verification we use model checking tool SPIN. Protocols of agents are written in Promela language and properties of the multi-agent data analysis system are expressed in logic LTL. We run several experiments with SPIN and the model.
Automated user documentation generation based on the Eclipse application model
Venue: arXiv cs.SE 2014
Year: 2014

An application's user documentation, also referred to as the user manual, is one of the core elements required in application distribution. While there exist many tools to aid an application's developer in creating and maintaining documentation on and for the code itself, there are no tools that complement code development with user documentation for modern graphical applications. Approaches like literate programming are not applicable to this scenario, as not a library, but a full application is to be documented to an end-user. Documentation generation on applications up to now was only partially feasible due to the gap between the code and its semantics. The new generation of Eclipse rich client platform developed applications is based on an application model, closing a broad semantic gap between code and visible interface. We use this application model to provide a semantic description for the contained elements. Combined with the internal relationships of the application model, these semantic descriptions are aggregated to well-structured user documentations that comply to the ISO/IEC 26514. This paper delivers a report on the Ecrit research project, where the potentials and limitations of user documentation generation based on the Eclipse application model were investigated.
Optimal Cost Almost-sure Reachability in POMDPs
Venue: arXiv cs.AI 2014
Year: 2014

We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objective we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present approximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst-case running time of our algorithm is double exponential, we also present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples of interest.
Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games
Venue: arXiv cs.AI 2014
Year: 2014

Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player~$1$ in a two-player board game, given rules of the board game, the desired number of steps required for player~$1$ to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like $4 \times 4$ Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased.
Deep Belief Network Training Improvement Using Elite Samples Minimizing Free Energy
Venue: arXiv cs.LG 2014
Year: 2014

Nowadays this is very popular to use deep architectures in machine learning. Deep Belief Networks (DBNs) are deep architectures that use stack of Restricted Boltzmann Machines (RBM) to create a powerful generative model using training data. In this paper we present an improvement in a common method that is usually used in training of RBMs. The new method uses free energy as a criterion to obtain elite samples from generative model. We argue that these samples can more accurately compute gradient of log probability of training data. According to the results, an error rate of 0.99% was achieved on MNIST test set. This result shows that the proposed method outperforms the method presented in the first paper introducing DBN (1.25% error rate) and general classification methods such as SVM (1.4% error rate) and KNN (with 1.6% error rate). In another test using ISOLET dataset, letter classification error dropped to 3.59% compared to 5.59% error rate achieved in those papers using this dataset. The implemented method is available online at "http://ceit.aut.ac.ir/~keyvanrad/DeeBNet Toolbox.html".
Anisotropic Agglomerative Adaptive Mean-Shift
Venue: arXiv cs.CV 2014
Year: 2014

Mean Shift today, is widely used for mode detection and clustering. The technique though, is challenged in practice due to assumptions of isotropicity and homoscedasticity. We present an adaptive Mean Shift methodology that allows for full anisotropic clustering, through unsupervised local bandwidth selection. The bandwidth matrices evolve naturally, adapting locally through agglomeration, and in turn guiding further agglomeration. The online methodology is practical and effecive for low-dimensional feature spaces, preserving better detail and clustering salience. Additionally, conventional Mean Shift either critically depends on a per instance choice of bandwidth, or relies on offline methods which are inflexible and/or again data instance specific. The presented approach, due to its adaptive design, also alleviates this issue - with a default form performing generally well. The methodology though, allows for effective tuning of results.
Resolution of Difficult Pronouns Using the ROSS Method
Venue: arXiv cs.CL 2014
Year: 2014

A new natural language understanding method for disambiguation of difficult pronouns is described. Difficult pronouns are those pronouns for which a level of world or domain knowledge is needed in order to perform anaphoral or other types of resolution. Resolution of difficult pronouns may in some cases require a prior step involving the application of inference to a situation that is represented by the natural language text. A general method is described: it performs entity resolution and pronoun resolution. An extension to the general pronoun resolution method performs inference as an embedded commonsense reasoning method. The general method and the embedded method utilize features of the ROSS representational scheme; in particular the methods use ROSS ontology classes and the ROSS situation model. The overall method is a working solution that solves the following Winograd schemas: a) trophy and suitcase, b) person lifts person, c) person pays detective, and d) councilmen and demonstrators.
Towards Cross-Project Defect Prediction with Imbalanced Feature Sets
Venue: arXiv cs.SE 2014
Year: 2014

Cross-project defect prediction (CPDP) has been deemed as an emerging technology of software quality assurance, especially in new or inactive projects, and a few improved methods have been proposed to support better defect prediction. However, the regular CPDP always assumes that the features of training and test data are all identical. Hence, very little is known about whether the method for CPDP with imbalanced feature sets (CPDP-IFS) works well. Considering the diversity of defect data sets available on the Internet as well as the high cost of labeling data, to address the issue, in this paper we proposed a simple approach according to a distribution characteristic-based instance (object class) mapping, and demonstrated the validity of our method based on three public defect data sets (i.e., PROMISE, ReLink and AEEEM). Besides, the empirical results indicate that the hybrid model composed of CPDP and CPDP-IFS does improve the prediction performance of the regular CPDP to some extent.
Estimation of transient process for singularly perturbed synchronization system with distributed parameters
Venue: arXiv cs.SY 2014
Year: 2014

Many systems, arising in electrical and electronic engineering are based on controlled phase synchronization of several periodic processes ("phase synchronization" systems, or PSS). Typically such systems are featured by the gradient-like behavior, i.e. the system has infinite sequence of equilibria points, and any solution converges to one of them. This property however says nothing about the transient behavior of the system, whose important qualitative index is the maximal phase error. The synchronous regime of gradient-like system may be preceded by cycle slipping, i.e. the increase of the absolute phase error. Since the cycle slipping is considered to be undesired behavior of PSSs, it is important to find efficient estimates for the number of slipped cycles. In the present paper, we address the problem of cycle-slipping for phase synchronization systems described by integro-differential Volterra equations with a small parameter at the higher derivative. New effective estimates for a number of slipped cycles are obtained by means of Popov's method of "a priori integral indices". The estimates are uniform with respect to the small parameter.
Welfare Maximization with Production Costs: A Primal Dual Approach
Venue: arXiv cs.DS 2014
Year: 2014

We study online combinatorial auctions with production costs proposed by Blum et al. using the online primal dual framework. In this model, buyers arrive online, and the seller can produce multiple copies of each item subject to a non-decreasing marginal cost per copy. The goal is to allocate items to maximize social welfare less total production cost. For arbitrary (strictly convex and differentiable) production cost functions, we characterize the optimal competitive ratio achievable by online mechanisms/algorithms. We show that online posted pricing mechanisms, which are incentive compatible, can achieve competitive ratios arbitrarily close to the optimal, and construct lower bound instances on which no online algorithms, not necessarily incentive compatible, can do better. Our positive results improve or match the results in several previous work, e.g., Bartal et al., Blum et al., and Buchbinder and Gonen. Our lower bounds apply to randomized algorithms and resolve an open problem by Buchbinder and Gonen.
Rabin-$p$ Cryptosystem: Practical and Efficient Method for Rabin based Encryption Scheme
Venue: arXiv cs.CR 2014
Year: 2014

In this work, we introduce a new, efficient and practical scheme based on the Rabin cryptosystem without using the Jacobi symbol, message redundancy technique or the needs of extra bits in order to specify the correct plaintext. Our system involves only a single prime number as the decryption key and does only one modular exponentiation. Consequently, this will practically reduce the computational efforts during decryption process. We demonstrate that the decryption is unique and proven to be equivalent to factoring.The scheme is performs better when compared to a number of Rabin cryptosystem variants.
Sequestration of Malevolent Anchor Nodes in Wireless Sensor Networks using Mahalanobis Distance
Venue: arXiv cs.NI 2014
Year: 2014

Discovering the malicious or vulnerable anchor node is an essential problem in wireless sensor networks (WSNs). In wireless sensor networks, anchor nodes are the nodes that know its current location. Neighbouring nodes or non-anchor nodes calculate its location coordinate (or location reference) with the help of anchor nodes. Ingenuous localization is not possible in the presence of a cheating anchor node or a cheating node. Nowadays, its a challenging task to identify the cheating anchor node or cheating node in a network. Even after finding out the location of the cheating anchor node, there is no assurance, that the identified node is legitimate or not. This paper aims to localize the cheating anchor nodes using trilateration algorithm and later associate it with Mahalanobis distance to obtain maximum accuracy in detecting malicious or cheating anchor nodes during localization. We were able to attain a considerable reduction in the error achieved during localization. For implementation purpose, we simulated our scheme using ns3 network simulator.
Dynamic Facility Location via Exponential Clocks
Venue: arXiv cs.DS 2014
Year: 2014

The \emph{dynamic facility location problem} is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance metric between clients and facilities changes over time. This leads to a trade-off between optimizing the classic objective function and the "stability" of the solution: there is a switching cost charged every time a client changes the facility to which it is connected. While the standard linear program (LP) relaxation for the classic problem naturally extends to this problem, traditional LP-rounding techniques do not, as they are often sensitive to small changes in the metric resulting in frequent switches. We present a new LP-rounding algorithm for facility location problems, which yields the first constant approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on the clients and facilities, and connect every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use \emph{no clustering} and we allow clients to connect through paths of \emph{arbitrary lengths}. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem.
A Note on Systematic Conflict Generation in CA-EN-type Causal Structures
Venue: arXiv cs.AI 2014
Year: 2014

This paper is aimed at providing a very first, more "global", systematic point of view with respect to possible conflict generation in CA-EN-like causal structures. For simplicity, only the outermost level of graphs is taken into account. Localization of the "conflict area", diagnostic preferences, and bases for systematic conflict generation are considered. A notion of {\em Potential Conflict Structure} ({\em PCS}) constituting a basic tool for identification of possible conflicts is proposed and its use is discussed.
On the Security of Fully Homomorphic Encryption and Encrypted Computing: Is Division safe?
Venue: arXiv cs.CR 2014
Year: 2014

Since fully homomorphic encryption and homomorphically encrypted computing preserve algebraic identities such as 2*2=2+2, a natural question is whether this extremely utilitarian feature also sets up cryptographic attacks that use the encrypted arithmetic operators to generate or identify the encryptions of known constants. In particular, software or hardware might use encrypted addition and multiplication to do encrypted division and deliver the encryption of x/x=1. That can then be used to generate 1+1=2, etc, until a complete codebook is obtained. This paper shows that there is no formula or computation using 32-bit multiplication x*y and three-input addition x+y+z that yields a known constant from unknown inputs. We characterise what operations are similarly `safe' alone or in company, and show that 32-bit division is not safe in this sense, but there are trivial modifications that make it so.
Approximation Schemes for Binary Quadratic Programming Problems with Low cp-Rank Decompositions
Venue: arXiv cs.DS 2014
Year: 2014

Binary quadratic programming problems have attracted much attention in the last few decades due to their potential applications. This type of problems are NP-hard in general, and still considered a challenge in the design of efficient approximation algorithms for their solutions. The purpose of this paper is to investigate the approximability for a class of such problems where the constraint matrices are {\it completely positive} and have low {\it cp-rank}. In the first part of the paper, we show that a completely positive rational factorization of such matrices can be computed in polynomial time, within any desired accuracy. We next consider binary quadratic programming problems of the following form: Given matrices $Q_1,...,Q_n\in\mathbb{R}_+^{n\times n}$, and a system of $m$ constrains $x^TQ_ix\le C_i^2$ ($x^TQ_ix\ge C_i^2$), $i=1,...,m$, we seek to find a vector $x^*\in \{0,1\}^n$ that maximizes (minimizes) a given function $f$. This class of problems generalizes many fundamental problems in discrete optimization such as packing and covering integer programs/knapsack problems, quadratic knapsack problems, submodular maximization, etc. We consider the case when $m$ and the cp-ranks of the matrices $Q_i$ are bounded by a constant. Our approximation results for the maximization problem are as follows. For the case when the objective function is nonnegative submodular, we give an $(1/4-ε)$-approximation algorithm, for any $ε>0$; when the function $f$ is linear, we present a PTAS. We next extend our PTAS result to a wider class of non-linear objective functions including quadratic functions, multiplicative functions, and sum-of-ratio functions. The minimization problem seems to be much harder due to the fact that the relaxation is {\it not} convex. For this case, we give a QPTAS for $m=1$.
Security in Monitoring Schemes: A Survey
Venue: arXiv cs.DC 2014
Year: 2014

With our growing reliability on distributed networks, the security aspect of such networks becomes of prime importance. In large scale distributed networks it becomes cardinal to have an efficient and effective monitoring scheme. The monitoring schemes supervise the node behaviour in the network and look out for any discrepancy. Monitoring schemes comprise of monitoring components that work together to help schemes in meeting various security requirement parameters for the networks. These security parameters are breached via various attacks by manipulation of monitoring components of particular monitoring schemes to produce faulty results and thereby reducing efficiency of networks, reliability and security. In this paper we have discussed these components of monitoring, multiple monitoring schemes, their security parameters and various types of attacks possible on these monitoring components by manipulating assumptions of monitoring schemes.
Incentivizing Spectrum Sharing via Subsidy Regulations
Venue: arXiv cs.NI 2014
Year: 2014

Traditional regulatory methods for spectrum licensing have been recently identified as one of the causes for the under-utilization of the valuable radio spectrum. Governmental agencies such as the Federal Communications Commission (FCC) are seeking ways to remove stringent regulatory barriers and facilitate broader access to the spectrum resources. The goal is to allow for an improved and ubiquitous sharing of the precious radio spectrum between commercial service providers. In this paper, we propose a novel noncooperative game theoretic approach, to show how to foster more sharing of the radio spectrum via the use of regulatory power. We define a two stage game in which the government regulators move first, followed by the providers. The providers are incentivized by lower spectrum allocation fees from the regulators in return for proof-of-sharing. The providers are offered discounted spectrum bands, potentially at different locations, but will be asked to provide coverage to users that are not subscribed to them so as to maintain their subsidy incentives from the government. In a simplification of the model, analytical expressions for the providers' perfect equilibrium strategies are derived, and we argue for the existence of the government's part of a perfect equilibrium. Our analysis shows that through subsidization, the government can provide small service providers a fair chance to compete with the large providers, thereby avoiding monopolization in the market.