OpenRaiser/Intern-Atlas huggingface dataset:
Work in Progress: Enabling robot device discovery through robot device descriptions
Venue: arXiv cs.RO 2013
Year: 2013

There is no dearth of new robots that provide both generalized and customized platforms for learning and research. Unfortunately as we attempt to adapt existing software components, we are faced with an explosion of device drivers that interface each hardware platform with existing frameworks. We certainly gain the efficiencies of reusing algorithms and tools developed across platforms but only once the device driver is created. We propose a domain specific language that describes the development and runtime interface of a robot and defines its link to existing frameworks. The Robot Device Interface Specification (RDIS) takes advantage of the internal firmware present on many existing devices by defining the communication mechanism, syntax and semantics in such a way to enable the generation of automatic interface links and resource discovery. We present the current domain model as it relates to differential drive robots as a mechanism to use the RDIS to link described robots to HTML5 via web sockets and ROS (Robot Operating System).
A decomposition method with minimum communication amount for parallelization of multi-dimensional FFTs
Venue: arXiv cs.NA 2013
Year: 2013

The fast Fourier transform (FFT) is undoubtedly an essential primitive that has been applied in various fields of science and engineering. In this paper, we present a decomposition method for parallelization of multi-dimensional FFTs with smallest communication amount for all ranges of the number of processes compared to previously proposed methods. This is achieved by two distinguishing features: adaptive decomposition and transpose order awareness. In the proposed method, the FFT data are decomposed based on a row-wise basis that maps the multi-dimensional data into one-dimensional data, and translates the corresponding coordinates from multi-dimensions into one-dimension so that the resultant one-dimensional data can be divided and allocated equally to the processes. As a result, differently from previous works that have the dimensions of decomposition pre-defined, our method can adaptively decompose the FFT data on the lowest possible dimensions depending on the number of processes. In addition, this row-wise decomposition provides plenty of alternatives in data transpose, and different transpose order results in different amount of communication. We identify the best transpose orders with smallest communication amounts for the 3-D, 4-D, and 5-D FFTs by analyzing all possible cases. Given both communication efficiency and scalability, our method is promising in development of highly efficient parallel packages for the FFT.
Modification of conceptual clustering algorithm Cobweb for numerical data using fuzzy membership function
Venue: arXiv cs.AI 2013
Year: 2013

Modification of a conceptual clustering algorithm Cobweb for the purpose of its application for numerical data is offered. Keywords: clustering, algorithm Cobweb, numerical data, fuzzy membership function.
Tight Bounds for Rumor Spreading with Vertex Expansion
Venue: arXiv cs.DM 2013
Year: 2013

We establish a bound for the classic PUSH-PULL rumor spreading protocol on arbitrary graphs, in terms of the vertex expansion of the graph. We show that O(log^2(n)/α) rounds suffice with high probability to spread a rumor from a single node to all n nodes, in any graph with vertex expansion at least α. This bound matches the known lower bound, and settles the question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.
Cloud Forensics: A Meta-Study of Challenges, Approaches, and Open Problems
Venue: arXiv cs.DC 2013
Year: 2013

In recent years, cloud computing has become popular as a cost-effective and efficient computing paradigm. Unfortunately, today's cloud computing architectures are not designed for security and forensics. To date, very little research has been done to develop the theory and practice of cloud forensics. Many factors complicate forensic investigations in a cloud environment. First, the storage system is no longer local. Therefore, even with a subpoena, law enforcement agents cannot confiscate the suspect's computer and get access to the suspect's files. Second, each cloud server contains files from many users. Hence, it is not feasible to seize servers from a data center without violating the privacy of many other users. Third, even if the data belonging to a particular suspect is identified, separating it from other users' data is difficult. Moreover, other than the cloud provider's word, there is usually no evidence that links a given data file to a particular suspect. For such challenges, clouds cannot be used to store healthcare, business, or national security related data, which require audit and regulatory compliance. In this paper, we systematically examine the cloud forensics problem and explore the challenges and issues in cloud forensics. We then discuss existing research projects and finally, we highlight the open problems and future directions in cloud forensics research area. We posit that our systematic approach towards understanding the nature and challenges of cloud forensics will allow us to examine possible secure solution approaches, leading to increased trust on and adoption of cloud computing, especially in business, healthcare, and national security. This in turn will lead to lower cost and long-term benefit to our society as a whole.
Rate-Distortion Bounds for an Epsilon-Insensitive Distortion Measure
Venue: arXiv cs.IT 2013
Year: 2013

Direct evaluation of the rate-distortion function has rarely been achieved when it is strictly greater than its Shannon lower bound. In this paper, we consider the rate-distortion function for the distortion measure defined by an epsilon-insensitive loss function. We first present the Shannon lower bound applicable to any source distribution with finite differential entropy. Then, focusing on the Laplacian and Gaussian sources, we prove that the rate-distortion functions of these sources are strictly greater than their Shannon lower bounds and obtain analytically evaluable upper bounds for the rate-distortion functions. Small distortion limit and numerical evaluation of the bounds suggest that the Shannon lower bound provides a good approximation to the rate-distortion function for the epsilon-insensitive distortion measure.
Variant-Frequency Semantics for Green Futures
Venue: arXiv cs.PL 2013
Year: 2013

This paper describes an operational semantics for futures, with the primary target on energy efficiency. The work in progress is built around an insight that different threads can coordinate by running at different "paces," so that the time for synchronization and the resulting wasteful energy consumption can be reduced. We exploit several inherent characteristics of futures to determine how the paces of involving threads can be coordinated. The semantics is inspired by recent advances in computer architectures, where the frequencies of CPU cores can be adjusted dynamically. The work is a first-step toward a direction where variant frequencies are directly modeled as an essential semantic feature in concurrent programming languages.
Non-simplifying Graph Rewriting Termination
Venue: arXiv cs.CL 2013
Year: 2013

So far, a very large amount of work in Natural Language Processing (NLP) rely on trees as the core mathematical structure to represent linguistic informations (e.g. in Chomsky's work). However, some linguistic phenomena do not cope properly with trees. In a former paper, we showed the benefit of encoding linguistic structures by graphs and of using graph rewriting rules to compute on those structures. Justified by some linguistic considerations, graph rewriting is characterized by two features: first, there is no node creation along computations and second, there are non-local edge modifications. Under these hypotheses, we show that uniform termination is undecidable and that non-uniform termination is decidable. We describe two termination techniques based on weights and we give complexity bound on the derivation length for these rewriting system.
URDP: General Framework for Direct CCA2 Security from any Lattice-Based PKE Scheme
Venue: arXiv cs.CR 2013
Year: 2013

Design efficient lattice-based cryptosystem secure against adaptive chosen ciphertext attack (IND-CCA2) is a challenge problem. To the date, full CCA2-security of all proposed lattice-based PKE schemes achieved by using a generic transformations such as either strongly unforgeable one-time signature schemes (SU-OT-SS), or a message authentication code (MAC) and weak form of commitment. The drawback of these schemes is that encryption requires "separate encryption". Therefore, the resulting encryption scheme is not sufficiently efficient to be used in practice and it is inappropriate for many applications such as small ubiquitous computing devices with limited resources such as smart cards, active RFID tags, wireless sensor networks and other embedded devices. In this work, for the first time, we introduce an efficient universal random data padding (URDP) scheme, and show how it can be used to construct a "direct" CCA2-secure encryption scheme from "any" worst-case hardness problems in (ideal) lattice in the standard model, resolving a problem that has remained open till date. This novel approach is a "black-box" construction and leads to the elimination of separate encryption, as it avoids using general transformation from CPA-secure scheme to a CCA2-secure one. IND-CCA2 security of this scheme can be tightly reduced in the standard model to the assumption that the underlying primitive is an one-way trapdoor function.
Inconsistencies of the Highly-Cited-Publications Indicator
Venue: arXiv cs.DL 2013
Year: 2013

One way of evaluating individual scientists is the determination of the number of highly cited publications, where the threshold is given by a large reference set. It is shown that this indicator behaves in a counterintuitive way, leading to inconsistencies in the ranking of different scientists.
How much do different ways of calculating percentiles influence the derived performance indicators? - A case study
Venue: arXiv cs.DL 2013
Year: 2013

Bibliometric indicators can be determined by comparing specific citation records with the percentiles of a reference set. However, there exists an ambiguity in the computation of percentiles because usually a significant number of papers with the same citation count are found at the border between percentile rank classes. The present case study of the citations to the journal Europhysics Letters (EPL) in comparison with all physics papers from the Web of Science shows the deviations which occur due to the different ways of treating the tied papers in the evaluation of the percentage of highly cited publications. A strong bias can occur, if the papers tied at the threshold number of citations are all considered as highly cited or all considered as not highly cited.
An implementation of CAD in Maple utilising McCallum projection
Venue: arXiv cs.SC 2013
Year: 2013

Cylindrical algebraic decomposition (CAD) is an important tool for the investigation of semi-algebraic sets. Originally introduced by Collins in the 1970s for use in quantifier elimination it has since found numerous applications within algebraic geometry and beyond. Following from his original work in 1988, McCallum presented an improved algorithm, CADW, which offered a huge increase in the practical utility of CAD. In 2009 a team based at the University of Western Ontario presented a new and quite separate algorithm for CAD, which was implemented and included in the computer algebra system Maple. As part of a wider project at Bath investigating CAD and its applications, Collins and McCallum's CAD algorithms have been implemented in Maple. This report details these implementations and compares them to Qepcad and the Ontario algorithm. The implementations were originally undertaken to facilitate research into the connections between the algorithms. However, the ability of the code to guarantee order-invariant output has led to its use in new research on CADs which are minimal for certain problems. In addition, the implementation described here is of interest as the only full implementation of CADW, (since Qepcad does not currently make use of McCallum's delineating polynomials), and hence can solve problems not admissible to other CAD implementations.
Matrix Access structure Policy used in Attribute-Based Proxy Re-encryption
Venue: arXiv cs.CR 2013
Year: 2013

Proxy re-encryption (PRE) allows a semi-trusted proxy to convert a ciphertext originally intended for Alice into an encryption of the same message intended for Bob. Song Luo, Jianbin Hu, and Zhong Chen presented a novel ciphertext policy attribute-based proxy re-encryption (CP-AB-PRE) scheme. The ciphertext policy realized in their scheme is AND-gates policy supporting multi-value attributes, negative attributes and wildcards. We propose a new access policies based on LSSS matrix access structures. Our scheme still have the properties of both PRE and CP-AB-PRE, such as unidirectionality, non-interactivity, multi-use, allows the encryptor to decide whether the ciphertext can be re-encrypted and allows the proxy to add access policy. Furthermore, our scheme can be modified to outsource the policy of W2.
A Modelling Approach Based on Fuzzy Agents
Venue: arXiv cs.AI 2013
Year: 2013

Modelling of complex systems is mainly based on the decomposition of these systems in autonomous elements, and the identification and definitio9n of possible interactions between these elements. For this, the agent-based approach is a modelling solution often proposed. Complexity can also be due to external events or internal to systems, whose main characteristics are uncertainty, imprecision, or whose perception is subjective (i.e. interpreted). Insofar as fuzzy logic provides a solution for modelling uncertainty, the concept of fuzzy agent can model both the complexity and uncertainty. This paper focuses on introducing the concept of fuzzy agent: a classical architecture of agent is redefined according to a fuzzy perspective. A pedagogical illustration of fuzzy agentification of a smart watering system is then proposed.
On Sharing Private Data with Multiple Non-Colluding Adversaries
Venue: arXiv cs.DB 2013
Year: 2013

We present SPARSI, a theoretical framework for partitioning sensitive data across multiple non-colluding adversaries. Most work in privacy-aware data sharing has considered disclosing summaries where the aggregate information about the data is preserved, but sensitive user information is protected. Nonetheless, there are applications, including online advertising, cloud computing and crowdsourcing markets, where detailed and fine-grained user-data must be disclosed. We consider a new data sharing paradigm and introduce the problem of privacy-aware data partitioning, where a sensitive dataset must be partitioned among k untrusted parties (adversaries). The goal is to maximize the utility derived by partitioning and distributing the dataset, while minimizing the amount of sensitive information disclosed. The data should be distributed so that an adversary, without colluding with other adversaries, cannot draw additional inferences about the private information, by linking together multiple pieces of information released to her. The assumption of no collusion is both reasonable and necessary in the above application domains that require release of private user information. SPARSI enables us to formally define privacy-aware data partitioning using the notion of sensitive properties for modeling private information and a hypergraph representation for describing the interdependencies between data entries and private information. We show that solving privacy-aware partitioning is, in general, NP-hard, but for specific information disclosure functions, good approximate solutions can be found using relaxation techniques. Finally, we present a local search algorithm applicable to generic information disclosure functions. We apply SPARSI together with the proposed algorithms on data from a real advertising scenario and show that we can partition data with no disclosure to any single advertiser.
Finding the Right Set of Users: Generalized Constraints for Group Recommendations
Venue: arXiv cs.IR 2013
Year: 2013

Recently, group recommendations have attracted considerable attention. Rather than recommending items to individual users, group recommenders recommend items to groups of users. In this position paper, we introduce the problem of forming an appropriate group of users to recommend an item when constraints apply to the members of the group. We present a formal model of the problem and an algorithm for its solution. Finally, we identify several directions for future work.
Finding overlapping communities in networks using evolutionary method
Venue: arXiv cs.SI 2013
Year: 2013

Community structure is a typical property of many real-world networks, and has become a key to understand the dynamics of the networked systems. In these networks most nodes apparently lie in a community while there often exists a few nodes straddling several communities. An ideal algorithm for community detection is preferable which can identify the overlapping communities in such networks. To represent an overlapping division we develop a encoding schema composed of two segments, the first one represents a disjoint partition and the second one represents a extension of the partition that allows of multiple memberships. We give a measure for the informativeness of a node, and present an evolutionary method for detecting the overlapping communities in a network.
Exploratory Model Building
Venue: arXiv cs.AI 2013
Year: 2013

Some instances of creative thinking require an agent to build and test hypothetical theories. Such a reasoner needs to explore the space of not only those situations that have occurred in the past, but also those that are rationally conceivable. In this paper we present a formalism for exploring the space of conceivable situation-models for those domains in which the knowledge is primarily probabilistic in nature. The formalism seeks to construct consistent, minimal, and desirable situation-descriptions by selecting suitable domain-attributes and dependency relationships from the available domain knowledge.
A Structured, Probabilistic Representation of Action
Venue: arXiv cs.AI 2013
Year: 2013

When agents devise plans for execution in the real world, they face two important forms of uncertainty: they can never have complete knowledge about the state of the world, and they do not have complete control, as the effects of their actions are uncertain. While most classical planning methods avoid explicit uncertainty reasoning, we believe that uncertainty should be explicitly represented and reasoned about. We develop a probabilistic representation for states and actions, based on belief networks. We define conditional belief nets (CBNs) to capture the probabilistic dependency of the effects of an action upon the state of the world. We also use a CBN to represent the intrinsic relationships among entities in the environment, which persist from state to state. We present a simple projection algorithm to construct the belief network of the state succeeding an action, using the environment CBN model to infer indirect effects. We discuss how the qualitative aspects of belief networks and CBNs make them appropriate for the various stages of the problem solving process, from model construction to the design of planning algorithms.
Abstracting Probabilistic Actions
Venue: arXiv cs.AI 2013
Year: 2013

This paper discusses the problem of abstracting conditional probabilistic actions. We identify two distinct types of abstraction: intra-action abstraction and inter-action abstraction. We define what it means for the abstraction of an action to be correct and then derive two methods of intra-action abstraction and two methods of inter-action abstraction which are correct according to this criterion. We illustrate the developed techniques by applying them to actions described with the temporal action representation used in the DRIPS decision-theoretic planner and we describe how the planner uses abstraction to reduce the complexity of planning.
From Influence Diagrams to Junction Trees
Venue: arXiv cs.AI 2013
Year: 2013

We present an approach to the solution of decision problems formulated as influence diagrams. This approach involves a special triangulation of the underlying graph, the construction of a junction tree with special properties, and a message passing algorithm operating on the junction tree for computation of expected utilities and optimal decision policies.
Using New Data to Refine a Bayesian Network
Venue: arXiv cs.AI 2013
Year: 2013

We explore the issue of refining an existent Bayesian network structure using new data which might mention only a subset of the variables. Most previous works have only considered the refinement of the network's conditional probability parameters, and have not addressed the issue of refining the network's structure. We develop a new approach for refining the network's structure. Our approach is based on the Minimal Description Length (MDL) principle, and it employs an adapted version of a Bayesian network learning algorithm developed in our previous work. One of the adaptations required is to modify the previous algorithm to account for the structure of the existent network. The learning algorithm generates a partial network structure which can then be used to improve the existent network. We also present experimental evidence demonstrating the effectiveness of our approach.
Constructing Belief Networks to Evaluate Plans
Venue: arXiv cs.AI 2013
Year: 2013

This paper examines the problem of constructing belief networks to evaluate plans produced by an knowledge-based planner. Techniques are presented for handling various types of complicating plan features. These include plans with context-dependent consequences, indirect consequences, actions with preconditions that must be true during the execution of an action, contingencies, multiple levels of abstraction multiple execution agents with partially-ordered and temporally overlapping actions, and plans which reference specific times and time durations.
Anytime Decision Making with Imprecise Probabilities
Venue: arXiv cs.AI 2013
Year: 2013

This paper examines methods of decision making that are able to accommodate limitations on both the form in which uncertainty pertaining to a decision problem can be realistically represented and the amount of computing time available before a decision must be made. The methods are anytime algorithms in the sense of Boddy and Dean 1991. Techniques are presented for use with Frisch and Haddawy's [1992] anytime deduction system, with an anytime adaptation of Nilsson's [1986] probabilistic logic, and with a probabilistic database model.
Solving Asymmetric Decision Problems with Influence Diagrams
Venue: arXiv cs.AI 2013
Year: 2013

While influence diagrams have many advantages as a representation framework for Bayesian decision problems, they have a serious drawback in handling asymmetric decision problems. To be represented in an influence diagram, an asymmetric decision problem must be symmetrized. A considerable amount of unnecessary computation may be involved when a symmetrized influence diagram is evaluated by conventional algorithms. In this paper we present an approach for avoiding such unnecessary computation in influence diagram evaluation.