Browsing by Subject "COMPUTATION"

Sort by: Order: Results:

Now showing items 1-9 of 9
  • 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.
  • Alviano, Mario; Dodaro, Carmine; Järvisalo, Matti; Maratea, Marco; Previti, Alessandro (2018)
    Answer Set Programming (ASP) is a logic-based knowledge representation framework, supporting-among other reasoning modes-the central task of query answering. In the propositional case, query answering amounts to computing cautious consequences of the input program among the atoms in a given set of candidates, where a cautious consequence is an atom belonging to all stable models. Currently, the most efficient algorithms either iteratively verify the existence of a stable model of the input program extended with the complement of one candidate, where the candidate is heuristically selected, or introduce a clause enforcing the falsity of at least one candidate, so that the solver is free to choose which candidate to falsify at any time during the computation of a stable model. This paper introduces new algorithms for the computation of cautious consequences, with the aim of driving the solver to search for stable models discarding more candidates. Specifically, one of such algorithms enforces minimality on the set of true candidates, where different notions of minimality can be used, and another takes advantage of unsatisfiable cores computation. The algorithms are implemented in WASP, and experiments on benchmarks from the latest ASP competitions show that the new algorithms perform better than the state of the art.
  • He, Chen; Micallef, Luana; He, Liye; Peddinti, Gopal; Aittokallio, Tero; Jacucci, Giulio (2021)
    Understanding the quality of insight has become increasingly important with the trend of allowing users to post comments during visual exploration, yet approaches for qualifying insight are rare. This article presents a case study to investigate the possibility of characterizing the quality of insight via the interactions performed. To do this, we devised the interaction of a visualization tool—MediSyn—for insight generation. MediSyn supports five types of interactions: selecting, connecting, elaborating, exploring, and sharing. We evaluated MediSyn with 14 participants by allowing them to freely explore the data and generate insights. We then extracted seven interaction patterns from their interaction logs and correlated the patterns to four aspects of insight quality. The results show the possibility of qualifying insights via interactions. Among other findings, exploration actions can lead to unexpected insights; the drill-down pattern tends to increase the domain values of insights. A qualitative analysis shows that using domain knowledge to guide exploration can positively affect the domain value of derived insights. We discuss the study’s implications, lessons learned, and future research opportunities.
  • Wirz, Lukas N.; Dimitrova, Maria; Fliegl, Heike; Sundholm, Dage (2018)
    The topology of twisted molecular rings is characterized by the linking number, which is equal to the sum of the twist-a local property of the molecular frame-and the writhe-a global parameter, which represents the bending of the molecular ring. In this work, we investigate a number of cyclic all-trans C40H40 annulenes with varying twisting numbers for a given linking number and their dications. The aromatic character is assessed by calculating ring-current strength susceptibilities using the gauge-including magnetically induced currents (GIMIC) method, which makes it possible to conduct a systematic study of the relation between the topology and aromaticity of twisted molecules. We found that the aromatic properties of the investigated Mobius twisted molecules are not only dependent on the linking number as previously suggested but also depend strongly on the partitioning of the linking number into the twist and writhe contributions.
  • Hiltunen, Tuukka; Ritala, Juha; Siro, Topi; Harju, Ari (2013)
  • The CMS collaboration; Sirunyan, A. M.; Eerola, P.; Kirschenmann, H.; Pekkanen, J.; Voutilainen, M.; Havukainen, J.; Heikkilä, J.K.; Järvinen, T.; Karimäki, V.; Kinnunen, R.; Lampén, T.; Lassila-Perini, K.; Laurila, S.; Lehti, S.; Lindén, T.; Luukka, P.; Siikonen, H.; Tuominen, E.; Tuominiemi, J.; Tuuva, T. (2018)
    A search for narrow vector resonances decaying into quark-antiquark pairs is presented. The analysis is based on data collected in proton-proton collisions at root s = 13 TeV with the CMS detector at the LHC, corresponding to an integrated luminosity of 35.9 fb(-1). The hypothetical resonance is produced with sufficiently high transverse momentum that its decay products are merged into a single jet with two-prong substructure. A signal would be identified as a peak over a smoothly falling background in the distribution of the invariant mass of the jet, using novel jet substructure techniques. No evidence for such a resonance is observed within the mass range of 50-300 GeV. Upper limits at 95% confidence level are set on the production cross section, and presented in a mass-coupling parameter space. The limits further constrain simplified models of dark matter production involving a mediator interacting between quarks and dark matter particles through a vector or axial-vector current. In the framework of these models, the results are the most sensitive to date, extending for the first time the search region to masses below 100 GeV.
  • The CMS collaboration; Sirunyan, A. M.; Eerola, P.; Kirschenmann, H.; Pekkanen, J.; Voutilainen, M.; Havukainen, J.; Heikkilä, J. K.; Järvinen, T.; Karimäki, V.; Kinnunen, R.; Lampén, T.; Lassila-Perini, K.; Laurila, S.; Lehti, S.; Lindén, T.; Luukka, P.; Mäenpää, T.; Siikonen, H.; Tuominen, E.; Tuominiemi, J.; Tuuva, T. (2018)
    Searches for resonances decaying into pairs of jets are performed using proton-proton collision data collected at root s = 13 TeV corresponding to an integrated luminosity of up to 36 fb(-1). A low-mass search, for resonances with masses between 0.6 and 1.6 TeV, is performed based on events with dijets reconstructed at the trigger level from calorimeter information. A high-mass search, for resonances with masses above 1.6 TeV, is performed using dijets reconstructed offline with a particle-flow algorithm. The dijet mass spectrum is well described by a smooth parameterization and no evidence for the production of new particles is observed. Upper limits at 95% confidence level are reported on the production cross section for narrow resonances with masses above 0.6 TeV. In the context of specific models, the limits exclude string resonances with masses below 7.7 TeV, scalar diquarks below 7.2 TeV, axigluons and colorons below 6.1 TeV, excited quarks below 6.0 TeV, color-octet scalars below 3.4 TeV, W' bosons below 3.3 TeV, Z' bosons below 2.7 TeV, Randall-Sundrum gravitons below 1.8 TeV and in the range 1.9 to 2.5 TeV, and dark matter mediators below 2.6 TeV. The limits on both vector and axial-vector mediators, in a simplified model of interactions between quarks and dark matter particles, are presented as functions of dark matter particle mass and coupling to quarks. Searches are also presented for broad resonances, including for the first time spin-1 resonances with intrinsic widths as large as 30% of the resonance mass. The broad resonance search improves and extends the exclusions of a dark matter mediator to larger values of its mass and coupling to quarks.
  • The CMS collaboration; Sirunyan, A. M.; Eerola, P.; Kirschenmann, H.; Pekkanen, J.; Voutilainen, M.; Havukainen, J.; Heikkilä, J. K.; Järvinen, T.; Karimäki, V.; Kinnunen, R.; Lampén, T.; Lassila-Perini, K.; Laurila, S.; Lehti, S.; Lindén, T.; Luukka, P.; Mäenpää, T.; Siikonen, H.; Tuominen, E.; Tuominiemi, J.; Tuuva, T. (2018)
    search is presented for physics beyond the standard model, based on measurements of dijet angular distributions in proton-proton collisions at root s = 13 TeV. The data collected with the CMS detector at the LHC correspond to an integrated luminosity of 35.9 fb(-1). The observed distributions, corrected to particle level, are found to be in agreement with predictions from perturbative quantum chromodynamics that include electroweak corrections. Constraints are placed on models containing quark contact interactions, extra spatial dimensions, quantum black holes, or dark matter, using the detector-level distributions. In a benchmark model where only left-handed quarks participate, contact interactions are excluded at the 95% confidence level up to a scale of 12.8 or 17.5 TeV, for destructive or constructive interference, respectively. The most stringent lower limits to date are set on the ultraviolet cutoff in the Arkani-Hamed-Dimopoulos-Dvali model of extra dimensions. In the Giudice-Rattazzi-Wells convention, the cutoff scale is excluded up to 10.1 TeV. The production of quantum black holes is excluded for masses below 5.9 and 8.2 TeV, depending on the model. For the first time, lower limits between 2.0 and 4.6 TeV are set on the mass of a dark matter mediator for (axial-)vector mediators, for the universal quark coupling g(q) = 1.0.
  • The CMS collaboration; Sirunyan, A. M.; Eerola, P.; Kirschenmann, H.; Pekkanen, J.; Voutilainen, M.; Havukainen, J.; Heikkilä, J. K.; Järvinen, T.; Karimäki, V.; Kinnunen, R.; Lampén, T.; Lassila-Perini, K.; Laurila, S.; Lehti, S.; Lindén, T.; Luukka, P.; Mäenpää, T.; Siikonen, H.; Tuominen, E.; Tuominiemi, J.; Tuuva, T. (2019)
    A search has been performed for heavy resonances decaying to ZZ or ZW in 2l2q final states, with two charged leptons (l = e, mu) produced by the decay of a Z boson, and two quarks produced by the decay of a W or Z boson. The analysis is sensitive to resonances with masses in the range from 400 to 4500 GeV. Two categories are defined based on the merged or resolved reconstruction of the hadronically decaying vector boson, optimized for high- and low-mass resonances, respectively. The search is based on data collected during 2016 by the CMS experiment at the LHC in proton-proton collisions with a center-of-mass energy of root s = 13 TeV, corresponding to an integrated luminosity of 35.9 fb(-1). No excess is observed in the data above the standard model background expectation. Upper limits on the production cross section of heavy, narrow spin-1 and spin-2 resonances are derived as a function of the resonance mass, and exclusion limits on the production of W' bosons and bulk graviton particles are calculated in the framework of the heavy vector triplet model and warped extra dimensions, respectively.