Search results for "Information Systems."
showing 10 items of 1545 documents
Mahonian STAT on words
2016
In 2000, Babson and Steingrimsson introduced the notion of what is now known as a permutation vincular pattern, and based on it they re-defined known Mahonian statistics and introduced new ones, proving or conjecturing their Mahonity. These conjectures were proved by Foata and Zeilberger in 2001, and by Foata and Randrianarivony in 2006.In 2010, Burstein refined some of these results by giving a bijection between permutations with a fixed value for the major index and those with the same value for STAT , where STAT is one of the statistics defined and proved to be Mahonian in the 2000 Babson and Steingrimsson's paper. Several other statistics are preserved as well by Burstein's bijection.At…
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
2017
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex $v$, outputs the children of $v$. We construct a quantum algorithm which, given such access to a search tree of depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm \delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model. We then show two applications of this result: a) We show how to transform a classical backtracking search algorithm which exam…
A Quantum Lovasz Local Lemma
2012
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e \cdot k)$ of them, has a joint satisfiable state. We then …
Blockchain-Based Proof of Location
2016
Location-Based Services (LBSs) build upon geographic information to provide users with location-dependent functionalities. In such a context, it is particularly important that geographic locations claimed by users are trustworthy. Centralized verification approaches proposed in the last few years are not satisfactory, as they entail a high risk to the privacy of users. In this paper, we present and evaluate a novel decentralized, infrastructure-independent proof-of-location scheme based on blockchain technology. Our scheme guarantees both location trustworthiness and user privacy preservation.
Sensitivity versus block sensitivity of Boolean functions
2010
Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
Quasi conjunction, quasi disjunction, t-norms and t-conorms: Probabilistic aspects
2013
We make a probabilistic analysis related to some inference rules which play an important role in nonmonotonic reasoning. In a coherence-based setting, we study the extensions of a probability assessment defined on $n$ conditional events to their quasi conjunction, and by exploiting duality, to their quasi disjunction. The lower and upper bounds coincide with some well known t-norms and t-conorms: minimum, product, Lukasiewicz, and Hamacher t-norms and their dual t-conorms. On this basis we obtain Quasi And and Quasi Or rules. These are rules for which any finite family of conditional events p-entails the associated quasi conjunction and quasi disjunction. We examine some cases of logical de…
Immunization Strategies Based on the Overlapping Nodes in Networks with Community Structure
2016
International audience; Understanding how the network topology affects the spread of an epidemic is a main concern in order to develop efficient immunization strategies. While there is a great deal of work dealing with the macroscopic topological properties of the networks, few studies have been devoted to the influence of the community structure. Furthermore, while in many real-world networks communities may overlap, in these studies non-overlapping community structures are considered. In order to gain insight about the influence of the overlapping nodes in the epidemic process we conduct an empirical evaluation of basic deterministic immunization strategies based on the overlapping nodes.…
Measuring Semantic Coherence of a Conversation
2018
Conversational systems have become increasingly popular as a way for humans to interact with computers. To be able to provide intelligent responses, conversational systems must correctly model the structure and semantics of a conversation. We introduce the task of measuring semantic (in)coherence in a conversation with respect to background knowledge, which relies on the identification of semantic relations between concepts introduced during a conversation. We propose and evaluate graph-based and machine learning-based approaches for measuring semantic coherence using knowledge graphs, their vector space embeddings and word embedding models, as sources of background knowledge. We demonstrat…
Semantic HMC for Big Data Analysis
2014
International audience; Analyzing Big Data can help corporations to im-prove their efficiency. In this work we present a new vision to derive Value from Big Data using a Semantic Hierarchical Multi-label Classification called Semantic HMC based in a non-supervised Ontology learning process. We also proposea Semantic HMC process, using scalable Machine-Learning techniques and Rule-based reasoning.
What happens when software developers are (un)happy
2017
The growing literature on affect among software developers mostly reports on the linkage between happiness, software quality, and developer productivity. Understanding happiness and unhappiness in all its components -- positive and negative emotions and moods -- is an attractive and important endeavor. Scholars in industrial and organizational psychology have suggested that understanding happiness and unhappiness could lead to cost-effective ways of enhancing working conditions, job performance, and to limiting the occurrence of psychological disorders. Our comprehension of the consequences of (un)happiness among developers is still too shallow, being mainly expressed in terms of developmen…