Search results for " Complexity"
showing 10 items of 623 documents
DeepEva: A deep neural network architecture for assessing sentence complexity in Italian and English languages
2021
Abstract Automatic Text Complexity Evaluation (ATE) is a research field that aims at creating new methodologies to make autonomous the process of the text complexity evaluation, that is the study of the text-linguistic features (e.g., lexical, syntactical, morphological) to measure the grade of comprehensibility of a text. ATE can affect positively several different contexts such as Finance, Health, and Education. Moreover, it can support the research on Automatic Text Simplification (ATS), a research area that deals with the study of new methods for transforming a text by changing its lexicon and structure to meet specific reader needs. In this paper, we illustrate an ATE approach named De…
Discovering representative models in large time series databases
2004
The discovery of frequently occurring patterns in a time series could be important in several application contexts. As an example, the analysis of frequent patterns in biomedical observations could allow to perform diagnosis and/or prognosis. Moreover, the efficient discovery of frequent patterns may play an important role in several data mining tasks such as association rule discovery, clustering and classification. However, in order to identify interesting repetitions, it is necessary to allow errors in the matching patterns; in this context, it is difficult to select one pattern particularly suited to represent the set of similar ones, whereas modelling this set with a single model could…
A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY
2013
Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bound…
Learning-Graph-Based Quantum Algorithm for k-distinctness
2012
We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error. This improves the previous $O(n^{k/(k+1)})$-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an $O(\sqrt{n}\alpha^{1/6})$ algorithm for the graph collision problem where $\alpha$ is the independence number of the graph.
Dynamic Gaussian Graphical Models for Modelling Genomic Networks
2014
After sequencing the entire DNA for various organisms, the challenge has become understanding the functional interrelatedness of the genome. Only by understanding the pathways for various complex diseases can we begin to make sense of any type of treatment. Unfortunately, decyphering the genomic network structure is an enormous task. Even with a small number of genes the number of possible networks is very large. This problem becomes even more difficult, when we consider dynamical networks. We consider the problem of estimating a sparse dynamic Gaussian graphical model with \(L_1\) penalized maximum likelihood of structured precision matrix. The structure can consist of specific time dynami…
Matching beer with food : pairing principles, underlying mechanisms and a focus on aromatic similarity
2018
Pairing between beer and dishes emerges as a new trend in France. Beer promoters or gastronomy professionals need to offer high-quality advices in terms of beer and food pairing to their customers. Within this context, the objective of the research was to identify pairing principles and to better understand the underlying perceptual mechanisms. Determinants of food and beverage pairing were first analysed from experts’ discourses. Results showed that food and beverage pairings are governed by perceptual, conceptual and affective features, related to physio-chemical, perceptual and cognitive processes. Experts often mentioned “Aromatic Similarity” as one of the main pairing principles. This …
Visual category representations in the infant brain
2021
SUMMARYVisual categorization is a human core cognitive capacity1,2that depends on the development of visual category representations in the infant brain3–7. However, the exact nature of infant visual category representations and their relationship to the corresponding adult form remains unknown8. Our results clarify the nature of visual category representations from electroencephalography (EEG) data in 6- to 8-month-old infants and their developmental trajectory towards adult maturity in the key characteristics of temporal dynamics2,9, representational format10–12, and spectral properties13,14. Temporal dynamics change from slowly emerging, developing representations in infants to quickly e…
Fast Algorithms for Pseudoarboricity
2015
The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, hav…
Optimal standalone data center renewable power supply using an offline optimization approach
2022
Abstract Because of the increasing energy consumption of data centers and their C O 2 emissions, the ANR DATAZERO2 project aims to design autonomous data centers running solely on local renewable energy coupled with storage devices to overcome the intermittency issue. In order to optimize the use of renewable energy and storage devices, a MILP solver is usually in charge of assigning the power to be supplied to the data center. However, in order to reduce the computation time and make the approach scalable, it would be more appropriate to use a polynomial time algorithm. This paper aims at showing and proving that it is possible to provide an optimal power profile via a deterministic algori…
Efficient lower and upper bounds of the diagonal-flip distance between triangulations
2006
There remains today an open problem whether the rotation distance between binary trees or equivalently the diagonal-flip distance between triangulations can be computed in polynomial time. We present an efficient algorithm for computing lower and upper bounds of this distance between a pair of triangulations.