Change search
Refine search result
12 1 - 50 of 94
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Artho, Cyrille
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Visser, W.
    Java Pathfinder at SV-COMP 2019 (Competition Contribution)2019In: 25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems conference series, TACAS 2019 held as part of the 22nd European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Springer, 2019, Vol. 11429, p. 224-228Conference paper (Refereed)
    Abstract [en]

    This paper gives a brief overview of Java Pathfinder, or jpf-core. We describe the architecture of JPF, its strengths, and how it was set up for SV-COMP 2019.

  • 2.
    Artho, Cyrille
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Ölveczky, P.C.
    Formal Techniques for Safety-Critical Systems (FTSCS 2015)2018In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 154, p. 1-2Article in journal (Refereed)
  • 3.
    Artho, Cyrille
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Ölveczky, P.C.
    Formal Techniques for Safety-Critical Systems (FTSCS 2016)2019In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 175, p. 35-36Article in journal (Refereed)
  • 4.
    Austrin, Per
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Kaski, Petteri
    Koivisto, Mikko
    Nederlof, Jesper
    Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs2018In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 2, p. 1368-1373Article in journal (Refereed)
    Abstract [en]

    Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

  • 5.
    Balliu, Musard
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Merro, Massimo
    University of Verona.
    Pasqua, Michele
    University of Verona.
    Securing Cross-App Interactions in IoT Platforms2019Conference paper (Refereed)
    Abstract [en]

    IoT platforms enable users to connect various smart devices and online services via reactive apps running on the cloud. These apps, often developed by third-parties, perform simple computations on data triggered by external information sources and actuate the results of computation on external information sinks. Recent research shows that unintended or malicious interactions between the different (even benign) apps of a user can cause severe security and safety risks. These works leverage program analysis techniques to build tools for unveiling unexpected interference across apps for specific use cases. Despite these initial efforts, we are still lacking a semantic framework for understanding interactions between IoT apps. The question of what security policy cross-app interference embodies remains largely unexplored. This paper proposes a semantic framework capturing the essence of cross-app interactions in IoT platforms. The framework generalizes and connects syntactic enforcement mechanisms to bisimulation-based notions of security, thus providing a baseline for formulating soundness criteria of these enforcement mechanisms. Specifically, we present a calculus that models the behavioral semantics of a system of apps executing concurrently, and use it to define desirable semantic policies in the security and safety context of IoT apps. To demonstrate the usefulness of our framework, we define static mechanisms for enforcing crossapp security and safety, and prove them sound with respect to our semantic conditions. Finally, we leverage real-world apps to validate the practical benefits of our policy framework.

  • 6.
    Berglund, Lasse
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Executive Summaries in Software Model Checking2018Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Model checking is a technique used to verify whether a model meets a given specification by exhaustively and automatically checking each reachable state in the model. It is a well-developed technique, but it suffers from some issues, perhaps most importantly the state space explosion problem. Models may contain so many states that must be checked means that the model checking procedure may be intractable. In this thesis we investigate whether procedure summaries can be used to improve the performance of model checking. Procedure summaries are concise representations of parts of a program, such as a function or method. We present a design and an implementation of dynamically generated summaries as an extension of Java PathFinder, a virtual machine executing Java bytecode that is able to model check programs written in Java by backtracking execution, to explore different schedulings etc. We find that our summaries incur an overhead that outweighs the benefits in most cases, but the approach shows promise in certain cases, in particular when stateless model checking is used. We also provide some statistics related to cases when our summaries are applicable that could provide guidance for future work within this field.

  • 7. Bhattacharya, S.
    et al.
    Chakrabarty, D.
    Henzinger, M.
    Na Nongkai, Danupon
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Dynamic algorithms for graph coloring2018In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2018, p. 1-20Conference paper (Refereed)
    Abstract [en]

    We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for ( δ + 1)vertex coloring and (2 δ 1)edge coloring in a graph with maximum degree δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a ( δ+1)-vertex coloring with O(log δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)) δ-vertex coloring with O(polylog δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2 δ)edge coloring with O(log δ) worst-case update time. This improves the recent O( δ)-edge coloring algorithm with Õ ( p δ) worst-case update time [4]. 

  • 8.
    Bhattacharya, Sayan
    et al.
    University of Warwick, UK.
    Na Nongkai, Danupon
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Saranurak, Thatchaphol
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Nondeterminism and Completeness for Dynamic AlgorithmsManuscript (preprint) (Other academic)
  • 9.
    Bilardi, Gianfranco
    et al.
    Univ Padua, Dept Informat Engn, I-35131 Padua, Italy..
    Scquizzato, Michele
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. Univ Padua, Padua, Italy.
    Silvestri, Francesco
    Univ Padua, Dept Informat Engn, I-35131 Padua, Italy..
    A Lower Bound Technique for Communication in BSP2018In: ACM TRANSACTIONS ON PARALLEL COMPUTING, ISSN 2329-4949, Vol. 4, no 3, article id UNSP 14Article in journal (Refereed)
    Abstract [en]

    Communication is a major factor determining the performance of algorithms on current computing systems; it is therefore valuable to provide tight lower bounds on the communication complexity of computations. This article presents a lower bound technique for the communication complexity in the bulk-synchronous parallel (BSP) model of a given class of DAG computations. The derived bound is expressed in terms of the switching potential of a DAG, that is, the number of permutations that the DAG can realize when viewed as a switching network. The proposed technique yields tight lower bounds for the fast Fourier transform (FFT), and for any sorting and permutation network. A stronger bound is also derived for the periodic balanced sorting network, by applying this technique to suitable subnetworks. Finally, we demonstrate that the switching potential captures communication requirements even in computational models different from BSP, such as the I/O model and the LPRAM.

  • 10.
    Bosk, Daniel
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Rodríguez-Cano, Guillermo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Greschbach, Benjamin
    KTH.
    Buchegger, Sonja
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Applying privacy-enhancing technologies: One alternative future of protests2018In: Protests in the Information Age: Social Movements, Digital Practices and Surveillance, Taylor & Francis, 2018, p. 73-94Chapter in book (Refereed)
    Abstract [en]

    While current technologies, such as online social networks, can facilitate coordination and communication for protest organization, they can also endanger political activists when the control over their data is ceded to third parties. For technology to be useful for activism, it needs to be trustworthy and protect the users’ privacy; only then can it be viewed as a potential improvement over more traditional, offline methods. Here, we discuss a selection of such privacy-enhancing technologies from a Computer Science perspective in an effort to open a dialogue and elicit input from other perspectives.

  • 11.
    Brynielsson, Joel
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Message from the EISIC 2017 program chair2017Conference paper (Refereed)
  • 12. Buss, S.
    et al.
    Itsykson, D.
    Knop, A.
    Sokolov, Dmitry
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Reordering rule makes OBDD proof systems stronger2018In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018, p. 161-1624Conference paper (Refereed)
    Abstract [en]

    Atserias, Kolaitis, and Vardi showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD(∧, weakening), simulates CP∗ (Cutting Planes with unary coefficients). We show that OBDD(∧, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring tautologies have polynomial size proofs in the OBDD(∧, weakening) system. The reordering rule allows changing the variable order for OBDDs. We show that OBDD (∧, weakening, reordering) is strictly stronger than OBDD(∧, weakening). This is proved using the Clique-Coloring tautologies, and by transforming tautologies using coded permutations and orification. We also give CNF formulas which have polynomial size OBDD(∧) proofs but require superpolynomial (actually, quasipolynomial size) resolution proofs, and thus we partially resolve an open question proposed by Groote and Zantema. Applying dag-like and tree-like lifting techniques to the mentioned results, we completely analyze which of the systems among CP∗, OBDD(∧), OBDD(∧, reordering), OBDD(∧, weakening) and OBDD (∧, weakening, reordering) polynomially simulate each other. For dag-like proof systems, some of our separations are quasipolynomial and some are exponential; for tree-like systems, all of our separations are exponential.

  • 13.
    Bälter, Olle
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Riese, Emma
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Enoksson, Fredrik
    KTH, School of Industrial Engineering and Management (ITM), Learning.
    Hedin, Björn
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Baltatzis, Alexander
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Josefsson, Pernilla
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    The Challenge of Identifying the Importance of Drivers and Barriers for Implementation of Technology Enhanced Learning2018In: The 11th Pan-Hellenic and International Conference: ICT in Education, 2018, p. 283-290Conference paper (Refereed)
    Abstract [en]

    The potential of technology enhanced learning (TEL) can have both pedagogical and administrative benefits. In a previous study, we investigated the drivers and barriers for TEL in higher education using Force Field Analysis (FFA). In this follow-up study, we collected new data through a questionnaire to a group of pedagogical developers and at a presentation at a university internal conference for teachers. A Kruskal Wallis test was carried out to test if the groups filling out questionnaire deviated from each other in their ranking. A comparison was also done to the scores in the previous study. As a result of this triangulation, deviations were found between ratings for seven of the 20 identified forces. While the assessments of strengths in FFA is debated, we argue that each group’s view is an important component to understand the situation, and triangulation of data is helpful in understanding the different views.

  • 14. Chalermsook, P.
    et al.
    Goswami, M.
    Kozma, L.
    Mehlhorn, K.
    Saranurak, Thatchaphol
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Multi-finger binary search trees2018In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2018, p. 55:1-55:26Conference paper (Refereed)
    Abstract [en]

    We study multi-finger binary search trees (BSTs), a far-reaching extension of the classical BST model, with connections to the well-studied k-server problem. Finger search is a popular technique for speeding up BST operations when a query sequence has locality of reference. BSTs with multiple fingers can exploit more general regularities in the input. In this paper we consider the cost of serving a sequence of queries in an optimal (offline) BST with k fingers, a powerful benchmark against which other algorithms can be measured. We show that the k-finger optimum can be matched by a standard dynamic BST (having a single root-finger) with an O(log k) factor overhead. This result is tight for all k, improving the O(k) factor implicit in earlier work. Furthermore, we describe new online BSTs that match this bound up to a (log k) O (1) factor. Previously only the “one-finger” special case was known to hold for an online BST (Iacono, Langerman, 2016; Cole et al., 2000). Splay trees, assuming their conjectured optimality (Sleator and Tarjan, 1983), would have to match our bounds for all k. Our online algorithms are randomized and combine techniques developed for the k-server problem with a multiplicative-weights scheme for learning tree metrics. To our knowledge, this is the first time when tools developed for the k-server problem are used in BSTs. As an application of our k-finger results, we show that BSTs can efficiently serve queries that are close to some recently accessed item. This is a (restricted) form of the unified property (Iacono, 2001) that was previously not known to hold for any BST algorithm, online or offline.

  • 15.
    Chattopadhyay, Arkadev
    et al.
    Tata Inst Fundamental Res, Mumbai, India..
    Koucky, Michal
    Charles Univ Prague, Prague, Czech Republic..
    Loff, Bruno
    INESC Tec, Porto, Portugal.;Univ Porto, Porto, Portugal..
    Mukhopadhyay, Sagnik
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Simulation Beats Richness: New Data-Structure Lower Bounds2018In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 1013-1020Conference paper (Refereed)
    Abstract [en]

    We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a p x n matrix x over F-2 and Bob gets a vector y is an element of F-2(n). Alice and Bob need to evaluate f (x center dot y) for a Boolean function f : {0, 1}(p) -> {0, 1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C center dot n for Alice and C for Bob, if and only if there exists a deterministic/randomized parity decision tree of cost Theta As applications of this technique, we obtain the following results: (i) The first strong lower-bounds against randomized data-structure schemes for the Vector-Matrix-Vector product problem over F-2. Moreover, our method yields strong lower bounds even when the data-structure scheme has tiny advantage over random guessing. (ii) The first lower bounds against randomized data-structures schemes for two natural Boolean variants of Orthogonal Vector Counting. (iii) We construct an asymmetric communication problem and obtain a deterministic lower-bound for it which is provably better than any lower-bound that may be obtained by the classical Richness Method of Miltersen et al.. This seems to be the first known limitation of the Richness Method in the context of proving deterministic lower bounds.

  • 16. Danglot, Benjamin
    et al.
    Preux, Philippe
    Baudry, Benoit
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Correctness Attraction: A Study of Stability of Software Behavior Under Runtime Perturbation2018In: PROCEEDINGS 2018 IEEE/ACM 40TH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING (ICSE), IEEE , 2018, p. 481-481Conference paper (Refereed)
  • 17. Danglot, Benjamin
    et al.
    Preux, Philippe
    Baudry, Benoit
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. KTH, School of Electrical Engineering and Computer Science (EECS), Centres, Centre for Advanced Software Technology Research (CASTOR).
    Correctness attraction: a study of stability of software behavior under runtime perturbation2018In: Journal of Empirical Software Engineering, ISSN 1382-3256, E-ISSN 1573-7616, Vol. 23, no 4, p. 2086-2119Article in journal (Refereed)
    Abstract [en]

    Can the execution of software be perturbed without breaking the correctness of the output? In this paper, we devise a protocol to answer this question from a novel perspective. In an experimental study, we observe that many perturbations do not break the correctness in ten subject programs. We call this phenomenon “correctness attraction”. The uniqueness of this protocol is that it considers a systematic exploration of the perturbation space as well as perfect oracles to determine the correctness of the output. To this extent, our findings on the stability of software under execution perturbations have a level of validity that has never been reported before in the scarce related work. A qualitative manual analysis enables us to set up the first taxonomy ever of the reasons behind correctness attraction.

  • 18.
    de Rezende, Susanna F.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Lower Bounds and Trade-offs in Proof Complexity2019Doctoral thesis, comprehensive summary (Other academic)
    Abstract [en]

    Propositional proof complexity is a field in theoretical computer science that analyses the resources needed to prove statements. In this thesis, we are concerned about the length of proofs and trade-offs between different resources, such as length and space.

    A classical NP-hard problem in computational complexity is that of determining whether a graph has a clique of size k. We show that for all k ≪ n^(1/4) regular resolution requires length n^Ω(k) to establish that an Erdős–Rényi graph with n vertices and appropriately chosen edge density does not contain a k-clique. In particular, this implies an unconditional lower bound on the running time of state-of-the-artalgorithms for finding a maximum clique.

    In terms of trading resources, we prove a length-space trade-off for the cutting planes proof system by first establishing a communication-round trade-off for real communication via a round-aware simulation theorem. The technical contri-bution of this result allows us to obtain a separation between monotone-AC^(i-1) and monotone-NC^i.

    We also obtain a trade-off separation between cutting planes (CP) with unbounded coefficients and cutting planes where coefficients are at most polynomial in thenumber of variables (CP*). We show that there are formulas that have CP proofs in constant space and quadratic length, but any CP* proof requires either polynomial space or exponential length. This is the first example in the literature showing any type of separation between CP and CP*.

    For the Nullstellensatz proof system, we prove a size-degree trade-off via a tight reduction of Nullstellensatz refutations of pebbling formulas to the reversible pebbling game. We show that for any directed acyclic graph G it holds that G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatzrefutation of the pebbling formula over G in size t + 1 and degree s.

    Finally, we introduce the study of cumulative space in proof complexity, a measure that captures the space used throughout the whole proof and not only the peak space usage. We prove cumulative space lower bounds for the resolution proof system, which can be viewed as time-space trade-offs where, when time is bounded, space must be large a significant fraction of the time.

  • 19.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Meir, Or
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Robere, Robert
    Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling2019In: Proceedings of the 34th Annual Computational Complexity Conference (CCC ’19), 2019, p. 18:1-18:16Conference paper (Other academic)
    Abstract [en]

    We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if an only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.

  • 20.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Meir, Or
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Toniann, Pitassi
    Robere, Robert
    Vinyals, Marc
    Lifting with Simple Gadgets and Applications to Circuit and Proof ComplexityManuscript (preprint) (Other academic)
    Abstract [en]

    We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems:

    • We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients. Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomialline space if coefficients are restricted to be of polynomial magnitude.
    • We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known.

    An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG G over any field coincides exactly with the reversible pebbling price of G. In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.

  • 21. Deryck, M.
    et al.
    Vennekens, J
    Devriendt, Jo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Marynissen, S.
    Legislation in the Knowledge Base Paradigm: Interactive Decision Enactment for Registration Duties2019In: Proceedings - 13th IEEE International Conference on Semantic Computing, ICSC 2019, Institute of Electrical and Electronics Engineers Inc. , 2019, p. 174-177Conference paper (Refereed)
    Abstract [en]

    Recently, a prototype for an interactive decision enactment system for notaries was developed. This prototype follows the Knowledge Base Paradigm (KBP): it consists of purely declarative domain knowledge, to which various logical inference methods can be applied. This paper extends that work in two ways. First, we experimentally validate the claim that the KBP leads to highly maintainable software. Second, we extend the number of additional logical inferences, which allows us to address a number of usability concerns. This provides further evidence for the claim that the KBP is indeed a viable method of developing interactive software systems. The resulting interactive decision enactment prototype is a fully generic system, that can be applied to other domains with minimal effort.

  • 22.
    Deryck, Marjolein
    et al.
    Katholieke Univ Leuven, Dept Comp Sci, Campus De Nayer, St Katelijne Waver, Belgium..
    Devriendt, Jo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Marynissen, Simon
    Katholieke Univ Leuven, Dept Comp Sci, Leuven, Belgium..
    Vennekens, Joost
    Katholieke Univ Leuven, Dept Comp Sci, Campus De Nayer, St Katelijne Waver, Belgium..
    Legislation in the knowledge base paradigm: interactive decision enactment for registration duties2019In: 2019 13TH IEEE INTERNATIONAL CONFERENCE ON SEMANTIC COMPUTING (ICSC), IEEE , 2019, p. 174-177Conference paper (Refereed)
    Abstract [en]

    Recently, a prototype for an interactive decision enactment system for notaries was developed. This prototype follows the Knowledge Base Paradigm (KBP): it consists of purely declarative domain knowledge, to which various logical inference methods can be applied. This paper extends that work in two ways. First, we experimentally validate the claim that the KBP leads to highly maintainable software. Second, we extend the number of additional logical inferences, which allows us to address a number of usability concerns. This provides further evidence for the claim that the KBP is indeed a viable method of developing interactive software systems. The resulting interactive decision enactment prototype is a fully generic system, that can be applied to other domains with minimal effort.

  • 23. Downs, J.
    et al.
    Velupillai, Sumithra
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    George, G.
    Holden, R.
    Kikoler, M.
    Dean, H.
    Fernandes, A.
    Dutta, R.
    Detection of Suicidality in Adolescents with Autism Spectrum Disorders: Developing a Natural Language Processing Approach for Use in Electronic Health Records2017In: Advances in Printing and Media Technology, ISSN 0892-2284, E-ISSN 1942-597X, Vol. 2017, p. 641-649Article in journal (Refereed)
    Abstract [en]

    Over 15% of young people with autism spectrum disorders (ASD) will contemplate or attempt suicide during adolescence. Yet, there is limited evidence concerning risk factors for suicidality in childhood ASD. Electronic health records (EHRs) can be used to create retrospective clinical cohort data for large samples of children with ASD. However systems to accurately extract suicidality-related concepts need to be developed so that putative models of suicide risk in ASD can be explored. We present a systematic approach to 1) adapt Natural Language Processing (NLP) solutions to screen with high sensitivity for reference to suicidal constructs in a large clinical ASD EHR corpus (230,465 documents), and 2) evaluate within a screened subset of 500 patients, the performance of an NLP classification tool for positive and negated suicidal mentions within clinical text. When evaluated, the NLP classification tool showed high system performance for positive suicidality with precision, recall, and F1 scores all > 0.85 at a document and patient level. The application therefore provides accurate output for epidemiological research into the factors contributing to the onset and recurrence of suicidality, and potential utility within clinical settings as an automated surveillance or risk prediction tool for specialist ASD services.

  • 24.
    Durieux, Thomas
    et al.
    INRIA, Lille, France.;Univ Lille, Lille, France..
    Hamadi, Youssef
    Ecole Polytech, Paris, France..
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Fully Automated HTML and Javascript Rewriting for Constructing a Self-healing Web Proxy2018In: 2018 29TH IEEE INTERNATIONAL SYMPOSIUM ON SOFTWARE RELIABILITY ENGINEERING (ISSRE) / [ed] Ghosh, S Natella, R Cukic, B Poston, R Laranjeiro, N, IEEE , 2018, p. 1-12Conference paper (Refereed)
    Abstract [en]

    Over the last few years, the complexity of web applications has increased to provide more dynamic web applications to users. The drawback of this complexity is the growing number of errors in the front-end applications. In this paper, we present BikiniProxy, a novel technique to provide self-healing for the web. BikiniProxy is designed as an HTTP proxy that uses five self-healing strategies to rewrite the buggy HTML and Javascript code. We evaluate BikiniProxy with a new benchmark of 555 reproducible Javascript errors of which 31.76% can be automatically self-healed.

  • 25.
    Durieux, Thomas
    et al.
    Univ Lille, Lille, France.;INRIA, Le Chesnay, France..
    Hamadi, Youssef
    Ecole Polytech, Palaiseau, France..
    Yu, Zhongxing
    Univ Lille, Lille, France.;INRIA, Le Chesnay, France..
    Baudry, Benoit
    KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS.
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Exhaustive Exploration of the Failure-oblivious Computing Search Space2018In: 2018 IEEE 11TH INTERNATIONAL CONFERENCE ON SOFTWARE TESTING, VERIFICATION AND VALIDATION (ICST), IEEE Press, 2018, p. 139-149Conference paper (Refereed)
    Abstract [en]

    High-availability of software systems requires automated handling of crashes in presence of errors. Failure-oblivious computing is one technique that aims to achieve high availability. We note that failure-obliviousness has not been studied in depth yet, and there is very few study that helps understand why failure-oblivious techniques work. In order to make failure-oblivious computing to have an impact in practice, we need to deeply understand failure-oblivious behaviors in software. In this paper, we study, design and perform an experiment that analyzes the size and the diversity of the failure-oblivious behaviors. Our experiment consists of exhaustively computing the search space of 16 field failures of large-scale open-source Java software. The outcome of this experiment is a much better understanding of what really happens when failure-oblivious computing is used, and this opens new promising research directions.

  • 26.
    Elffers, Jan
    et al.
    KTH.
    Cru, Jesús Giráldez
    KTH.
    Gocht, Stephan
    KTH.
    Nordström, Jakob
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Simon, L.
    Seeking practical CDCL insights from theoretical SAT benchmarks2018In: IJCAI International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence , 2018, p. 1300-1308Conference paper (Refereed)
    Abstract [en]

    Over the last decades Boolean satisfiability (SAT) solvers based on conflict-driven clause learning (CDCL) have developed to the point where they can handle formulas with millions of variables. Yet a deeper understanding of how these solvers can be so successful has remained elusive. In this work we shed light on CDCL performance by using theoretical benchmarks, which have the attractive features of being a) scalable, b) extremal with respect to different proof search parameters, and c) theoretically easy in the sense of having short proofs in the resolution proof system underlying CDCL. This allows for a systematic study of solver heuristics and how efficiently they search for proofs. We report results from extensive experiments on a wide range of benchmarks. Our findings include several examples where theory predicts and explains CDCL behaviour, but also raise a number of intriguing questions for further study.

  • 27.
    Elffers, Jan
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Giráldez-Cru, Jakob
    KTH.
    Nordström, Jakob
    KTH.
    Vinyals, M.
    Using combinatorial benchmarks to probe the reasoning power of pseudo-boolean solvers2018In: 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018, Springer, 2018, Vol. 10929, p. 75-93Conference paper (Refereed)
    Abstract [en]

    We study cdcl-cuttingplanes, Open-WBO, and Sat4j, three successful solvers from the Pseudo-Boolean Competition 2016, and evaluate them by performing experiments on crafted benchmarks designed to be trivial for the cutting planes (CP) proof system underlying pseudo-Boolean (PB) proof search but yet potentially tricky for PB solvers. Our experiments demonstrate severe shortcomings in state-of-the-art PB solving techniques. Although our benchmarks have linear-size tree-like CP proofs, and are thus extremely easy in theory, the solvers often perform quite badly even for very small instances. We believe this shows that solvers need to employ stronger rules of cutting planes reasoning. Even some instances that lack not only Boolean but also real-valued solutions are very hard in practice, which indicates that PB solvers need to get better not only at Boolean reasoning but also at linear programming. Taken together, our results point to several crucial challenges to be overcome in the quest for more efficient pseudo-Boolean solvers, and we expect that a further study of our benchmarks could shed more light on the potential and limitations of current state-of-the-art PB solving.

  • 28. Felderer, M.
    et al.
    Gurov, Dilian
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Huisman, M.
    Lisper, B.
    Schlick, R.
    Formal methods in industrial practice - Bridging the gap (track summary)2018In: 8th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation, ISoLA 2018, Springer, 2018, Vol. 11247, p. 77-81Conference paper (Refereed)
    Abstract [en]

    Already for many decades, formal methods are considered to be the way forward to help the software industry to make more reliable and trustworthy software. However, despite this strong belief, and many individual success stories, no real change in industrial software development seems to happen. In fact, the software industry is moving fast forward itself, and the gap between what formal methods can achieve, and the daily software development practice does not seem to get smaller (and might even be growing).

  • 29. Frezza, S.
    et al.
    Daniels, M.
    Pears, Arnold Neville
    KTH, School of Industrial Engineering and Management (ITM), Learning.
    Cajander, Å.
    Kann, Viggo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Kapoor, A.
    McDermott, R.
    Peters, A. -K
    Sabin, M.
    Wallace, C.
    Modelling competencies for computing education beyond 2020: A research based approach to defining competencies in the computing disciplines2018In: Annual Conference on Innovation and Technology in Computer Science Education, ITiCSE, Association for Computing Machinery , 2018, p. 148-174Conference paper (Refereed)
    Abstract [en]

    How might the content and outcomes of tertiary education programmes be described and analysed in order to understand how they are structured and function? To address this question we develop a framework for modelling graduate competencies linked to tertiary degree programmes in the computing disciplines. While the focus of our work is computing the framework is applicable to education more broadly. The work presented here draws upon the pioneering curricular document for information technology (IT2017), curricular competency frameworks, other related documents such as the software engineering competency model (SWECOM), the Skills Framework for the Information Age (SFIA), current research in competency models, and elicitation workshop results from recent computing conferences. The aim is to inform the ongoing Computing Curricula (CC2020) project, an endeavour supported by the Association for Computing Machinery (ACM) and the IEEE Computer Society. We develop the Competency Learning Framework (CoLeaF), providing an internationally relevant tool for describing competencies. We argue that this competency based approach is well suited for constructing learning environments and assists degree programme architects in dealing with the challenge of developing, describing and including competencies relevant to computer and IT professionals. In this paper we demonstrate how the CoLeaF competency framework can be applied in practice, and though a series of case studies demonstrate its effectiveness and analytical power as a tool for describing and comparing degree programmes in the international higher education landscape.

  • 30.
    Garg, Ankit
    et al.
    Microsoft Res, Redmond, WA 98052 USA..
    Goos, Mika
    Harvard Univ, Cambridge, MA 02138 USA..
    Kamath, Pritish
    MIT, Cambridge, MA 02139 USA..
    Sokolov, Dmitry
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Monotone Circuit Lower Bounds from Resolution2018In: STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING / [ed] Diakonikolas, I Kempe, D Henzinger, M, ASSOC COMPUTING MACHINERY , 2018, p. 902-911Conference paper (Refereed)
    Abstract [en]

    For any unsatisfiable CNF formula F that is hard to refute in the Resolution proof system, we show that a gadget-composed version of F is hard to refute in any proof system whose lines are computed by efficient communication protocols-or, equivalently, that a monotone function associated with F has large monotone circuit complexity. Our result extends to monotone real circuits, which yields new lower bounds for the Cutting Planes proof system.

  • 31.
    Gedin, Emanuel
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Hardness of showing hardness of the minimum circuit size problem2018Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    The problem of finding the smallest size of a circuit that computes a given boolean function, usually referred to as the minimum circuit size problem (MCSP), has been studied for many years but it is still unknown whether or not the problem is NP-hard. With this in mind we study properties of potential reductions to this problem. The reductions in focus are local natural reductions which has been common in other well-known proofs of NP-hardness. We present a generalized method that shows the existence of an algorithm solving any problem which has a local natural reduction to MCSP. In particular we show that if the decision problem of distinguishing satisfiable 3-SAT instances from those where at most 7/8 + o(1) of the clauses can be satisfied has a reduction to MCSP where any arbitrary bit of the output can be computed in O(n1 - ε) time for any ε > 0 then k-SAT can be solved by a circuit of depth 3 and size 2o(n).

  • 32.
    Glassey, Richard
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Haller, Philipp
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Wiggberg, Mattias
    KTH, School of Industrial Engineering and Management (ITM), Industrial Economics and Management (Dept.), Industrial Management.
    Agile and adaptive learning via the ECK-model in the software development academy2018In: CEUR Workshop Proceedings, CEUR-WS , 2018, Vol. 2193Conference paper (Refereed)
    Abstract [en]

    This paper reports the learning management experiences within an intensive three-month education that helps newly arrived in Sweden find work as IT professionals. The creation of the Software Development Academy was motivated by the migration crisis and the wider need to help integrate newcomers into the social and professional landscape. Despite having relevant skills and training, many have had their studies and careers disrupted either by conflict, or simply by lacking the profile and networks needed to restart their careers in a new country. With limited resources and time, combined with the intensive pace and diverse student backgrounds, the program faces many challenges that threaten its success. To mitigate these challenges, an agile and adaptive approach was adopted that employs TEL techniques and pedagogical concepts to ensure the program is continuously improving via short iterations and tight feedback loops. The program has just finished its third offering and has continuously improved through weekly collection of knowledge, confidence, and experience data that guide interventions and reactions as they are needed. The experience, process, and model presented here may inspire and benefit other courses with similar profiles and challenges.

  • 33.
    Guanciale, Roberto
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Protecting Instruction Set Randomization from Code Reuse Attacks2018In: 23rd Nordic Conference on Secure IT Systems, NordSec 2018, Springer Verlag , 2018, p. 421-436Conference paper (Refereed)
    Abstract [en]

    Instruction Set Randomization (ISR) prevents code injection by randomizing the instruction encoding used by programs, thus preventing an attacker from preparing a payload that can be injected in a victim. In this paper we show that code-reuse attacks can be used to circumvent existing ISR techniques and we demonstrate these attacks on an ARMv7 CPU that has been extended with ISR support. To counter this treat, we propose a new ISR that does not have the same vulnerabilities as the existing solutions, imposes moderate decryption cost, does not require additional memory per instruction, and affords efficient random access to the encrypted code. These properties enable efficient hardware implementation of our solution. In order to evaluate our proposal, we implement the new ISR in a hardware simulator and we compare its overhead with respect to existing ISR. 

  • 34.
    Guarnieri, Marco
    et al.
    IMDEA Software Institute.
    Balliu, Musard
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Schoepe, Daniel
    Chalmers University of Technology.
    Basin, David
    ETH Zurich.
    Sabelfeld, Andrei
    Chalmers University of Technology.
    Information-Flow Control for Database-backed Applications2019Conference paper (Refereed)
    Abstract [en]

    Securing database-backed applications requires tracking information across the application program and the database together, since securing each component in isolation may still result in an overall insecure system. Current research extends language-based techniques with models capturing the database’s behavior. This research, however, relies on simplistic database models, which ignore security-relevant features that may leak sensitive information. We propose a novel security monitor for database-backed applications. Our monitor tracks fine-grained dependencies between variables and database tuples by leveraging database theory concepts like disclosure lattices and query determinacy. It also accounts for a realistic database model that supports security-critical  constructs like triggers and dynamic policies. The monitor automatically synthesizes program-level code that replicates the behavior of database features like triggers, thereby tracking information flows inside the database. We also introduce symbolic tuples, an efficient approximation of dependency-tracking over disclosure lattices. We implement our monitor for SCALA programs and demonstrate its effectiveness on four case studies.

  • 35.
    Haller, Philipp
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Vasconcelos, Vasco Thudichum
    Univ Lisbon, Lisbon, Portugal..
    Special issue on the tenth Workshop on Programming Language Approaches to Concurrency- and Communication-cEntric Software2019In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 106, p. 196-197Article in journal (Refereed)
  • 36.
    Havtun, Hans
    et al.
    KTH, School of Industrial Engineering and Management (ITM), Energy Technology, Applied Thermodynamics and Refrigeration.
    Kann, Viggo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Carlsund, Ninni
    KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, NA.
    Wingård, Lars
    KTH, School of Industrial Engineering and Management (ITM), Production Engineering.
    Continuous assessment: Time and effort well spent for students and teachers?2019In: KTH SoTL 2019, 2019Conference paper (Refereed)
  • 37.
    Hedin, Björn
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Kann, Viggo
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Improving Study Skills by Combining a Study Skill Module and Repeated Reflection Seminars2019In: Education Research International, ISSN 2090-4002, E-ISSN 2090-4010, article id 9739854Article in journal (Refereed)
    Abstract [en]

    If students have a broad spectrum of study skills, learning will likely be positively affected, since they can adapt the way they learn in different situations. Such study skills can be learned in, for example, learning-to-learn courses. Several studies of such courses have been done over the years, but few of these have been carried out in longitudinal naturalistic settings, where the effect has been evaluated over several years in nonexperimental settings. In this paper, we present a novel approach for learning study skills, as a part of a course running over three years. The course starts with a learning-to-learn module, followed by 11 follow-ups that include, among other things, peer discussions about learning strategies with the aim of promoting self-regulated learning. This evaluation shows which study skills the students were most interested in trying, how successful they were in continuing to use the study skills, and which effects the students believed the study skills had after trying them. No significant change was found in how satisfied the students were with their overall study technique immediately after the initial module, but in the long term, 78% of the students believed the course had promoted their ability to analyze and adapt their study habits. We conclude that our approach could be a useful way to get the students to improve their repertoire and use of study skills, and we believe that the students also will improve general self-regulated learning skills.

  • 38.
    Holmqvist, Carl
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Opinion analysis of microblogs for stock market prediction2018Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    This degree project investigates if a company’s stock price development can be predicted using the general opinion expressed in tweets about the company. The project starts off with the model from a previous project and then tries to improve the results using state-of-the-art neural network sentiment analysis and more tweet data. This project also attempts to perform hourly predictions along with daily predictions in order to investigate the method further.

    The results show a decrease in accuracy compared to the previous project. The results also indicate that the neural network sentiment analysis improves the accuracy of the stock price development when compared to the baseline model under comparable conditions.

  • 39. Iatropoulos, G.
    et al.
    Herman, Pawel
    KTH, School of Electrical Engineering and Computer Science (EECS), Computational Science and Technology (CST).
    Lansner, Anders
    KTH, School of Electrical Engineering and Computer Science (EECS), Computational Science and Technology (CST).
    Karlgren, Jussi
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. Gavagai, Slussplan 9, Stockholm, Sweden.
    Larsson, M.
    Olofsson, J. K.
    The language of smell: Connecting linguistic and psychophysical properties of odor descriptors2018In: Cognition, ISSN 0010-0277, E-ISSN 1873-7838, Vol. 178, p. 37-49Article in journal (Refereed)
    Abstract [en]

    The olfactory sense is a particularly challenging domain for cognitive science investigations of perception, memory, and language. Although many studies show that odors often are difficult to describe verbally, little is known about the associations between olfactory percepts and the words that describe them. Quantitative models of how odor experiences are described in natural language are therefore needed to understand how odors are perceived and communicated. In this study, we develop a computational method to characterize the olfaction-related semantic content of words in a large text corpus of internet sites in English. We introduce two new metrics: olfactory association index (OAI, how strongly a word is associated with olfaction) and olfactory specificity index (OSI, how specific a word is in its description of odors). We validate the OAI and OSI metrics using psychophysical datasets by showing that terms with high OAI have high ratings of perceived olfactory association and are used to describe highly familiar odors. In contrast, terms with high OSI have high inter-individual consistency in how they are applied to odors. Finally, we analyze Dravnieks's (1985) dataset of odor ratings in terms of OAI and OSI. This analysis reveals that terms that are used broadly (applied often but with moderate ratings) tend to be olfaction-unrelated and abstract (e.g., “heavy” or “light”; low OAI and low OSI) while descriptors that are used selectively (applied seldom but with high ratings) tend to be olfaction-related (e.g., “vanilla” or “licorice”; high OAI). Thus, OAI and OSI provide behaviorally meaningful information about olfactory language. These statistical tools are useful for future studies of olfactory perception and cognition, and might help integrate research on odor perception, neuroimaging, and corpus-based linguistic models of semantic organization.

  • 40. Ive, J.
    et al.
    Viani, N.
    Chandran, D.
    Bittar, A.
    Velupillai, Sumithra
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. King's College London, IoPPN, London, SE5 8AF, United Kingdom.
    KCL-Health-NLP@CLEF eHealth 2018 Task 1: ICD-10 coding of French and Italian death certificates with character-level convolutional neural networks2018In: CEUR Workshop Proceedings, CEUR-WS , 2018, Vol. 2125Conference paper (Refereed)
    Abstract [en]

    In this paper we describe the participation of the KCL-Health-NLP team in the CLEF eHealth 2018 lab, specifically Task 1: Multilingual Information Extraction-ICD10 coding. The task involves the automatic coding of causes of death in death certificates in French, Italian and Hungarian according to the ICD-10 taxonomy. Choosing to work on the two Romance languages, we treated the task as a sequence-to-sequence prediction problem. Our system has an encoder-decoder architecture, with convolutional neural networks based on character em-beddings as encoders and recurrent neural network decoders. Our hypothesis was that a character-level representation would allow our model to generalise across two genealogically related languages. Results obtained by pre-training our Italian model on the French data set confirmed this intuition. We also explored the impact of character-level features extracted from dictionary-matched ICD codes. We obtained F-measures of 0.72/0.64 and 0.78 on the French aligned/raw and Italian raw internal test data, respectively. On the blind test set released by the task organisers, our top results were 0.65/0.52 and 0.69 F-measure, respectively.

  • 41.
    Josefsson, Pernilla
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Baltatzis, Alexander
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Bälter, Olof
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Enoksson, Fredrik
    KTH, School of Industrial Engineering and Management (ITM).
    Hedin, Björn
    KTH, School of Electrical Engineering and Computer Science (EECS), Media Technology and Interaction Design, MID.
    Riese, Emma
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    DRIVERS AND BARRIERS FOR PROMOTING TECHNOLOGY ENHANCED LEARNING IN HIGHER EDUCATION2018In: 12TH INTERNATIONAL TECHNOLOGY, EDUCATION AND DEVELOPMENT CONFERENCE (INTED) / [ed] Chova, LG Martinez, AL Torres, IC, IATED-INT ASSOC TECHNOLOGY EDUCATION & DEVELOPMENT , 2018, p. 4576-4584Conference paper (Refereed)
    Abstract [en]

    The paper presents a study were drivers and barriers for increased use of Technology Enhanced Learning in higher education were identified. The method included focus groups with Faculty Pedagogical Developers at KTH Royal Institute of Technology, followed by a Force Field Analysis. Ten drivers and ten barriers were identified, and are presented in this paper. The most significant drivers found were: collegial discussions, increased automatization, Technology enhanced learning support for the teachers (to assist exploration), tech savvy students and engagement among faculty. The most significant barriers identified were: unclear return on time investment, insufficient funding for purchases and lack of central decisions. The analysis also revealed that some drivers and barriers could act both ways. One example is locally developed systems which are understood to be drivers when it comes to solving (local) problems and encouraging experimentation with IT systems, but when these local systems are cancelled due to lack of funding, or for example replaced by centralized systems, they discourage use and development. The findings constitute a foundation for future discussions about change processes to increase utilization of technology enhanced learning in higher education.

  • 42.
    Karlgren, Jussi
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Regulation of Unpredictable Effects of Decision Making Systems is Non-trivial2018In: 50 Years of Law and IT: The Swedish Law and Informatics Research Institute 1968-2018 / [ed] Peter Wahlgren, Stockholm: The Stockholm University Law Faculty , 2018, p. 127-132Chapter in book (Other academic)
    Abstract [en]

    Technical advances are rapidly delegating decision making in newarenas of human activity to information systems through theapplication of new classification mechanisms from machine learningresearch. How to manage technology-induced change and its effectsthrough legislative systems in order to encourage and supportbehaviour and activities which is desirable and beneficial to thepublic good and dissuade from such which is not is non-trivial. Ingeneral, legislation to cover new technical advances will be based onexisting technology and existing practice. This may seen reasonablebasis to build from and adds legitimacy to regulation and itsapplication, but regulation of technology too often stumbles at thebalancing line between under- standing and promoting future changeproductively and protecting past practice. This paper argues that morethought must be put into the aims of regulatory activities.

  • 43.
    Karlgren, Jussi
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. Gavagai, Stockholm, Sweden.
    Esposito, L.
    Gratton, C.
    Kanerva, P.
    Authorship profiling without using topical information: Notebook for PAN at CLEF 20182018In: CLEF 2018 Working Notes, CEUR-WS , 2018, Vol. 2125Conference paper (Refereed)
    Abstract [en]

    This paper describes an experiment made for the PAN 2018 shared task on author profiling. The task is to distinguish female from male authors of microblog posts published on Twitter using no extraneous information except what is in the posts; this experiment focusses on using non-topical information from the posts, rather than gender differences in referential content.

  • 44.
    Karlgren, Jussi
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Kanerva, P.
    Hyperdimensional utterance spaces2018In: CEUR Workshop Proceedings, CEUR-WS , 2018, Vol. 2167, p. 29-35Conference paper (Refereed)
    Abstract [en]

    Human language has a large and varying number of features, both lexical items and constructions, which interact to represent various aspects of communicative information. High-dimensional semantic spaces have proven useful and effective for aggregating and processing lexical information for many language processing tasks. This paper describes a hyperdimensional processing model for language data, a straightforward extension of models previously used for words to handling utterance or text level information. A hyperdimensional model is able to represent a broad range of linguistic and extra-linguistic features in a common integral framework which is suitable as a bridge between symbolic and continuous representations, as an encoding scheme for symbolic information and as a basis for feature space exploration. This paper provides an overview of the framework and an example of how it is used in a pilot experiment.

  • 45. Karlsson, Olof
    et al.
    Haller, Philipp
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Extending Scala with records: Design, implementation, and evaluation2018In: Scala 2018 Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, Association for Computing Machinery (ACM), 2018, p. 72-82Conference paper (Refereed)
  • 46.
    Khosrowjerdi, Hojat
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Learning-based Testing for Automotive Embedded Systems: A requirements modeling and Fault injection study2019Licentiate thesis, comprehensive summary (Other academic)
    Abstract [en]

    This thesis concerns applications of learning-based testing (LBT) in the automotive domain. In this domain, LBT is an attractive testing solution, since it offers a highly automated technology to conduct safety critical requirements testing based on machine learning. Furthermore, as a black-box testing technique, LBT can manage the complexity of modern automotive software applications such as advanced driver assistance systems. Within the automotive domain, three relevant software testing questions for LBT are studied namely: effectiveness of requirements modeling, learning efficiency and error discovery capabilities.

    Besides traditional requirements testing, this thesis also considers fault injection testing starting from the perspective of automotive safety standards, such as ISO26262. For fault injection testing, a new methodology is developed based on the integration of LBT technologies with virtualized hardware emulation to implement both test case generation and fault injection. This represents a novel application of machine learning to fault injection testing. Our approach is flexible, non-intrusive and highly automated. It can therefore provide a complement to traditional fault injection methodologies such as hardware-based fault injection.

  • 47.
    Khosrowjerdi, Hojat
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Meinke, Karl
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Learning-Based testing for autonomous systems using spatial and temporal requirements2018In: MASES 2018 - Proceedings of the 1st International Workshop on Machine Learning and Software Engineering in Symbiosis, co-located with ASE 2018, Association for Computing Machinery, Inc , 2018, p. 6-15Conference paper (Refereed)
    Abstract [en]

    Cooperating cyber-physical systems-of-systems (CO-CPS) such as vehicle platoons, robot teams or drone swarms usually have strict safety requirements on both spatial and temporal behavior. Learning-based testing is a combination of machine learning and model checking that has been successfully used for black-box requirements testing of cyber-physical systems-of-systems. We present an overview of research in progress to apply learning-based testing to evaluate spatio-temporal requirements on autonomous systems-of-systems through modeling and simulation.

  • 48.
    Khosrowjerdi, Hojat
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Meinke, Karl
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Rasmusson, Andreas
    Scania CV AB, S-15187 Sodertalje, Sweden..
    Virtualized-Fault Injection Testing: a Machine Learning Approach2018In: 2018 IEEE 11TH INTERNATIONAL CONFERENCE ON SOFTWARE TESTING, VERIFICATION AND VALIDATION (ICST), IEEE , 2018, p. 297-308Conference paper (Refereed)
    Abstract [en]

    We introduce a new methodology for virtualized fault injection testing of safety critical embedded systems. This approach fully automates the key steps of test case generation, fault injection and verdict construction. We use machine learning to reverse engineer models of the system under test. We use model checking to generate test verdicts with respect to safety requirements formalised in temporal logic. We exemplify our approach by implementing a tool chain based on integrating the QEMU hardware emulator, the GNU debugger GDB and the LBTest requirements testing tool. This tool chain is then evaluated on two industrial safety critical applications from the automotive sector.

  • 49.
    Kitamura, T.
    et al.
    Japan.
    Maissonneuve, Q.
    Japan.
    Choi, E. -H
    Japan.
    Artho, Cyrille
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Gargantini, A.
    Italy.
    Optimal Test Suite Generation for Modified Condition Decision Coverage Using SAT Solving2018In: 37th International Conference on Computer Safety, Reliability and Security, SAFECOMP 2018, Springer, 2018, p. 123-138Conference paper (Refereed)
    Abstract [en]

    Boolean expressions occur frequently in descriptions of computer systems, but they tend to be complex and error-prone in complex systems. The modified condition decision coverage (MCDC) criterion in system testing is an important testing technique for Boolean expression, as its usage mandated by safety standards such as DO-178 [1] (avionics) and ISO26262 [2] (automotive). In this paper, we develop an algorithm to generate optimal MCDC test suites for Boolean expressions. Our algorithm is based on SAT solving and generates minimal MCDC test suites. Experiments on a real-world avionics system confirm that the technique can construct minimal MCDC test suites within reasonable times, and improves significantly upon prior techniques.

  • 50. Kozma, László
    et al.
    Saranurak, Thatchaphol
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Smooth Heaps and a Dual View of Self-adjusting Data Structures2018In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM , 2018, p. 801-814Conference paper (Refereed)
    Abstract [en]

    We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures (Allen, Munro, 1978; Sleator, Tarjan, 1983; Fredman, Sedgewick, Sleator, Tarjan, 1986; Wilber, 1989; Fredman, 1999; Iacono, Özkan, 2014). Roughly speaking, we map an arbitrary heap algorithm within a broad and natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e. the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures. There is a rich theory of dynamic optimality for BSTs (i.e. the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature (e.g. Pettie; 2005, 2008). Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps. On the algorithmic side, we obtain a new, simple and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal (Lucas, 1988; Munro, 2000; Demaine et al., 2009). Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms. Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g. it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a “power-of-two-choices” type of heuristic. For the smooth heap we obtain instance-specific upper bounds, with applications in adaptive sorting, and we see it as a promising candidate for the long-standing question of a simpler alternative to Fibonacci heaps. The paper is dedicated to Raimund Seidel on occasion of his sixtieth birthday.

12 1 - 50 of 94
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf