OpenRaiser/Intern-Atlas huggingface dataset:
On the Tractability of Minimal Model Computation for Some CNF Theories
Venue: arXiv cs.AI 2013
Year: 2013

Designing algorithms capable of efficiently constructing minimal models of CNFs is an important task in AI. This paper provides new results along this research line and presents new algorithms for performing minimal model finding and checking over positive propositional CNFs and model minimization over propositional CNFs. An algorithmic schema, called the Generalized Elimination Algorithm (GEA) is presented, that computes a minimal model of any positive CNF. The schema generalizes the Elimination Algorithm (EA) [BP97], which computes a minimal model of positive head-cycle-free (HCF) CNF theories. While the EA always runs in polynomial time in the size of the input HCF CNF, the complexity of the GEA depends on the complexity of the specific eliminating operator invoked therein, which may in general turn out to be exponential. Therefore, a specific eliminating operator is defined by which the GEA computes, in polynomial time, a minimal model for a class of CNF that strictly includes head-elementary-set-free (HEF) CNF theories [GLL06], which form, in their turn, a strict superset of HCF theories. Furthermore, in order to deal with the high complexity associated with recognizing HEF theories, an "incomplete" variant of the GEA (called IGEA) is proposed: the resulting schema, once instantiated with an appropriate elimination operator, always constructs a model of the input CNF, which is guaranteed to be minimal if the input theory is HEF. In the light of the above results, the main contribution of this work is the enlargement of the tractability frontier for the minimal model finding and checking and the model minimization problems.
Finding Alternate Paths in the Internet:A Survey of Techniques for End-to-End Path Discovery
Venue: arXiv cs.NI 2013
Year: 2013

The Internet provides physical path diversity between a large number of hosts, making it possible for networks to use alternative paths when one path fails to deliver the required Quality of Service. However, for various reasons, many established protocols (e.g. de facto Internet inter-domain routing protocol, Border-Gateway Protocol - BGP) do not fully exploit such alternate paths. This paper surveys research into techniques for discovering end-to-end alternate paths, including those based on monitoring path performance, choosing paths that are maximally disjoint, and in routing across multiple paths. It surveys proposals for making BGP better able to exploit multiple paths and how multi-homing can create alternate paths. It also describes how alternate paths can be realized through detour routing (application layer mechanisms) and routing deflections (network layer mechanisms). It also discusses Fast Re-Route techniques for construction of backup routes. It concludes by surveying open research issues into the discovery and use of alternate paths in the Internet.
Claw-free t-perfect graphs can be recognised in polynomial time
Venue: arXiv cs.DM 2013
Year: 2013

A graph is called t-perfect if its stable set polytope is defined by non-negativity, edge and odd-cycle inequalities. We show that it can be decided in polynomial time whether a given claw-free graph is t-perfect.
Sequencing and navigation through learning content
Venue: arXiv cs.CY 2013
Year: 2013

The aim of this paper is to describe a basic idea to introduce formal modeling in development and presentation of e-learning systems. By introducing formalism, reasoning on e-learning systems and processes through them can be more easily understood. In particular, we propose to use Harel automata (statecharts) in modeling sequencing and navigation through learning content and learning process.
Satisfiability Modulo ODEs
Venue: arXiv cs.LO 2013
Year: 2013

We study SMT problems over the reals containing ordinary differential equations. They are important for formal verification of realistic hybrid systems and embedded software. We develop delta-complete algorithms for SMT formulas that are purely existentially quantified, as well as exists-forall formulas whose universal quantification is restricted to the time variables. We demonstrate scalability of the algorithms, as implemented in our open-source solver dReal, on SMT benchmarks with several hundred nonlinear ODEs and variables.
Dimensions, Structures and Security of Networks
Venue: arXiv cs.SI 2013
Year: 2013

One of the main issues in modern network science is the phenomenon of cascading failures of a small number of attacks. Here we define the dimension of a network to be the maximal number of functions or features of nodes of the network. It was shown that there exist linear networks which are provably secure, where a network is linear, if it has dimension one, that the high dimensions of networks are the mechanisms of overlapping communities, that overlapping communities are obstacles for network security, and that there exists an algorithm to reduce high dimensional networks to low dimensional ones which simultaneously preserves all the network properties and significantly amplifies security of networks. Our results explore that dimension is a fundamental measure of networks, that there exist linear networks which are provably secure, that high dimensional networks are insecure, and that security of networks can be amplified by reducing dimensions.
Homophyly Networks -- A Structural Theory of Networks
Venue: arXiv cs.SI 2013
Year: 2013

A grand challenge in network science is apparently the missing of a structural theory of networks. The authors have showed that the existence of community structures is a universal phenomenon in real networks, and that neither randomness nor preferential attachment is a mechanism of community structures of network \footnote{A. Li, J. Li, and Y. Pan, Community structures are definable in networks, and universal in the real world, To appear.}. This poses a fundamental question: What are the mechanisms of community structures of real networks? Here we found that homophyly is the mechanism of community structures and a structural theory of networks. We proposed a homophyly model. It was shown that networks of our model satisfy a series of new topological, probabilistic and combinatorial principles, including a fundamental principle, a community structure principle, a degree priority principle, a widths principle, an inclusion and infection principle, a king node principle, and a predicting principle etc, leading to a structural theory of networks. Our model demonstrates that homophyly is the underlying mechanism of community structures of networks, that nodes of the same community share common features, that power law and small world property are never obstacles of the existence of community structures in networks, and that community structures are definable in networks.
All Linear-Time Congruences for Familiar Operators
Venue: arXiv cs.LO 2013
Year: 2013

The detailed behaviour of a system is often represented as a labelled transition system (LTS) and the abstract behaviour as a stuttering-insensitive semantic congruence. Numerous congruences have been presented in the literature. On the other hand, there have not been many results proving the absence of more congruences. This publication fully analyses the linear-time (in a well-defined sense) region with respect to action prefix, hiding, relational renaming, and parallel composition. It contains 40 congruences. They are built from the alphabet, two kinds of traces, two kinds of divergence traces, five kinds of failures, and four kinds of infinite traces. In the case of finite LTSs, infinite traces lose their role and the number of congruences drops to 20. The publication concentrates on the hardest and most novel part of the result, that is, proving the absence of more congruences.
Sparse Signal Recovery from Nonadaptive Linear Measurements
Venue: arXiv cs.IT 2013
Year: 2013

The theory of Compressed Sensing, the emerging sampling paradigm 'that goes against the common wisdom', asserts that 'one can recover signals in Rn from far fewer samples or measurements, if the signal has a sparse representation in some orthonormal basis', from m = O(klogn), k<< n nonadaptive measurements . The accuracy of the recovered signal is 'as good as that attainable with direct knowledge of the k most important coefficients and its locations'. Moreover, a good approximation to those important coefficients is extracted from the measurements by solving a L1 minimization problem viz. Basis Pursuit. 'The nonadaptive measurements have the character of random linear combinations of the basis/frame elements'. The theory has implications which are far reaching and immediately leads to a number of applications in Data Compression,Channel Coding and Data Acquisition. 'The last of these applications suggest that CS could have an enormous impact in areas where conventional hardware design has significant limitations', leading to 'efficient and revolutionary methods of data acquisition and storage in future'. The paper reviews fundamental mathematical ideas pertaining to compressed sensing viz. sparsity, incoherence, reduced isometry property and basis pursuit, exemplified by the sparse recovery of a speech signal and convergence of the L1- minimization algorithm.
Diffusion LMS for clustered multitask networks
Venue: arXiv cs.SY 2013
Year: 2013

Recent research works on distributed adaptive networks have intensively studied the case where the nodes estimate a common parameter vector collaboratively. However, there are many applications that are multitask-oriented in the sense that there are multiple parameter vectors that need to be inferred simultaneously. In this paper, we employ diffusion strategies to develop distributed algorithms that address clustered multitask problems by minimizing an appropriate mean-square error criterion with $\ell_2$-regularization. Some results on the mean-square stability and convergence of the algorithm are also provided. Simulations are conducted to illustrate the theoretical findings.
Parameterless Optimal Approximate Message Passing
Venue: arXiv cs.IT 2013
Year: 2013

Iterative thresholding algorithms are well-suited for high-dimensional problems in sparse recovery and compressive sensing. The performance of this class of algorithms depends heavily on the tuning of certain threshold parameters. In particular, both the final reconstruction error and the convergence rate of the algorithm crucially rely on how the threshold parameter is set at each step of the algorithm. In this paper, we propose a parameter-free approximate message passing (AMP) algorithm that sets the threshold parameter at each iteration in a fully automatic way without either having an information about the signal to be reconstructed or needing any tuning from the user. We show that the proposed method attains both the minimum reconstruction error and the highest convergence rate. Our method is based on applying the Stein unbiased risk estimate (SURE) along with a modified gradient descent to find the optimal threshold in each iteration. Motivated by the connections between AMP and LASSO, it could be employed to find the solution of the LASSO for the optimal regularization parameter. To the best of our knowledge, this is the first work concerning parameter tuning that obtains the fastest convergence rate with theoretical guarantees.
Robust Compressed Sensing and Sparse Coding with the Difference Map
Venue: arXiv cs.CV 2013
Year: 2013

In compressed sensing, we wish to reconstruct a sparse signal $x$ from observed data $y$. In sparse coding, on the other hand, we wish to find a representation of an observed signal $y$ as a sparse linear combination, with coefficients $x$, of elements from an overcomplete dictionary. While many algorithms are competitive at both problems when $x$ is very sparse, it can be challenging to recover $x$ when it is less sparse. We present the Difference Map, which excels at sparse recovery when sparseness is lower and noise is higher. The Difference Map out-performs the state of the art with reconstruction from random measurements and natural image reconstruction via sparse coding.
Revisiting Aggregation for Data Intensive Applications: A Performance Study
Venue: arXiv cs.DB 2013
Year: 2013

Aggregation has been an important operation since the early days of relational databases. Today's Big Data applications bring further challenges when processing aggregation queries, demanding adaptive aggregation algorithms that can process large volumes of data relative to a potentially limited memory budget (especially in multiuser settings). Despite its importance, the design and evaluation of aggregation algorithms has not received the same attention that other basic operators, such as joins, have received in the literature. As a result, when considering which aggregation algorithm(s) to implement in a new parallel Big Data processing platform (AsterixDB), we faced a lack of "off the shelf" answers that we could simply read about and then implement based on prior performance studies. In this paper we revisit the engineering of efficient local aggregation algorithms for use in Big Data platforms. We discuss the salient implementation details of several candidate algorithms and present an in-depth experimental performance study to guide future Big Data engine developers. We show that the efficient implementation of the aggregation operator for a Big Data platform is non-trivial and that many factors, including memory usage, spilling strategy, and I/O and CPU cost, should be considered. Further, we introduce precise cost models that can help in choosing an appropriate algorithm based on input parameters including memory budget, grouping key cardinality, and data skew.
Conceptual quantification of the dynamicity of longitudinal social networks
Venue: arXiv cs.SI 2013
Year: 2013

A longitudinal social network evolves over time through the creation and/ or deletion of links among a set of actors (e.g. individuals or organizations). Longitudinal social networks are studied by network science and social science researchers to understand networke volution, trend propagation, friendship and belief formation, diffusion of innovation, the spread of deviant behavior and more. In the current literature, there are different approaches and methods (e.g. Sampsons approach and the markov model) to study the dynamics of longitudinal social networks. These approaches and methods have mainly been utilised to explore evolutionary changes of longitudinal social networks from one state to another and to explain the underlying reasons for these changes. However, they cannot quantify the level of dynamicity of the over time network changes and the contribution of individual network members (i.e. actors) to these changes. In this study, we first develop a set of measures to quantify different aspects of the dynamicity of a longitudinal social network. We then apply these measures, in order to conduct empirical investigations, to two different longitudinal social networks. Finally, we discuss the implications of the application of these measures and possible future research directions of this study.
Decomposing Truthful and Competitive Online Double Auctions
Venue: arXiv cs.GT 2013
Year: 2013

In this paper, we study online double auctions, where multiple sellers and multiple buyers arrive and depart dynamically to exchange one commodity. We show that there is no deterministic online double auction that is truthful and competitive for maximising social welfare in an adversarial model. However, given the prior information that sellers are patient and the demand is not more than the supply, a deterministic and truthful greedy mechanism is actually 2-competitive, i.e. it guarantees that the social welfare of its allocation is at least half of the optimal one achievable offline. Moreover, if the number of incoming buyers is predictable, we demonstrate that an online double auction can be reduced to an online one-sided auction, and the truthfulness and competitiveness of the reduced online double auction follow that of the online one-sided auction. Notably, by using the reduction, we find a truthful mechanism that is almost 1-competitive, when buyers arrive randomly. Finally, we argue that these mechanisms also have a promising applicability in more general settings without assuming that sellers are patient, by decomposing a market into multiple sub-markets.
Online Learning with Multiple Operator-valued Kernels
Venue: arXiv cs.LG 2013
Year: 2013

We consider the problem of learning a vector-valued function f in an online learning setting. The function f is assumed to lie in a reproducing Hilbert space of operator-valued kernels. We describe two online algorithms for learning f while taking into account the output structure. A first contribution is an algorithm, ONORMA, that extends the standard kernel-based online learning algorithm NORMA from scalar-valued to operator-valued setting. We report a cumulative error bound that holds both for classification and regression. We then define a second algorithm, MONORMA, which addresses the limitation of pre-defining the output structure in ONORMA by learning sequentially a linear combination of operator-valued kernels. Our experiments show that the proposed algorithms achieve good performance results with low computational cost.
A Message Passing Strategy for Decentralized Connectivity Maintenance in Agent Removal
Venue: arXiv cs.SY 2013
Year: 2013

In a multi-agent system, agents coordinate to achieve global tasks through local communications. Coordination usually requires sufficient information flow, which is usually depicted by the connectivity of the communication network. In a networked system, removal of some agents may cause a disconnection. In order to maintain connectivity in agent removal, one can design a robust network topology that tolerates a finite number of agent losses, and/or develop a control strategy that recovers connectivity. This paper proposes a decentralized control scheme based on a sequence of replacements, each of which occurs between an agent and one of its immediate neighbors. The replacements always end with an agent, whose relocation does not cause a disconnection. We show that such an agent can be reached by a local rule utilizing only some local information available in agents' immediate neighborhoods. As such, the proposed message passing strategy guarantees the connectivity maintenance in arbitrary agent removal. Furthermore, we significantly improve the optimality of the proposed scheme by incorporating $δ$-criticality (i.e. the criticality of an agent in its $δ$-neighborhood).
Borel and Hausdorff Hierarchies in Topological Spaces of Choquet Games and Their Effectivization
Venue: arXiv cs.LO 2013
Year: 2013

What parts of classical descriptive set theory done in Polish spaces still hold for more general topological spaces, possibly T0 or T1, but not T2 (i.e. not Hausdorff)? This question has been addressed by Victor Selivanov in a series of papers centered on algebraic domains. And recently it has been considered by Matthew de Brecht for quasi-Polish spaces, a framework that contains both countably based continuous domains and Polish spaces. In this paper we present alternative unifying topological spaces, that we call approximation spaces. They are exactly the spaces for which player Nonempty has a stationary strategy in the Choquet game. A natural proper subclass of approximation spaces coincides with the class of quasi-Polish spaces. We study the Borel and Hausdorff difference hierarchies in approximation spaces, revisiting the work done for the other topological spaces. We also consider the problem of effectivization of these results.
Data-based approximate policy iteration for nonlinear continuous-time optimal control design
Venue: arXiv cs.SY 2013
Year: 2013

This paper addresses the model-free nonlinear optimal problem with generalized cost functional, and a data-based reinforcement learning technique is developed. It is known that the nonlinear optimal control problem relies on the solution of the Hamilton-Jacobi-Bellman (HJB) equation, which is a nonlinear partial differential equation that is generally impossible to be solved analytically. Even worse, most of practical systems are too complicated to establish their accurate mathematical model. To overcome these difficulties, we propose a data-based approximate policy iteration (API) method by using real system data rather than system model. Firstly, a model-free policy iteration algorithm is derived for constrained optimal control problem and its convergence is proved, which can learn the solution of HJB equation and optimal control policy without requiring any knowledge of system mathematical model. The implementation of the algorithm is based on the thought of actor-critic structure, where actor and critic neural networks (NNs) are employed to approximate the control policy and cost function, respectively. To update the weights of actor and critic NNs, a least-square approach is developed based on the method of weighted residuals. The whole data-based API method includes two parts, where the first part is implemented online to collect real system information, and the second part is conducting offline policy iteration to learn the solution of HJB equation and the control policy. Then, the data-based API algorithm is simplified for solving unconstrained optimal control problem of nonlinear and linear systems. Finally, we test the efficiency of the data-based API control design method on a simple nonlinear system, and further apply it to a rotational/translational actuator system. The simulation results demonstrate the effectiveness of the proposed method.
Accelerating Dissipative Particle Dynamics Simulations on GPUs: Algorithms, Numerics and Applications
Venue: arXiv cs.DC 2013
Year: 2013

We present a scalable dissipative particle dynamics simulation code, fully implemented on the Graphics Processing Units (GPUs) using a hybrid CUDA/MPI programming model, which achieves 10-30 times speedup on a single GPU over 16 CPU cores and almost linear weak scaling across a thousand nodes. A unified framework is developed within which the efficient generation of the neighbor list and maintaining particle data locality are addressed. Our algorithm generates strictly ordered neighbor lists in parallel, while the construction is deterministic and makes no use of atomic operations or sorting. Such neighbor list leads to optimal data loading efficiency when combined with a two-level particle reordering scheme. A faster in situ generation scheme for Gaussian random numbers is proposed using precomputed binary signatures. We designed custom transcendental functions that are fast and accurate for evaluating the pairwise interaction. The correctness and accuracy of the code is verified through a set of test cases simulating Poiseuille flow and spontaneous vesicle formation. Computer benchmarks demonstrate the speedup of our implementation over the CPU implementation as well as strong and weak scalability. A large-scale simulation of spontaneous vesicle formation consisting of 128 million particles was conducted to further illustrate the practicality of our code in real-world applications.