Search results for "Computer Science::Information Retrieval"
showing 10 items of 171 documents
Quantum Queries on Permutations
2015
K. Iwama and R. Freivalds considered query algorithms where the black box contains a permutation. Since then several authors have compared quantum and deterministic query algorithms for permutations. It turns out that the case of \(n\)-permutations where \(n\) is an odd number is difficult. There was no example of a permutation problem where quantization can save half of the queries for \((2m+1)\)-permutations if \(m\ge 2\). Even for \((2m)\)-permutations with \(m\ge 2\), the best proved advantage of quantum query algorithms is the result by Iwama/Freivalds where the quantum query complexity is \(m\) but the deterministic query complexity is \((2m-1)\). We present a group of \(5\)-permutati…
Vagueness and Roughness
2008
The paper proposes a new formal approach to vagueness and vague sets taking inspirations from Pawlak's rough set theory. Following a brief introduction to the problem of vagueness, an approach to conceptualization and representation of vague knowledge is presented from a number of different perspectives: those of logic, set theory, algebra, and computer science. The central notion of the vague set, in relation to the rough set, is defined as a family of sets approximated by the so called lower and upper limits. The family is simultaneously considered as a family of all denotations of sharp terms representing a suitable vague term, from the agent's point of view. Some algebraic operations on…
A Structural $\mathcal{ SHOIN(D)}$ Ontology Model for Change Modelling
2013
This paper presents a complete structural ontology model suited for change modelling on \(\mathcal{ SHOIN(D)}\) ontologies. The application of this model is illustrated along the paper through the description of an ontology example inspired by the UOBM ontology benchmark and its evolution.
The Elephant in the Machine: Proposing a New Metric of Data Reliability and its Application to a Medical Case to Assess Classification Reliability
2020
In this paper, we present and discuss a novel reliability metric to quantify the extent a ground truth, generated in multi-rater settings, as a reliable basis for the training and validation of machine learning predictive models. To define this metric, three dimensions are taken into account: agreement (that is, how much a group of raters mutually agree on a single case)
Vectors of Pairwise Item Preferences
2019
Neural embedding has been widely applied as an effective category of vectorization methods in real-world recommender systems. However, its exploration of users’ explicit feedback on items, to create good quality user and item vectors is still limited. Existing neural embedding methods only consider the items that are accessed by the users, but neglect the scenario when a user gives high or low rating to a particular item. In this paper, we propose Pref2Vec, a method to generate vector representations of pairwise item preferences, users and items, which can be directly utilized for machine learning tasks. Specifically, Pref2Vec considers users’ pairwise item preferences as elementary units. …
The Impact of the Mass Spectrum of Lenses in Quasar Microlensing Studies. Constraints on a Mixed Population of Primordial Black Holes and Stars
2020
We show that quasar microlensing magnification statistics induced by a population of point microlenses distributed according to a mass-spectrum can be very well approximated by that of a single-mass, "monochromatic", population. When the spatial resolution (physically defined by the source size) is small as compared with the Einstein radius, the mass of the monochromatic population matches the geometric mean of the mass-spectrum. Otherwise, the best-fit mass can be larger. Taking into account the degeneracy with the geometric mean, the interpretation of quasar microlensing observations under the hypothesis of a mixed population of primordial black holes and stars, makes the existence of a s…
Euclid preparation XV. Forecasting cosmological constraints for the Euclid and CMB joint analysis
2022
The combination and cross-correlation of the upcoming $Euclid$ data with cosmic microwave background (CMB) measurements is a source of great expectation since it will provide the largest lever arm of epochs, ranging from recombination to structure formation across the entire past light cone. In this work, we present forecasts for the joint analysis of $Euclid$ and CMB data on the cosmological parameters of the standard cosmological model and some of its extensions. This work expands and complements the recently published forecasts based on $Euclid$-specific probes, namely galaxy clustering, weak lensing, and their cross-correlation. With some assumptions on the specifications of current and…
Grover’s Algorithm with Errors
2013
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size n in \(O(\sqrt{n})\) queries, while any classical algorithm needs O(n) queries [3].
Understanding Quantum Algorithms via Query Complexity
2017
Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we su…
Locality of order-invariant first-order formulas
1998
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.