OpenRaiser/Intern-Atlas huggingface dataset:
Approximation for Maximum Surjective Constraint Satisfaction Problems
Venue: arXiv cs.CC 2011
Year: 2011

Maximum surjective constraint satisfaction problems (Max-Sur-CSPs) are computational problems where we are given a set of variables denoting values from a finite domain B and a set of constraints on the variables. A solution to such a problem is a surjective mapping from the set of variables to B such that the number of satisfied constraints is maximized. We study the approximation performance that can be acccchieved by algorithms for these problems, mainly by investigating their relation with Max-CSPs (which are the corresponding problems without the surjectivity requirement). Our work gives a complexity dichotomy for Max-Sur-CSP(B) between PTAS and APX-complete, under the assumption that there is a complexity dichotomy for Max-CSP(B) between PO and APX-complete, which has already been proved on the Boolean domain and 3-element domains.
OMG U got flu? Analysis of shared health messages for bio-surveillance
Venue: arXiv cs.CL 2011
Year: 2011

Background: Micro-blogging services such as Twitter offer the potential to crowdsource epidemics in real-time. However, Twitter posts ('tweets') are often ambiguous and reactive to media trends. In order to ground user messages in epidemic response we focused on tracking reports of self-protective behaviour such as avoiding public gatherings or increased sanitation as the basis for further risk analysis. Results: We created guidelines for tagging self protective behaviour based on Jones and Salathé (2009)'s behaviour response survey. Applying the guidelines to a corpus of 5283 Twitter messages related to influenza like illness showed a high level of inter-annotator agreement (kappa 0.86). We employed supervised learning using unigrams, bigrams and regular expressions as features with two supervised classifiers (SVM and Naive Bayes) to classify tweets into 4 self-reported protective behaviour categories plus a self-reported diagnosis. In addition to classification performance we report moderately strong Spearman's Rho correlation by comparing classifier output against WHO/NREVSS laboratory data for A(H1N1) in the USA during the 2009-2010 influenza season. Conclusions: The study adds to evidence supporting a high degree of correlation between pre-diagnostic social media signals and diagnostic influenza case data, pointing the way towards low cost sensor networks. We believe that the signals we have modelled may be applicable to a wide range of diseases.
Telling Two Distributions Apart: a Tight Characterization
Venue: arXiv cs.DS 2011
Year: 2011

We consider the problem of distinguishing between two arbitrary black-box distributions defined over the domain [n], given access to $s$ samples from both. It is known that in the worst case O(n^{2/3}) samples is both necessary and sufficient, provided that the distributions have L1 difference of at least ε. However, it is also known that in many cases fewer samples suffice. We identify a new parameter, that provides an upper bound on how many samples needed, and present an efficient algorithm that requires the number of samples independent of the domain size. Also for a large subclass of distributions we provide a lower bound, that matches our upper bound up to a poly-logarithmic factor.
Controlled Total Variation regularization for inverse problems
Venue: arXiv cs.CV 2011
Year: 2011

This paper provides a new algorithm for solving inverse problems, based on the minimization of the $L^2$ norm and on the control of the Total Variation. It consists in relaxing the role of the Total Variation in the classical Total Variation minimization approach, which permits us to get better approximation to the inverse problems. The numerical results on the deconvolution problem show that our method outperforms some previous ones.
An Enhanced Multiple Random Access Scheme for Satellite Communications
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we introduce Multi-Slots Coded ALOHA (MuSCA) as a multiple random access method for satellite communications. This scheme can be considered as a generalization of the Contention Resolution Diversity Slotted Aloha (CRDSA) mechanism. Instead of transmitting replicas, this system replaces them by several parts of a single word of an error correcting code. It is also different from Coded Slotted ALOHA (CSA) as the assumption of destructive collisions is not adopted. In MuSCA, the entity in charge of the decoding mechanism collects all bursts of the same user (including the interfered slots) before decoding and implements a successive interference cancellation (SIC) process to remove successfully decoded signals. Simulations show that for a frame of 100 slots, the achievable total normalized throughput is greater than 1.25 and 1.4 for a frame of 500 slots, resulting in a gain of 80% and 75% with respect to CRDSA and CSA respectively. This paper is a first analysis of the proposed scheme and opens several perspectives.
Reduced-dimension multiuser detection: detectors and performance guarantees
Venue: arXiv cs.IT 2011
Year: 2011

We explore several reduced-dimension multiuser detection (RD-MUD) structures that significantly decrease the number of required correlation branches at the receiver front-end, while still achieving performance similar to that of the conventional matched-filter (MF) bank. RD-MUD exploits the fact that the number of active users is typically small relative to the total number of users in the system and relies on ideas of analog compressed sensing to reduce the number of correlators. We first develop a general framework for both linear and nonlinear RD-MUD detectors. We then present theoretical performance analysis for two specific detectors: the linear reduced-dimension decorrelating (RDD) detector, which combines subspace projection and thresholding to determine active users and sign detection for data recovery, and the nonlinear reduced-dimension decision-feedback (RDDF) detector, which combines decision-feedback orthogonal matching pursuit for active user detection and sign detection for data recovery. The theoretical performance results for both detectors are validated via numerical simulations.
Sampling Techniques in Bayesian Finite Element Model Updating
Venue: arXiv cs.CE 2011
Year: 2011

Recent papers in the field of Finite Element Model (FEM) updating have highlighted the benefits of Bayesian techniques. The Bayesian approaches are designed to deal with the uncertainties associated with complex systems, which is the main problem in the development and updating of FEMs. This paper highlights the complexities and challenges of implementing any Bayesian method when the analysis involves a complicated structural dynamic model. In such systems an analytical Bayesian formulation might not be available in an analytic form; therefore this leads to the use of numerical methods, i.e. sampling methods. The main challenge then is to determine an efficient sampling of the model parameter space. In this paper, three sampling techniques, the Metropolis-Hastings (MH) algorithm, Slice Sampling and the Hybrid Monte Carlo (HMC) technique, are tested by updating a structural beam model. The efficiency and limitations of each technique is investigated when the FEM updating problem is implemented using the Bayesian Approach. Both MH and HMC techniques are found to perform better than the Slice sampling when Young's modulus is chosen as the updating parameter. The HMC method gives better results than MH and Slice sampling techniques, when the area moment of inertias and section areas are updated.
Fuzzy Inference Systems Optimization
Venue: arXiv cs.AI 2011
Year: 2011

This paper compares various optimization methods for fuzzy inference system optimization. The optimization methods compared are genetic algorithm, particle swarm optimization and simulated annealing. When these techniques were implemented it was observed that the performance of each technique within the fuzzy inference system classification was context dependent.
Reasoning about Actions with Temporal Answer Sets
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we combine Answer Set Programming (ASP) with Dynamic Linear Time Temporal Logic (DLTL) to define a temporal logic programming language for reasoning about complex actions and infinite computations. DLTL extends propositional temporal logic of linear time with regular programs of propositional dynamic logic, which are used for indexing temporal modalities. The action language allows general DLTL formulas to be included in domain descriptions to constrain the space of possible extensions. We introduce a notion of Temporal Answer Set for domain descriptions, based on the usual notion of Answer Set. Also, we provide a translation of domain descriptions into standard ASP and we use Bounded Model Checking techniques for the verification of DLTL constraints.
The Logic of XACML - Extended
Venue: arXiv cs.CR 2011
Year: 2011

We study the international standard XACML 3.0 for describing security access control policy in a compositional way. Our main contribution is to derive a logic that precisely captures the idea behind the standard and to formally define the semantics of the policy combining algorithms of XACML. To guard against modelling artefacts we provide an alternative way of characterizing the policy combining algorithms and we formally prove the equivalence of these approaches. This allows us to pinpoint the shortcoming of previous approaches to formalization based either on Belnap logic or on D-algebra.
Optimization strategies for parallel CPU and GPU implementations of a meshfree particle method
Venue: arXiv cs.PF 2011
Year: 2011

Much of the current focus in high performance computing (HPC) for computational fluid dynamics (CFD) deals with grid based methods. However, parallel implementations for new meshfree particle methods such as Smoothed Particle Hydrodynamics (SPH) are less studied. In this work, we present optimizations for both central processing unit (CPU) and graphics processing unit (GPU) of a SPH method. These optimization strategies can be further applied to many other meshfree methods. The obtained performance for each architecture and a comparison between the most efficient implementations for CPU and GPU are shown.
Clone Structures in Voters' Preferences
Venue: arXiv cs.GT 2011
Year: 2011

In elections, a set of candidates ranked consecutively (though possibly in different order) by all voters is called a clone set, and its members are called clones. A clone structure is a family of all clone sets of a given election. In this paper we study properties of clone structures. In particular, we give an axiomatic characterization of clone structures, show their hierarchical structure, and analyze clone structures in single-peaked and single-crossing elections. We give a polynomial-time algorithm that finds a minimal collection of clones that need to be collapsed for an election to become single-peaked, and we show that this problem is NP-hard for single-crossing elections.
The large-scale structure of journal citation networks
Venue: arXiv cs.SI 2011
Year: 2011

We analyse the large-scale structure of the journal citation network built from information contained in the Thomson-Reuters Journal Citation Reports. To this end, we take advantage of the network science paraphernalia and explore network properties like density, percolation robustness, average and largest node distances, reciprocity, incoming and outgoing degree distributions, as well as assortative mixing by node degrees. We discover that the journal citation network is a dense, robust, small, and reciprocal world. Furthermore, in and out node degree distributions display long-tails, with few vital journals and many trivial ones, and they are strongly positively correlated.
The non-abelian squares are not context-free
Venue: arXiv cs.FL 2011
Year: 2011

Answering a recent question of Crochemore, we prove that the language of words that are not abelian squares is not context-free.
Secure Execution of Distributed Session Programs
Venue: arXiv cs.DC 2011
Year: 2011

The development of the SJ Framework for session-based distributed programming is part of recent and ongoing research into integrating session types and practical, real-world programming languages. SJ programs featuring session types (protocols) are statically checked by the SJ compiler to verify the key property of communication safety, meaning that parties engaged in a session only communicate messages, including higher-order communications via session delegation, that are compatible with the message types expected by the recipient. This paper presents current work on security aspects of the SJ Framework. Firstly, we discuss our implementation experience from improving the SJ Runtime platform with security measures to protect and augment communication safety at runtime. We implement a transport component for secure session execution that uses a modified TLS connection with authentication based on the Secure Remote Password (SRP) protocol. The key technical point is the delicate treatment of secure session delegation to counter a previous vulnerability. We find that the modular design of the SJ Runtime, based on the notion of an Abstract Transport for session communication, supports rapid extension to utilise additional transports whilst separating this concern from the application-level session programming task. In the second part of this abstract, we formally prove the target security properties by modelling the extended SJ delegation protocols in the pi-calculus.
A Logic for Choreographies
Venue: arXiv cs.PL 2011
Year: 2011

We explore logical reasoning for the global calculus, a coordination model based on the notion of choreography, with the aim to provide a methodology for specification and verification of structured communications. Starting with an extension of Hennessy-Milner logic, we present the global logic (GL), a modal logic describing possible interactions among participants in a choreography. We illustrate its use by giving examples of properties on service specifications. Finally, we show that, despite GL is undecidable, there is a significant decidable fragment which we provide with a sound and complete proof system for checking validity of formulae.
A Type System for Unstructured Locking that Guarantees Deadlock Freedom without Imposing a Lock Ordering
Venue: arXiv cs.PL 2011
Year: 2011

Deadlocks occur in concurrent programs as a consequence of cyclic resource acquisition between threads. In this paper we present a novel type system that guarantees deadlock freedom for a language with references, unstructured locking primitives, and locks which are implicitly associated with references. The proposed type system does not impose a strict lock acquisition order and thus increases programming language expressiveness.
Injecting External Solutions Into CMA-ES
Venue: arXiv cs.LG 2011
Year: 2011

This report considers how to inject external candidate solutions into the CMA-ES algorithm. The injected solutions might stem from a gradient or a Newton step, a surrogate model optimizer or any other oracle or search mechanism. They can also be the result of a repair mechanism, for example to render infeasible solutions feasible. Only small modifications to the CMA-ES are necessary to turn injection into a reliable and effective method: too long steps need to be tightly renormalized. The main objective of this report is to reveal this simple mechanism. Depending on the source of the injected solutions, interesting variants of CMA-ES arise. When the best-ever solution is always (re-)injected, an elitist variant of CMA-ES with weighted multi-recombination arises. When \emph{all} solutions are injected from an \emph{external} source, the resulting algorithm might be viewed as \emph{adaptive encoding} with step-size control. In first experiments, injected solutions of very good quality lead to a convergence speed twice as fast as on the (simple) sphere function without injection. This means that we observe an impressive speed-up on otherwise difficult to solve functions. Single bad injected solutions on the other hand do no significant harm.
(1+eps)-approximate Sparse Recovery
Venue: arXiv cs.DS 2011
Year: 2011

The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution of matrices A in R^{m\times n} such that, for any x \in R^n and with probability at least 2/3 over A, there is an algorithm to recover x* from Ax with ||x* - x||_p <= C min_{k-sparse x'} ||x - x'||_p for some constant C > 1 and norm p. The measurement complexity of this problem is well understood for constant C > 1. However, in a variety of applications it is important to obtain C = 1 + eps for a small eps > 0, and this complexity is not well understood. We resolve the dependence on eps in the number of measurements required of a k-sparse recovery algorithm, up to polylogarithmic factors for the central cases of p = 1 and p = 2. Namely, we give new algorithms and lower bounds that show the number of measurements required is (1/eps^{p/2})k polylog(n). For p = 2, our bound of (1/eps) k log(n/k) is tight up to constant factors. We also give matching bounds when the output is required to be k-sparse, in which case we achieve (1/eps^p) k polylog(n). This shows the distinction between the complexity of sparse and non-sparse outputs is fundamental.
Robustness of Social Networks: Comparative Results Based on Distance Distributions
Venue: arXiv cs.SI 2011
Year: 2011

Given a social network, which of its nodes have a stronger impact in determining its structure? More formally: which node-removal order has the greatest impact on the network structure? We approach this well-known problem for the first time in a setting that combines both web graphs and social networks, using datasets that are orders of magnitude larger than those appearing in the previous literature, thanks to some recently developed algorithms and software tools that make it possible to approximate accurately the number of reachable pairs and the distribution of distances in a graph. Our experiments highlight deep differences in the structure of social networks and web graphs, show significant limitations of previous experimental results, and at the same time reveal clustering by label propagation as a new and very effective way of locating nodes that are important from a structural viewpoint.
An Ontology-Based Method for Semantic Integration of Business Components
Venue: arXiv cs.SE 2011
Year: 2011

Building new business information systems from reusable components is today an approach widely adopted and used. Using this approach in analysis and design phases presents a great interest and requires the use of a particular class of components called Business Components (BC). Business Components are today developed by several manufacturers and are available in many repositories. However, reusing and integrating them in a new Information System requires detection and resolution of semantic conflicts. Moreover, most of integration and semantic conflict resolution systems rely on ontology alignment methods based on domain ontology. This work is positioned at the intersection of two research areas: Integration of reusable Business Components and alignment of ontologies for semantic conflict resolution. Our contribution concerns both the proposal of a BC integration solution based on ontologies alignment and a method for enriching the domain ontology used as a support for alignment.
A Survey on Delay-Aware Resource Control for Wireless Systems --- Large Deviation Theory, Stochastic Lyapunov Drift and Distributed Stochastic Learning
Venue: arXiv cs.PF 2011
Year: 2011

In this tutorial paper, a comprehensive survey is given on several major systematic approaches in dealing with delay-aware control problems, namely the equivalent rate constraint approach, the Lyapunov stability drift approach and the approximate Markov Decision Process (MDP) approach using stochastic learning. These approaches essentially embrace most of the existing literature regarding delay-aware resource control in wireless systems. They have their relative pros and cons in terms of performance, complexity and implementation issues. For each of the approaches, the problem setup, the general solution and the design methodology are discussed. Applications of these approaches to delay-aware resource allocation are illustrated with examples in single-hop wireless networks. Furthermore, recent results regarding delay-aware multi-hop routing designs in general multi-hop networks are elaborated. Finally, the delay performance of the various approaches are compared through simulations using an example of the uplink OFDMA systems.
On the homotopy test on surfaces
Venue: arXiv cs.CG 2011
Year: 2011

Let G be a graph cellularly embedded in a surface S. Given two closed walks c and d in G, we take advantage of the RAM model to describe linear time algorithms to decide if c and d are homotopic in S, either freely or with fixed basepoint. We restrict S to be orientable for the free homotopy test, but allow non-orientable surfaces when the basepoint is fixed. After O(|G|) time preprocessing independent of c and d, our algorithms answer the homotopy test in O(|c|+|d|) time, where |G|, |c| and |d| are the respective numbers of edges of G, c and d. As a byproduct we obtain linear time algorithms for the word problem and the conjugacy problem in surface groups. We present a geometric approach based on previous works by Colin de Verdière and Erickson.
Improving Christofides' Algorithm for the s-t Path TSP
Venue: arXiv cs.DS 2011
Year: 2011

We present a deterministic (1+sqrt(5))/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides' algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact has been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides' algorithm variant. Our algorithm also proves an upper bound of (1+sqrt(5))/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.