Browsing by Subject "COMPLEXITY"

Sort by: Order: Results:

Now showing items 1-20 of 27
  • Kangas, Kustaa; Koivisto, Mikko; Salonen, Sami (2019)
    We investigate the problem of computing the number of linear extensions of a given n-element poset whose cover graph has treewidth t. We present an algorithm that runs in time $${\tilde{O}}(n^{t+3})$$O~(nt+3)for any constant t; the notation $${\tilde{O}}$$O~hides polylogarithmic factors. Our algorithm applies dynamic programming along a tree decomposition of the cover graph; the join nodes of the tree decomposition are handled by fast multiplication of multivariate polynomials. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters n and t alone: fixing these parameters leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. We compare two approaches to select an efficient tree decomposition: one is to include additional features of the tree decomposition to build a more accurate, heuristic cost function; the other approach is to fit a statistical regression model to collected running time data. Both approaches are shown to yield a tree decomposition that typically is significantly more efficient than a random optimal-width tree decomposition.
  • Baumeister, Dorothea; Järvisalo, Matti; Neugebauer, Daniel; Niskanen, Andreas; Rothe, Jörg (2021)
    A Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central formal model for the study of computational aspects of argumentation in AI. Credulous and skeptical acceptance of arguments in a given AF are well-studied problems both in terms of theoretical analysis-especially computational complexity-and the development of practical decision procedures for the problems. However, AFs make the assumption that all attacks between arguments are certain (i.e., present attacks are known to exist, and missing attacks are known to not exist), which can in various settings be a restrictive assumption. A generalization of AFs to incomplete AFs was recently proposed as a formalism that allows the representation of both uncertain attacks and uncertain arguments in AFs. In this article, we explore the impact of allowing for modeling such uncertainties in AFs on the computational complexity of natural generalizations of acceptance problems to incomplete AFs under various central AF semantics. Complementing the complexity-theoretic analysis, we also develop the first practical decision procedures for all of the NP-hard variants of acceptance in incomplete AFs. In terms of complexity analysis, we establish a full complexity landscape, showing that depending on the variant of acceptance and property/semantics, the complexity of acceptance in incomplete AFs ranges from polynomial-time decidable to completeness for Sigma(p)(3). In terms of algorithms, we show through an extensive empirical evaluation that an implementation of the proposed decision procedures, based on boolean satisfiability (SAT) solving, is effective in deciding variants of acceptance under uncertainties. We also establish conditions for what type of atomic changes are guaranteed to be redundant from the perspective of preserving extensions of completions of incomplete AFs, and show that the results allow for considerably improving the empirical efficiency of the proposed SAT-based counterexample-guided abstraction refinement algorithms for acceptance in incomplete AFs for problem variants with complexity beyond NP. (C) 2021 The Authors. Published by Elsevier B.V.
  • Morris, Rebecca J.; Gripenberg, Sofia; Lewis, Owen T.; Roslin, Tomas (2014)
  • Durand, Arnaud; Hannula, Miika; Kontinen, Juha; Meier, Arne; Virtema, Jonni (2018)
    We define a variant of team semantics called multiteam semantics based on multisets and study the properties of various logics in this framework. In particular, we define natural probabilistic versions of inclusion and independence atoms and certain approximation operators motivated by approximate dependence atoms of Vaananen.
  • Hagolani, Pascal F.; Zimm, Roland; Marin-Riera, Miquel; Salazar-Ciudad, Isaac (2019)
    Embryonic development involves gene networks, extracellular signaling, cell behaviors (cell division, adhesion, etc.) and mechanical interactions. How should these be coordinated to lead to complex and robust morphologies? To explore this question, we randomly wired genes and cell behaviors into a huge number of networks in EmbryoMaker. EmbryoMaker is a computational model of animal development that simulates how the 3D positions of cells, i.e. morphology, change over time due to such networks. We found that any gene network can lead to complex morphologies if this activates cell behaviors over large regions of the embryo. Importantly, however, for such complex morphologies to be robust to noise, gene networks should include cell signaling that compartmentalizes the embryo into small regions where cell behaviors are regulated differently. If, instead, cell behaviors are equally regulated over large regions, complex but non-robust morphologies arise. We explain how compartmentalization enhances robustness and why it is a general feature of animal development. Our results are consistent with theories proposing that robustness evolved by the co-option of gene networks and extracellular cell signaling in early animal evolution.
  • Sinnemäki, Kaius (2014)
    Linguistic typological preferences have often been linked to cognitive processing preferences but often without recourse to typologically relevant experiments on cognitive processing. This article reviews experimental work on the possible parallels between preferences in cognitive processing and language typology. I summarize the main theoretical accounts of the processing‐typology connection and show that typological distributions arise diachronically from preferred paths of language change, which may be affected by the degree to which alternative structures are preferred (e.g., easier) in acquisition or usage. The surveyed experimental evidence shows that considerable support exists for many linguistic universals to reflect preferences in cognitive processing. Artificial language learning experiments emerge as a promising method for researching the processing‐typology connection, as long as its limitations are taken into account. I further show that social and cultural differences in cognition may have an effect on typological distributions and that to account for this variation a multidisciplinary approach to the processing‐typology connection has to be developed. Lastly, since the body of experimental research does not adequately represent the linguistic diversity of the world's languages, it remains as an urgent task for the field to better account for this diversity in future work.
  • Kivimäki, Mika; Walker, Keenan A.; Pentti, Jaana; Nyberg, Solja; Mars, Nina; Vahtera, Jussi; Suominen, Sakari B.; Lallukka, Tea; Rahkonen, Ossi; Pietiläinen, Olli; Koskinen, Aki; Vaananen, Ari; Kalsi, Jatinderpal K.; Goldberg, Marcel; Zins, Marie; Alfredsson, Lars; Westerholm, Peter J. M.; Knutsson, Anders; Theorell, Tores; Ervasti, Jenni; Oksanen, Tuula; Sipilä, Pyry N.; Tabak, Adam G.; Ferrie, Jane E.; Williams, Stephen A.; Livingston, Gill; Gottesman, Rebecca F.; Singh-Manoux, Archana; Zetterberg, Henrik; Lindbohm, Joni (2021)
    OBJECTIVES To examine the association between cognitively stimulating work and subsequent risk of dementia and to identify protein pathways for this association. DESIGN Multicohort study with three sets of analyses. SETTING United Kingdom, Europe, and the United States. PARTICIPANTS Three associations were examined: cognitive stimulation and dementia risk in 107 896 participants from seven population based prospective cohort studies from the IPD-Work consortium (individual participant data meta-analysis in working populations); cognitive stimulation and proteins in a random sample of 2261 participants from one cohort study; and proteins and dementia risk in 13 656 participants from two cohort studies. MAIN OUTCOME MEASURES Cognitive stimulation was measured at baseline using standard questionnaire instruments on active versus passive jobs and at baseline and over time using a job exposure matrix indicator. 4953 proteins in plasma samples were scanned. Follow-up of incident dementia varied between 13.7 to 30.1 years depending on the cohort. People with dementia were identified through linked electronic health records and repeated clinical examinations. RESULTS During 1.8 million person years at risk, 1143 people with dementia were recorded. The risk of dementia was found to be lower for participants with high compared with low cognitive stimulation at work (crude incidence of dementia per 10 000 person years 4.8 in the high stimulation group and 7.3 in the low stimulation group, age and sex adjusted hazard ratio 0.77, 95% confidence interval 0.65 to 0.92, heterogeneity in cohort specific estimates I2=0%, P=0.99). This association was robust to additional adjustment for education, risk factors for dementia in adulthood (smoking, heavy alcohol consumption, physical inactivity, job strain, obesity, hypertension, and prevalent diabetes at baseline), and cardiometabolic diseases (diabetes, coronary heart disease, stroke) before dementia diagnosis (fully adjusted hazard ratio 0.82, 95% confidence interval 0.68 to 0.98). The risk of dementia was also observed during the first 10 years of follow-up (hazard ratio 0.60, 95% confidence interval 0.37 to 0.95) and from year 10 onwards (0.79, 0.66 to 0.95) and replicated using a repeated job exposure matrix indicator of cognitive stimulation (hazard ratio per 1 standard deviation increase 0.77, 95% confidence interval 0.69 to 0.86). In analysis controlling for multiple testing, higher cognitive stimulation at work was associated with lower levels of proteins that inhibit central nervous system axonogenesis and synaptogenesis: slit homologue 2 (SLIT2, fully adjusted r3 -0.34, P(0.001), carbohydrate sulfotransferase 12 (CHSTC, fully adjusted r3 -0.33, P(0.001), and peptidyl-glycine alpha-amidating monooxygenase (AMD, fully adjusted r3 -0.32, P(0.001). These proteins were associated with increased dementia risk, with the fully adjusted hazard ratio per 1 SD being 1.16 (95% confidence interval 1.05 to 1.28) for SLIT2, 1.13 (1.00 to 1.27) for CHSTC, and 1.04 (0.97 to 1.13) for AMD. CONCLUSIONS The risk of dementia in old age was found to be lower in people with cognitively stimulating jobs than in those with non-stimulating jobs. The findings that
  • Räsänen, Aleksi (2021)
    Cross-scale interactions affect resilience in a wide array of social systems such as flood risk management, but it has been argued that studies of such interactions remain limited. Based on qualitative interviews, quantitative surveys, and policy document analysis, I employed the panarchy framework in an analysis of temporal changes and cross-scale interactions in flood risk management at the local and regional scale in Rovaniemi, in Finnish Lapland. The results revealed that administrative co-operation in flood preparedness has functioned well in Rovaniemi in recent decades and few changes have been made to it. Nevertheless, flood defense measures have been the subject of a persistent and dynamic conflict, which has been locked in a polarized phase. Among local residents? approaches to flood risk management, there have been few changes in preparedness, although administrative actors have emphasized communication and self-preparedness in recent years. I discuss how the cross-scale mismatches have contributed to hinder the flood risk management, sharpen the conflict over flood defense measures, and keep the local residents? level of preparedness low.
  • Korhonen, Tuukka; Järvisalo, Matti (AAAI Press, 2020)
    AAAI Conference on Artificial Intelligence
  • Erjansola, Ari-Matti; Lipponen, Jukka; Vehkalahti, Kimmo; Aula, Hanna-Mari; Pirttila-Backman, Anna-Maija (2021)
    Brand logos are a fundamental part of the corporate visual identity, and their reception has been vigorously researched. The focus has been on the visual traits of the logo and their effect on the reception process, whereas little attention has been paid to how the logo becomes part of the brand. This article narrows this research gap in investigating how a new logo is evaluated, how the perception evolves, and what underlying dimensions emerge from the reception process. We adopted a longitudinal free-association approach and followed the qualitative and quantitative changes in logo associations among first-year students at Aalto University as it was going through a merger accompanied with a radical visual-identity redesign. We show how the new logo faced initial resistance before it became a source of positive brand associations, and how it became anchored in the university ' s corporate identity. We argue that logo evaluations span three dimensions: they may be congruent or incongruent with the disposition of the individual toward the change: they may be congruent or incongruent with the visual preferences of the individual; and they may be based on the visuals of the logo or on its identity-expressing capabilities.
  • Rizzi, Romeo; Cairo, Massimo; Mäkinen, Veli; Tomescu, Alexandru I.; Valenzuela, Daniel (2019)
    Covering alignment problems arise from recent developments in genomics; so called pan-genome graphs are replacing reference genomes, and advances in haplotyping enable full content of diploid genomes to be used as basis of sequence analysis. In this paper, we show that the computational complexity will change for natural extensions of alignments to pan-genome representations and to diploid genomes. More broadly, our approach can also be seen as a minimal extension of sequence alignment to labelled directed acyclic graphs (labeled DAGs). Namely, we show that finding a covering alignment of two labeled DAGs is NP-hard even on binary alphabets. A covering alignment asks for two paths R-1 (red) and G(1) (green) in DAG D-1 and two paths R-2 (red) and G(2) (green) in DAG D-2 that cover the nodes of the graphs and maximize the sum of the global alignment scores: asosp(R-1), sp(R-2)) + asosp(G(1)), sp(G(2))), where sp(P) is the concatenation of labels on the path P. Pair-wise alignment of haplotype sequences forming a diploid chromosome can be converted to a two-path coverable labelled DAG, and then the covering alignment models the similarity of two diploids over arbitrary recombinations. We also give a reduction to the other direction, to show that such a recombination-oblivious diploid alignment is NP-hard on alphabets of size 3.
  • Kulmuni, J.; Westram, A. M. (2017)
    The possibility of intrinsic barriers to gene flow is often neglected in empirical research on local adaptation and speciation with gene flow, for example when interpreting patterns observed in genome scans. However, we draw attention to the fact that, even with gene flow, divergent ecological selection may generate intrinsic barriers involving both ecologically selected and other interacting loci. Mechanistically, the link between the two types of barriers may be generated by genes that have multiple functions (i.e., pleiotropy), and/or by gene interaction networks. Because most genes function in complex networks, and their evolution is not independent of other genes, changes evolving in response to ecological selection can generate intrinsic barriers as a by-product. A crucial question is to what extent such by-product barriers contribute to divergence and speciation-that is whether they stably reduce gene flow. We discuss under which conditions by-product barriers may increase isolation. However, we also highlight that, depending on the conditions (e.g., the amount of gene flow and the strength of selection acting on the intrinsic vs. the ecological barrier component), the intrinsic incompatibility may actually destabilize barriers to gene flow. In practice, intrinsic barriers generated as a by-product of divergent ecological selection may generate peaks in genome scans that cannot easily be interpreted. We argue that empirical studies on divergence with gene flow should consider the possibility of both ecological and intrinsic barriers. Future progress will likely come from work combining population genomic studies, experiments quantifying fitness and molecular studies on protein function and interactions.
  • Duplouy, Anne; Nair, Abhilash; Nyman, Toshka; van Nouhuys, Saskya (2021)
    Population bottlenecks associated with founder events strongly impact the establishment and genetic makeup of populations. In addition to their genotype, founding individuals also bring along parasites, as well as symbionts that can manipulate the phenotype of their host, affecting the host population establishment, dynamics and evolution. Thus, to understand introduction, invasion, and spread, we should identify the roles played by accompanying symbionts. In 1991, the parasitoid wasp, Hyposoter horticola, and its associated hyperparasitoid were accidentally introduced from the main angstrom land islands, Finland, to an isolated island in the archipelago, along with their host, the Glanville fritillary butterfly. Though the receiving island was unoccupied, the butterfly was present on some of the small islands in the vicinity. The three introduced species have persisted locally ever since. A strain of the endosymbiotic bacterium Wolbachia has an intermediate prevalence in the parasitoid H. horticola across the main angstrom land population. The infection increases its susceptibility of to hyperparasitism. We investigated the establishment and spread of the parasitoid, along with patterns of prevalence of its symbiont using 323 specimens collected between 1992 and 2013, from five localities across angstrom land, including the source and introduced populations. Using 14 microsatellites and one mitochondrial marker, we suggest that the relatively diverse founding population and occasional migration between islands might have facilitated the persistence of all isolated populations, despite multiple local population crashes. We also show that where the hyperparasitoid is absent, and thus selection against infected wasp genotypes is relaxed, there is near-fixation of Wolbachia.
  • LaMere, Kelsey; Mäntyniemi, Samu; Vanhatalo, Jarno; Haapasaari, Päivi (2020)
    Eliciting stakeholders’ mental models is an important participatory modeling (PM) tool for building systems knowledge, a frequent challenge in natural resource management. Therefore, mental models constitute a valu-able source of information, making it imperative to document them in detail, while preserving the integrity of stakeholders’ beliefs. We propose a methodology, the Rich Elicitation Approach (REA), which combines direct and indirect elicitation techniques to meet these goals. We describe the approach in the context of the effects of climate change on Baltic salmon. The REA produced holistic depictions of mental models, with more variables and causal relationships per diagram than direct elicitation alone, thus providing a solid knowledge base on which to begin PM studies. The REA was well received by stakeholders and fulfilled the substantive, normative, instrumental, and educational functions of PM. However, motivating stakeholders to confirm the accuracy of their models during the verification stage of the REA was challenging.
  • Alexandridis, Nikolaos; Marion, Glenn; Chaplin-Kramer, Rebecca; Dainese, Matteo; Ekroos, Johan; Grab, Heather; Jonsson, Mattias; Karp, Daniel S.; Meyer, Carsten; O'Rourke, Megan E.; Pontarp, Mikael; Poveda, Katja; Seppelt, Ralf; Smith, Henrik G.; Martin, Emily A.; Clough, Yann (2021)
    Natural control of invertebrate crop pests has the potential to complement or replace conventional insecticide based practices, but its mainstream application is hampered by predictive unreliability across agroecosystems. Inconsistent responses of natural pest control to changes in landscape characteristics have been attributed to ecological complexity and system-specific conditions. Here, we review agroecological models and their potential to provide predictions of natural pest control across agricultural landscapes. Existing models have used a multitude of techniques to represent specific crop-pest-enemy systems at various spatiotemporal scales, but less wealthy regions of the world are underrepresented. A realistic representation of natural pest control across systems appears to be hindered by a practical trade-off between generality and realism. Nonetheless, observations of context-sensitive, trait-mediated responses of natural pest control to land-use gradients indicate the potential of ecological models that explicitly represent the underlying mechanisms. We conclude that modelling natural pest control across agroecosystems should exploit existing mechanistic techniques towards a framework of contextually bound generalizations. Observed similarities in causal relationships can inform the functional grouping of diverse agroecosystems worldwide and the development of the respective models based on general, but context-sensitive, ecological mechanisms. The combined use of qualitative and quantitative techniques should allow the flexible integration of empirical evidence and ecological theory for robust predictions of natural pest control across a wide range of agroecological contexts and levels of knowledge availability. We highlight challenges and promising directions towards developing such a general modelling framework.
  • Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko (2017)
    We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2((d-1)n/2). Our techniques generalize an algebraic approach studied in various recent works. (c) 2017 Elsevier Inc. All rights reserved.
  • Aulbach, Matthias; Harjunen, Ville Johannes; Spape, Michiel; Knittle, Keegan; Haukkala, Ari; Ravaja, Niklas (2020)
    Go/No‐Go tasks, which require participants to inhibit automatic responses to images of palatable foods, have shown diagnostic value in quantifying food‐related impulses. Moreover, they have shown potential for training to control impulsive eating. To test the hypothesis that training modulates early neural markers of response inhibition, the current study investigated how the N2 event‐related brain potential to high‐ and low‐calorie food images changes along Go‐/No‐Go training and how the N2 is related to later eating behavior. 50 healthy adults, (mBMI = 23.01) first completed a food Go/No‐Go task in which high‐ and low‐calorie food images were accompanied by Go‐and No‐Go‐cues with equal frequency. Participants then completed a training block in which high‐calorie foods were predominantly paired with a No‐Go cue and the low‐calorie foods with a Go cue, followed by a block with reversed coupling (order of the training blocks counterbalanced between participants). After each training, there was a snacking opportunity during which calorie intake was measured. Against our preregistered hypotheses, the N2‐amplitudes were not significantly affected by the calorie‐content and there was no training‐related modulation in the N2. In addition , food intake was not influenced by the preceding training blocks and the N2 amplitude did not predict the food intake. Our study suggests that the link between N2 obtained in a food‐related Go/No‐Go task and impulse control is not clear‐cut and may be limited to specific task characteristics. The results are of high importance as they question the previously assumed mechanism of Go/No‐Go training in food‐related inhibitory control.
  • Yli-Jyrä, Anssi Mikael (Springer-Verlag, 2012)
    Arc contractions in syntactic dependency graphs can be used to decide which graphs are trees. The paper observes that these contractions can be expressed with weighted finite-state transducers (weighted FST) that operate on string-encoded trees. The observation gives rise to a finite-state parsing algorithm that computes the parse forest and extracts the best parses from it. The algorithm is customizable to functional and bilexical dependency parsing, and it can be extended to non-projective parsing via a multi-planar encoding with prior results on high recall. Our experiments support an analysis of projective parsing according to which the worst-case time complexity of the algorithm is quadratic to the sentence length, and linear to the overlapping arcs and the number of functional categories of the arcs. The results suggest several interesting directions towards efficient and highprecision dependency parsing that takes advantage of the flexibility and the demonstrated ambiguity-packing capacity of such a parser.
  • Uvarov, Pavel; Kajander, Tommi; Airaksinen, Matti S. (2014)
  • Knaapila, Antti; Laaksonen, Oskar; Virtanen, Markus; Yang, Baoru; Lagstrom, Hanna; Sandell, Mari (2017)
    The primary dimension of odor is pleasantness, which is associated with a multitude of factors. We investigated how the pleasantness, familiarity, and identification of spice odors were associated with each other and with the use of the respective spice, overall use of herbs, and level of food neophobia. A total of 126 adults (93 women, 33 men; age 25-61 years, mean 39 years) rated the odors from 12 spices (oregano, anise, rosemary, mint, caraway, sage, thyme, cinnamon, fennel, marjoram, garlic, and clove) for pleasantness and familiarity, and completed a multiple-choice odor identification. Data on the use of specific spices, overall use of herbs, and Food Neophobia Scale score were collected using an online questionnaire. Familiar odors were mostly rated as pleasant (except garlic), whereas unfamiliar odors were rated as neutral (r = 0.63). We observed consistent and often significant trends that suggested the odor pleasantness and familiarity were positively associated with the correct odor identification, consumption of the respective spice, overall use of herbs, and food neophilia. Our results suggest that knowledge acquisition through repetitive exposure to spice odor with active attention may gradually increase the odor pleasantness within the framework set by the chemical characteristics of the aroma compound. (C) 2016 Elsevier Ltd. All rights reserved.