OpenRaiser/Intern-Atlas huggingface dataset:
Contribution à la modélisation explicite des plates-formes d'exécution pour l'IDM
Venue: arXiv cs.SE 2014
Year: 2014

One foundation of the model driven engineering (MDE) is to separate the modelling application description from its technological implementation (i.e. platform). Some of them are dedicated to the system execution. Hence, one promise solution of the MDE is to automate transformations from platform independent models to platform specific models. Little work has explicitly described platform characteristics. Yet, an explicit modelling allows taking in account their characteristics more easily (par ex., performances, maintainability,portability). This paper presents both an execution platform modelling state of art and a pattern to describe execution platform modelling framework. It intends to confirm the feasibility and the interests in describing an execution platform metamodel.
A Tight Lower Bound for Decrease-Key in the Pure Heap Model
Venue: arXiv cs.DS 2014
Year: 2014

We improve the lower bound on the amortized cost of the decrease-key operation in the pure heap model and show that any pure-heap-model heap (that has a \bigoh{\log n} amortized-time extract-min operation) must spend \bigom{\log\log n} amortized time on the decrease-key operation. Our result shows that sort heaps as well as pure-heap variants of numerous other heaps have asymptotically optimal decrease-key operations in the pure heap model. In addition, our improved lower bound matches the lower bound of Fredman [J. ACM 46(4):473-501 (1999)] for pairing heaps [M.L. Fredman, R. Sedgewick, D.D. Sleator, and R.E. Tarjan. Algorithmica 1(1):111-129 (1986)] and surpasses it for pure-heap variants of numerous other heaps with augmented data such as pointer rank-pairing heaps.
Differential Distributed Space-Time Coding with Imperfect Synchronization
Venue: arXiv cs.IT 2014
Year: 2014

Differential distributed space-time coding (D-DSTC) has been considered to improve both diversity and data-rate in cooperative communications in the absence of channel information. However, conventionally, it is assumed that relays are perfectly synchronized in the symbol level. In practice, this assumption is easily violated due to the distributed nature of the relay networks. This paper proposes a new differential encoding and decoding process for D-DSTC systems with two relays. The proposed method is robust against synchronization errors and does not require any channel information at the destination. Moreover, the maximum possible diversity and symbol-by-symbol decoding are attained. Simulation results are provided to show the performance of the proposed method for various synchronization errors and the fact that our algorithm is not sensitive to synchronization error.
GCD Computation of n Integers
Venue: arXiv cs.DS 2014
Year: 2014

Greatest Common Divisor (GCD) computation is one of the most important operation of algorithmic number theory. In this paper we present the algorithms for GCD computation of $n$ integers. We extend the Euclid's algorithm and binary GCD algorithm to compute the GCD of more than two integers.
Higher-Order Approximate Relational Refinement Types for Mechanism Design and Differential Privacy
Venue: arXiv cs.PL 2014
Year: 2014

Mechanism design is the study of algorithm design in which the inputs to the algorithm are controlled by strategic agents, who must be incentivized to faithfully report them. Unlike typical programmatic properties, it is not sufficient for algorithms to merely satisfy the property---incentive properties are only useful if the strategic agents also believe this fact. Verification is an attractive way to convince agents that the incentive properties actually hold, but mechanism design poses several unique challenges: interesting properties can be sophisticated relational properties of probabilistic computations involving expected values, and mechanisms may rely on other probabilistic properties, like differential privacy, to achieve their goals. We introduce a relational refinement type system, called $\mathsf{HOARe}^2$, for verifying mechanism design and differential privacy. We show that $\mathsf{HOARe}^2$ is sound w.r.t. a denotational semantics, and correctly models $(ε,δ)$-differential privacy; moreover, we show that it subsumes DFuzz, an existing linear dependent type system for differential privacy. Finally, we develop an SMT-based implementation of $\mathsf{HOARe}^2$ and use it to verify challenging examples of mechanism design, including auctions and aggregative games, and new proposed examples from differential privacy.
Modeling and Recognition of Smart Grid Faults by a Combined Approach of Dissimilarity Learning and One-Class Classification
Venue: arXiv cs.AI 2014
Year: 2014

Detecting faults in electrical power grids is of paramount importance, either from the electricity operator and consumer viewpoints. Modern electric power grids (smart grids) are equipped with smart sensors that allow to gather real-time information regarding the physical status of all the component elements belonging to the whole infrastructure (e.g., cables and related insulation, transformers, breakers and so on). In real-world smart grid systems, usually, additional information that are related to the operational status of the grid itself are collected such as meteorological information. Designing a suitable recognition (discrimination) model of faults in a real-world smart grid system is hence a challenging task. This follows from the heterogeneity of the information that actually determine a typical fault condition. The second point is that, for synthesizing a recognition model, in practice only the conditions of observed faults are usually meaningful. Therefore, a suitable recognition model should be synthesized by making use of the observed fault conditions only. In this paper, we deal with the problem of modeling and recognizing faults in a real-world smart grid system, which supplies the entire city of Rome, Italy. Recognition of faults is addressed by following a combined approach of multiple dissimilarity measures customization and one-class classification techniques. We provide here an in-depth study related to the available data and to the models synthesized by the proposed one-class classifier. We offer also a comprehensive analysis of the fault recognition results by exploiting a fuzzy set based reliability decision rule.
Maximizing Spectrum Availability and Exploitation: How to Maximize Spectrum Sharing Benefits to the Incumbents?
Venue: arXiv cs.CY 2014
Year: 2014

A significant portion of the radio frequency spectrum remains underutilized due to exclusive and static allocation of spectrum. Provisioning secondary access to the underutilized spectrum could be beneficial to the incumbents if they could gain significant value out of the fallow spectrum while ensuring protection of their primary services. From an incumbent perspective, the spectrum sharing approach needs to be non-harmful as well as efficient. In order to make spectrum sharing efficient, it is necessary to maximize the spectrum available for secondary access as well as maximize its exploitation. We examine the impact of the conservative assumptions that lead to lesser availability of spectrum for secondary access. The problem of joint scheduling and spectrum-access footprint allocation is at the heart of maximizing the exploitation. This problem is NP-hard and we present a suboptimal approach based on the minimal spectrum consumption cost of a spectrum-access request. In order to improve the spectrum sharing potential, we investigate the impact of the various design choices for a spectrum access mechanism. The experiments demonstrate the significance of the active role of the incumbents, the benefits of fine granular spectrum access, and the need for transceiver standards for accomplishing efficient usage of the spectrum.
On Polynomial Kernelization of $\mathcal{H}$-free Edge Deletion
Venue: arXiv cs.DS 2014
Year: 2014

For a set of graphs $\mathcal{H}$, the \textsc{$\mathcal{H}$-free Edge Deletion} problem asks to find whether there exist at most $k$ edges in the input graph whose deletion results in a graph without any induced copy of $H\in\mathcal{H}$. In \cite{cai1996fixed}, it is shown that the problem is fixed-parameter tractable if $\mathcal{H}$ is of finite cardinality. However, it is proved in \cite{cai2013incompressibility} that if $\mathcal{H}$ is a singleton set containing $H$, for a large class of $H$, there exists no polynomial kernel unless $coNP\subseteq NP/poly$. In this paper, we present a polynomial kernel for this problem for any fixed finite set $\mathcal{H}$ of connected graphs and when the input graphs are of bounded degree. We note that there are \textsc{$\mathcal{H}$-free Edge Deletion} problems which remain NP-complete even for the bounded degree input graphs, for example \textsc{Triangle-free Edge Deletion}\cite{brugmann2009generating} and \textsc{Custer Edge Deletion($P_3$-free Edge Deletion)}\cite{komusiewicz2011alternative}. When $\mathcal{H}$ contains $K_{1,s}$, we obtain a stronger result - a polynomial kernel for $K_t$-free input graphs (for any fixed $t> 2$). We note that for $s>9$, there is an incompressibility result for \textsc{$K_{1,s}$-free Edge Deletion} for general graphs \cite{cai2012polynomial}. Our result provides first polynomial kernels for \textsc{Claw-free Edge Deletion} and \textsc{Line Edge Deletion} for $K_t$-free input graphs which are NP-complete even for $K_4$-free graphs\cite{yannakakis1981edge} and were raised as open problems in \cite{cai2013incompressibility,open2013worker}.
Tight lower bound for the channel assignment problem
Venue: arXiv cs.DS 2014
Year: 2014

We study the complexity of the Channel Assignment problem. A major open problem asks whether Channel Assignment admits an $O(c^n)$-time algorithm, for a constant $c$ independent of the weights on the edges. We answer this question in the negative i.e. we show that there is no $2^{o(n\log n)}$-time algorithm solving Channel Assignment unless the Exponential Time Hypothesis fails. Note that the currently best known algorithm works in time $O^*(n!) = 2^{O(n\log n)}$ so our lower bound is tight.
A Logic for Reasoning about Evidence
Venue: arXiv cs.AI 2014
Year: 2014

We introduce a logic for reasoning about evidence, that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence
When Ignorance is Bliss
Venue: arXiv cs.AI 2014
Year: 2014

It is commonly-accepted wisdom that more information is better, and that information should never be ignored. Here we argue, using both a Bayesian and a non-Bayesian analysis, that in some situations you are better off ignoring information if your uncertainty is represented by a set of probability measures. These include situations in which the information is relevant for the prediction task at hand. In the non-Bayesian analysis, we show how ignoring information avoids dilation, the phenomenon that additional pieces of information sometimes lead to an increase in uncertainty. In the Bayesian analysis, we show that for small sample sizes and certain prediction tasks, the Bayesian posterior based on a noninformative prior yields worse predictions than simply ignoring the given information.
An evolutionary solver for linear integer programming
Venue: arXiv cs.NE 2014
Year: 2014

In this paper we introduce an evolutionary algorithm for the solution of linear integer programs. The strategy is based on the separation of the variables into the integer subset and the continuous subset; the integer variables are fixed by the evolutionary system, and the continuous ones are determined in function of them, by a linear program solver. We report results obtained for some standard benchmark problems, and compare them with those obtained by branch-and-bound. The performance of the evolutionary algorithm is promising. Good feasible solutions were generally obtained, and in some of the difficult benchmark tests it outperformed branch-and-bound.
Spectral goodness of fit for network models
Venue: arXiv cs.SI 2014
Year: 2014

We introduce a new statistic, 'spectral goodness of fit' (SGOF) to measure how well a network model explains the structure of an observed network. SGOF provides an absolute measure of fit, analogous to the standard R-squared in linear regression. Additionally, as it takes advantage of the properties of the spectrum of the graph Laplacian, it is suitable for comparing network models of diverse functional forms, including both fitted statistical models and algorithmic generative models of networks. After introducing, defining, and providing guidance for interpreting SGOF, we illustrate the properties of the statistic with a number of examples and comparisons to existing techniques. We show that such a spectral approach to assessing model fit fills gaps left by earlier methods and can be widely applied.
Q-A: Towards the Solution of Usability-Security Tension in User Authentication
Venue: arXiv cs.HC 2014
Year: 2014

Users often choose passwords that are easy to remember but also easy to guess by attackers. Recent studies have revealed the vulnerability of textual passwords to shoulder surfing and keystroke loggers. It remains a critical challenge in password research to develop an authentication scheme that addresses these security issues, in addition to offering good memorability. Motivated by psychology research on humans' cognitive strengths and weaknesses, we explore the potential of cognitive questions as a way to address the major challenges in user authentication. We design, implement, and evaluate Q-A, a novel cognitive-question-based password system that requires a user to enter the letter at a given position in her answer for each of six personal questions (e.g. "What is the name of your favorite childhood teacher?"). In this scheme, the user does not need to memorize new, artificial information as her authentication secret. Our scheme offers 28 bits of theoretical password space, which has been found sufficient to prevent online brute-force attacks. Q-A is also robust against shoulder surfing and keystroke loggers. We conducted a multi-session in-lab user study to evaluate the usability of Q-A; 100% of users were able to remember their Q-A password over the span of one week, although login times were high. We compared our scheme with random six character passwords and found that login success rate in Q-A was significantly higher. Based on our results, we suggest that Q-A would be most appropriate in contexts that demand high security and where logins occur infrequently (e.g., online bank accounts).
A Method for Reducing the Severity of Epidemics by Allocating Vaccines According to Centrality
Venue: arXiv cs.SI 2014
Year: 2014

One long-standing question in epidemiological research is how best to allocate limited amounts of vaccine or similar preventative measures in order to minimize the severity of an epidemic. Much of the literature on the problem of vaccine allocation has focused on influenza epidemics and used mathematical models of epidemic spread to determine the effectiveness of proposed methods. Our work applies computational models of epidemics to the problem of geographically allocating a limited number of vaccines within several Texas counties. We developed a graph-based, stochastic model for epidemics that is based on the SEIR model, and tested vaccine allocation methods based on multiple centrality measures. This approach provides an alternative method for addressing the vaccine allocation problem, which can be combined with more conventional approaches to yield more effective epidemic suppression strategies. We found that allocation methods based on in-degree and inverse betweenness centralities tended to be the most effective at containing epidemics.
A Latent Space Analysis of Editor Lifecycles in Wikipedia
Venue: arXiv cs.SI 2014
Year: 2014

Collaborations such as Wikipedia are a key part of the value of the modern Internet. At the same time there is concern that these collaborations are threatened by high levels of member turnover. In this paper we borrow ideas from topic analysis to editor activity on Wikipedia over time into a latent space that offers an insight into the evolving patterns of editor behavior. This latent space representation reveals a number of different categories of editor (e.g. content experts, social networkers) and we show that it does provide a signal that predicts an editor's departure from the community. We also show that long term editors gradually diversify their participation by shifting edit preference from one or two namespaces to multiple namespaces and experience relatively soft evolution in their editor profiles, while short term editors generally distribute their contribution randomly among the namespaces and experience considerably fluctuated evolution in their editor profiles.
The Operationalization of "Fields" as WoS Subject Categories (WCs) in Evaluative Bibliometrics: The cases of "Library and Information Science" and "Science & Technology Studies"
Venue: arXiv cs.DL 2014
Year: 2014

Normalization of citation scores using reference sets based on Web-of-Science Subject Categories (WCs) has become an established ("best") practice in evaluative bibliometrics. For example, the Times Higher Education World University Rankings are, among other things, based on this operationalization. However, WCs were developed decades ago for the purpose of information retrieval and evolved incrementally with the database; the classification is machine-based and partially manually corrected. Using the WC "information science & library science" and the WCs attributed to journals in the field of "science and technology studies," we show that WCs do not provide sufficient analytical clarity to carry bibliometric normalization in evaluation practices because of "indexer effects." Can the compliance with "best practices" be replaced with an ambition to develop "best possible practices"? New research questions can then be envisaged.
Top-Down Skiplists
Venue: arXiv cs.DS 2014
Year: 2014

We describe todolists (top-down skiplists), a variant of skiplists (Pugh 1990) that can execute searches using at most $\log_{2-\varepsilon} n + O(1)$ binary comparisons per search and that have amortized update time $O(\varepsilon^{-1}\log n)$. A variant of todolists, called working-todolists, can execute a search for any element $x$ using $\log_{2-\varepsilon} w(x) + o(\log w(x))$ binary comparisons and have amortized search time $O(\varepsilon^{-1}\log w(w))$. Here, $w(x)$ is the "working-set number" of $x$. No previous data structure is known to achieve a bound better than $4\log_2 w(x)$ comparisons. We show through experiments that, if implemented carefully, todolists are comparable to other common dictionary implementations in terms of insertion times and outperform them in terms of search times.
Graph- versus Vector-Based Analysis of a Consensus Protocol
Venue: arXiv cs.LO 2014
Year: 2014

The Paxos distributed consensus algorithm is a challenging case-study for standard, vector-based model checking techniques. Due to asynchronous communication, exhaustive analysis may generate very large state spaces already for small model instances. In this paper, we show the advantages of graph transformation as an alternative modelling technique. We model Paxos in a rich declarative transformation language, featuring (among other things) nested quantifiers, and we validate our model using the GROOVE model checker, a graph-based tool that exploits isomorphism as a natural way to prune the state space via symmetry reductions. We compare the results with those obtained by the standard model checker Spin on the basis of a vector-based encoding of the algorithm.
An Investigation into the use of Images as Password Cues
Venue: arXiv cs.HC 2014
Year: 2014

Computer users are generally authenticated by means of a password. Unfortunately passwords are often forgotten and replacement is expensive and inconvenient. Some people write their passwords down but these records can easily be lost or stolen. The option we explore is to find a way to cue passwords securely. The specific cueing technique we report on in this paper employs images as cues. The idea is to elicit textual descriptions of the images, which can then be used as passwords. We have defined a set of metrics for the kind of image that could function effectively as a password cue. We identified five candidate image types and ran an experiment to identify the image class with the best performance in terms of the defined metrics. The first experiment identified inkblot-type images as being superior. We tested this image, called a cueblot, in a real-life environment. We allowed users to tailor their cueblot until they felt they could describe it, and they then entered a description of the cueblot as their password. The cueblot was displayed at each subsequent authentication attempt to cue the password. Unfortunately, we found that users did not exploit the cueing potential of the cueblot, and while there were a few differences between textual descriptions of cueblots and non-cued passwords, they were not compelling. Hence our attempts to alleviate the difficulties people experience with passwords, by giving them access to a tailored cue, did not have the desired effect. We have to conclude that the password mechanism might well be unable to benefit from bolstering activities such as this one.
Structural differences between open and direct communication in an online community
Venue: arXiv cs.SI 2014
Year: 2014

Most research of online communication focuses on modes of communication that are either open (like forums, bulletin boards, Twitter, etc.) or direct (like e-mails). In this work, we study a dataset that has both types of communication channels. We relate our findings to theories of social organization and human dynamics. The data comprises 36,492 users of a movie discussion community. Our results show that there are differences in the way users communicate in the two channels that are reflected in the shape of degree- and interevent time distributions. The open communication that is designed to facilitate conversations with any member, shows a broader degree distribution and more of the triangles in the network are primarily formed in this mode of communication. The direct channel is presumably preferred by closer communication and the response time in dialogues is shorter. On a more coarse-grained level, there are common patterns in the two networks. The differences and overlaps between communication networks, thus, provide a unique window into how social and structural aspects of communication establish and evolve.
Merging and Shifting of Images with Prominence Coefficient for Predictive Analysis using Combined Image
Venue: arXiv cs.CV 2014
Year: 2014

Shifting of objects in an image and merging many images after appropriate shifting is being used in several engineering and scientific applications which require complex perception development. A method has been presented here which could be used in precision engineering and biological applications where more precise prediction is required of a combined phenomenon with varying prominence of each phenomenon. Accurate merging of intended pixels can be achieved in high quality using frequency domain techniques even though initial properties of the original pixels are lost in this process. This paper introduces a technique to shift and merge various images with varying prominence of each image. A coefficient named prominence coefficient has been introduced which is capable of making some of the images transparent and highlighting the rest as per requirement of merging process which can be used as a simple but effective technique for overlapped view of a set of images.