Change search
Refine search result
12 1 - 50 of 70
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.
    Ö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)
  • 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 2016)2019In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 175, p. 35-36Article in journal (Refereed)
  • 3.
    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.

  • 4.
    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.

  • 5. 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]. 

  • 6.
    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)
  • 7.
    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.

  • 8.
    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.

  • 9. 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.

  • 10.
    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.

  • 11.
    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.

  • 12. 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)
  • 13. 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: 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.

  • 14.
    de Rezende, Susanna F.
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Meir, Or
    Nordström, Jakob
    Robere, Robert
    Nullstellensatz Size-Degree Trade-offs from Reversible PebblingManuscript (preprint) (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.

  • 15.
    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.

  • 16.
    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.

  • 17.
    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.

  • 18. 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).

  • 19. 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.

  • 20.
    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.

  • 21.
    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).

  • 22.
    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.

  • 23.
    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. 

  • 24.
    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)
  • 25.
    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.

  • 26.
    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.

  • 27. 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.

  • 28. 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.

  • 29.
    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.

  • 30.
    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.

  • 31.
    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.

  • 32. 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)
  • 33.
    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.

  • 34.
    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.

  • 35.
    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.

  • 36. 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.

  • 37.
    Li, Xiyu
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. Royal Inst Technol, Sch Engn Sci Chem, Dept Theoret Chem & Biol, S-10691 Stockholm, Sweden..
    Duan, Sai
    KTH, School of Engineering Sciences in Chemistry, Biotechnology and Health (CBH), Theoretical Chemistry and Biology. Royal Inst Technol, Sch Engn Sci Chem, Dept Theoret Chem & Biol, S-10691 Stockholm, Sweden..
    Liu, Haichun
    KTH, School of Engineering Sciences in Chemistry, Biotechnology and Health (CBH), Theoretical Chemistry and Biology. Royal Inst Technol, Sch Engn Sci Chem, Dept Theoret Chem & Biol, S-10691 Stockholm, Sweden..
    Chen, Guanying
    Harbin Inst Technol, Sch Chem Engn & Technol, Harbin 150001, Heilongjiang, Peoples R China..
    Luo, Yi
    KTH, Superseded Departments (pre-2005), Biotechnology. KTH, Superseded Departments (pre-2005), Chemistry. KTH, School of Engineering Sciences in Chemistry, Biotechnology and Health (CBH), Theoretical Chemistry and Biology. Royal Inst Technol, Sch Engn Sci Chem, Dept Theoret Chem & Biol, S-10691 Stockholm, Sweden..
    Ågren, Hans
    Royal Inst Technol, Sch Engn Sci Chem, Dept Theoret Chem & Biol, S-10691 Stockholm, Sweden..
    Mechanism for the Extremely Efficient Sensitization of Yb(3+)Luminescence in CsPbCl3 Nanocrystals2019In: Journal of Physical Chemistry Letters, ISSN 1948-7185, E-ISSN 1948-7185, Vol. 10, no 3, p. 487-492Article in journal (Refereed)
    Abstract [en]

    Rare earth ion (RE3+)-doped inorganic CsPbX3 (X = Cl or Cl/Br) nanocrystals have been presented as promising materials for applications in solar-energy conversion technology. An extremely efficient sensitization of Yb3+ luminescence in CsPbCl3 nanoparticles (NCs) was very recently demonstrated where quantum cutting is responsible for the performance of photoluminescence quantum yields over 100% (T. J. Milstein, et al. Nano Letters 2018, 18, 3792). In the present work, based on the cubic phase of inorganic perovskite, we seek to obtain atom-level insight into the basic mechanisms behind these observations in order to boost the further development of RE3+-doped CsPbX3 NCs for optoelectronics. In our calculations of cubic crystal structure, we do not find any energy level formed in the middle of the band gap, which disfavors a mechanism of stepwise energy transfer from the perovskite host to two Yb3+ ions. Our work indicates that the configuration with "right-angle" Yb3+-V-Pb-Yb3+ couple is most likely to form in Yb3+-doped CsPbCl3. Associated with this "right-angle" couple, the "right-angle" Pb atom with trapped excited states would localize the photogenerated electrons and act as the energy donor in a quantum cutting process, which achieves simultaneous sensitization of two neighboring Yb3+ ions.

  • 38.
    Lindner, Andreas
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Guanciale, Roberto
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Metere, R.
    TrABin: Trustworthy analyses of binaries2019In: Science of Computer Programming, ISSN 0167-6423, E-ISSN 1872-7964, Vol. 174, p. 72-89Article in journal (Refereed)
    Abstract [en]

    Verification of microkernels, device drivers, and crypto routines requires analyses at the binary level. In order to automate these analyses, in the last years several binary analysis platforms have been introduced. These platforms share a common design: the adoption of hardware-independent intermediate representations, a mechanism to translate architecture dependent code to this representation, and a set of architecture independent analyses that process the intermediate representation. The usage of these platforms to verify software introduces the need for trusting both the correctness of the translation from binary code to intermediate language (called transpilation) and the correctness of the analyses. Achieving a high degree of trust is challenging since the transpilation must handle (i) all the side effects of the instructions, (ii) multiple instruction encodings (e.g. ARM Thumb), and (iii) variable instruction length (e.g. Intel). Similarly, analyses can use complex transformations (e.g. loop unrolling) and simplifications (e.g. partial evaluation) of the artifacts, whose bugs can jeopardize correctness of the results. We overcome these problems by developing a binary analysis platform on top of the interactive theorem prover HOL4. First, we formally model a binary intermediate language and we prove correctness of several supporting tools (i.e. a type checker). Then, we implement two proof-producing transpilers, which respectively translate ARMv8 and CortexM0 programs to the intermediate language and generate a certificate. This certificate is a HOL4 proofdemonstrating correctness of the translation. As demonstrating analysis, we implement a proof-producing weakest precondition generator, which can be used to verify that a given loop-free program fragment satisfies a contract. Finally, we use an AES encryption implementation to benchmark our platform.

  • 39.
    Lu, Yunyue
    et al.
    East China Univ Sci & Technol, Sch Chem & Mol Engn, Key Lab Adv Mat, Shanghai 200237, Peoples R China.;East China Univ Sci & Technol, Sch Chem & Mol Engn, Inst Fine Chem, Shanghai 200237, Peoples R China..
    Song, Heli
    East China Univ Sci & Technol, Sch Chem & Mol Engn, Key Lab Adv Mat, Shanghai 200237, Peoples R China.;East China Univ Sci & Technol, Sch Chem & Mol Engn, Inst Fine Chem, Shanghai 200237, Peoples R China..
    Li, Xin
    KTH, School of Electrical Engineering and Computer Science (EECS), Centres, Centre for High Performance Computing, PDC.
    Ågren, Hans
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Liu, Qingyun
    Shandong Univ Sci & Technol, Coll Chem & Environm Engn, Qingdao 266510, Peoples R China..
    Zhang, Jiwei
    Donghua Univ, Coll Chem Chem Engn & Biotechnol, Shanghai 201620, Peoples R China..
    Zhang, Xuan
    Donghua Univ, Coll Chem Chem Engn & Biotechnol, Shanghai 201620, Peoples R China..
    Xie, Yongshu
    East China Univ Sci & Technol, Sch Chem & Mol Engn, Key Lab Adv Mat, Shanghai 200237, Peoples R China.;East China Univ Sci & Technol, Sch Chem & Mol Engn, Inst Fine Chem, Shanghai 200237, Peoples R China..
    Multiply Wrapped Porphyrin Dyes with a Phenothiazine Donor: A High Efficiency of 11.7% Achieved through a Synergetic Coadsorption and Cosensitization Approach2019In: ACS Applied Materials and Interfaces, ISSN 1944-8244, E-ISSN 1944-8252, Vol. 11, no 5, p. 5046-5054Article in journal (Refereed)
    Abstract [en]

    Photocurrent (J) and photovoltage (Vac) are two important parameters for dye-sensitized solar cells (DSSCs) to achieve high power conversion efficiencies (PCEs). Herein, we synthesize four novel porphyrin dyes, XW36 XW39, using an N-phenyl-substituted phenothiazine donor to pursue higher PCE. For XW36 and XW37, the N-phenyl group is wrapped with two ortho-alkoxy chains. In contrast, it is substituted with a para-alkoxy group in XW38 and XW39. The phenothiazine wrapping in XW36 and XW37 induces more serious distortion, which is beneficial for anti-aggregation but unfavorable for the electron transfer from donor to a porphyrin framework. Thus, individual porphyrin dyes XW36 and XW37 exhibit efficiencies of 9.05 and 9.58%, respectively, lower than those of 9.51 and 10.0% achieved for XW38 and XW39, respectively. Besides, the introduction of a methyl group into a benzoic acid acceptor unit is conducive to anti-aggregation and thus improves the V-oc and efficiencies. Therefore, higher efficiencies were achieved for XW37 and XW39, compared with XW36 and XW38, respectively. Interestingly, although the individual XW36 dye shows a lowest efficiency among the four dyes, a highest efficiency of 11.7% was obtained for XW36 on the basis of synergetic adsorption with chenodeoxycholic acid and PT-C6 because of simultaneously improved J and Voc, which may be ascribed to the lowest dye-loading amount of XW36 among all of these porphyrin dyes, with the largest vacancy area left on the TiO2 surface available for cosensitizer PT-C6, resulting in a highest J. The high efficiency of 11.7% is one of the highest efficiencies using I-/I-3(-) electrolytes in DSSCs. These results provide an effective strategy for developing efficient DSSCs by the targeted coadsorption and cosensitization of porphyrin sensitizers optimized through introducing a bis(ortho-alkoxy)-wrapped phenyl group into the phenothiazine donor and/or methyl groups into the benzoic acid acceptor unit.

  • 40.
    Lundberg, Didrik
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Provably Sound and Secure Automatic Proving and Generation of Verification Conditions2018Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
    Abstract [en]

    Formal verification of programs can be done with the aid of an interactive theorem prover. The program to be verified is represented in an intermediate language representation inside the interactive theorem prover, after which statements and their proofs can be constructed. This is a process that can be automated to a high degree. This thesis presents a proof procedure to efficiently generate a theorem stating the weakest precondition for a program to terminate successfully in a state upon which a certain postcondition is placed. Specifically, the Poly/ML implementation of the SML metalanguage is used to generate a theorem in the HOL4 interactive theorem prover regarding the properties of a program written in BIR, an abstract intermediate representation of machine code used in the PROSPER project.

  • 41. Martinez, M.
    et al.
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Ultra-large repair search space with automatically mined templates: The cardumen mode of astor2018In: 10th International Symposium on Search-Based Software Engineering, SSBSE 2018, Springer, 2018, Vol. 11036, p. 65-86Conference paper (Refereed)
    Abstract [en]

    Astor is a program repair library which has different modes. In this paper, we present the Cardumen mode of Astor, a repair approach based mined templates that has an ultra-large search space. We evaluate the capacity of Cardumen to discover test-suite adequate patches (aka plausible patches) over the 356 real bugs from Defects4J [11]. Cardumen finds 8935 patches over 77 bugs of Defects4J. This is the largest number of automatically synthesized patches ever reported, all patches being available in an open-science repository. Moreover, Cardumen identifies 8 unique patches, that are patches for Defects4J bugs that were never repaired in the whole history of program repair.

  • 42. Martinez, M.
    et al.
    Monperrus, Martin
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Astor: Exploring the design space of generate-and-validate program repair beyond GenProg2019In: Journal of Systems and Software, ISSN 0164-1212, E-ISSN 1873-1228, Vol. 151, p. 65-80Article in journal (Refereed)
    Abstract [en]

    This article contributes to defining the design space of program repair. Repair approaches can be loosely characterized according to the main design philosophy, in particular “generate- and-validate” and synthesis-based approaches. Each of those repair approaches is a point in the design space of program repair. Our goal is to facilitate the design, development and evaluation of repair approaches by providing a framework that: a) contains components commonly present in most approaches, b) provides built-in implementations of existing repair approaches. This paper presents a Java framework named Astor that focuses on the design space of generate-and-validate repair approaches. The key novelty of Astor is to provides explicit extension points to explore the design space of program repair. Thanks to those extension points, researchers can both reuse existing program repair components and implement new ones. Astor includes 6 unique implementations of repair approaches in Java, including GenProg for Java called jGenProg. Researchers have already defined new approaches over Astor. The implementations of program repair approaches built already available in Astor are capable of repairing, in total, 98 real bugs from 5 large Java programs. Astor code is publicly available on Github: https://github.com/SpoonLabs/astor.

  • 43.
    Meinke, Karl
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Bennaceur, A.
    Machine learning for software engineering: Models, methods, and applications2018In: Proceedings of the 40th International Conference on Software Engineering: Companion Proceeedings, IEEE Computer Society, 2018, p. 548-549Conference paper (Refereed)
    Abstract [en]

    Machine Learning (ML) is the discipline that studies methods for automatically inferring models from data. Machine learning has been successfully applied in many areas of software engineering ranging from behaviour extraction, to testing, to bug fixing. Many more applications are yet be defined. However, a better understanding of ML methods, their assumptions and guarantees would help software engineers adopt and identify the appropriate methods for their desired applications. We argue that this choice can be guided by the models one seeks to infer. In this technical briefing, we review and reflect on the applications of ML for software engineering organised according to the models they produce and the methods they use. We introduce the principles of ML, give an overview of some key methods, and present examples of areas of software engineering benefiting from ML. We also discuss the open challenges for reaching the full potential of ML for software engineering and how ML can benefit from software engineering methods.

  • 44.
    Mukhopadhyay, Sagnik
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Radhakrishnan, Jaykumar
    Tata Inst Fundamental Res, Bombay, Maharashtra, India..
    Sanyal, Swagato
    IIT Kharagpur, Dept Comp Sci & Engn, Kharagpur, W Bengal, India..
    Separation Between Deterministic and Randomized Query Complexity2018In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 47, no 4, p. 1644-1666Article in journal (Refereed)
    Abstract [en]

    Saks and Wigderson 27th FOGS, IEEE Computer Society, as Alamitos, CA, 1986, pp. 29-38] conjectured that R-0(f) = Omega (D(f)(0.753...)) for all Boolean functions f, here R-0 denotes the randomized complexity and D denotes 10 determinist is query CCATI p1exit;,yr. We,show t hat for the pointer function GPW(rxs) defined by Goos. Pitassi, arid Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077-1088] the following hold: s) s) and (b) R-1(GPW(rxs)) = Irs), cyhere R1 denotes the randomized one-sided error query complexity. These results imply that (i) R-0(GPW(s2xs)) = O(D(GPW(s2xs))2/3) t hereby refuting the; conjecture of Saks and Wigdorson, and (ii) R-1 (GPW(sxs))- O(R-0(GPW(sxs))(2/3)), thereby providing a polynomial separation between the randomized zero -error and one-sided error query complexity measures.

  • 45.
    Mukhopadhyay, Sagnik
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS. Computer Science Institute of Charles University, Prague, Czech Republic.
    Loff, Bruno
    Lifting Theorems for Equality.2019Conference paper (Refereed)
    Abstract [en]

    We show a deterministic simulation (or lifting) theorem for composed problems f ◦Eqn where the9 inner function (the gadget) is Equality on n bits. When f is a total function on p bits, it is easy to10 show via a rank argument that the communication complexity of f ◦Eqn is Ω(deg(f)·n). However,11 there is a surprising counter-example of a partial function f on p bits, such that any completion f012 of f has deg(f0) = Ω(p), and yet f ◦Eqn has communication complexity O(n). Nonetheless, we are13 able to show that the communication complexity of f ◦Eqn is at least D(f)·n for a complexity14 measure D(f) which is closely related to the AND-query complexity of f and is lower-bounded by15 the logarithm of the leaf complexity of f. As a corollary, we also obtain lifting theorems for the16 set-disjointness gadget, and a lifting theorem in the context of parity decision-trees, for the NOR17 gadget.18 As an application, we prove a tight lower-bound for the deterministic communication complexity19 of the communication problem, where Alice and Bob are each given p-many n-bit strings, with the20 promise that either all of the strings are distinct, or all-but-one of the strings are distinct, and they21 wish to know which is the case. We show that the complexity of this problem is Θ(p·n).

  • 46. Nemati, H.
    et al.
    Baumann, Christoph
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Guanciale, Roberto
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Dam, Mads
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Formal verification of integrity-Preserving countermeasures against cache storage side-channels2018In: 7th International Conference on Principles of Security and Trust, POST 2018 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Springer Verlag , 2018, p. 109-133Conference paper (Refereed)
    Abstract [en]

    Formal verification of systems-level software such as hypervisors and operating systems can enhance system trustworthiness. However, without taking low level features like caches into account the verification may become unsound. While this is a well-known fact w.r.t. timing leaks, few works have addressed latent cache storage side-channels, whose effects are not limited to information leakage. We present a verification methodology to analyse soundness of countermeasures used to neutralise these channels. We apply the proposed methodology to existing countermeasures, showing that they allow to restore integrity of the system. We decompose the proof effort into verification conditions that allow for an easy adaption of our strategy to various software and hardware platforms. As case study, we extend the verification of an existing hypervisor whose integrity can be tampered using cache storage channels. We used the HOL4 theorem prover to validate our security analysis, applying the verification methodology to a generic hardware model. 

  • 47. Pandurangan, G.
    et al.
    Robinson, P.
    Scquizzato, Michele
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    On the distributed complexity of large-scale graph computations2018In: SPAA '18 Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery (ACM), 2018, p. 405-414Conference paper (Refereed)
    Abstract [en]

    Motivated by the increasing need to understand the distributed algorithmic foundations of large-scale graph computations, we study some fundamental graph problems in a message-passing model for distributed computing where k 2 machines jointly perform computations on graphs with n nodes (typically, n ≫ k). The input graph is assumed to be initially randomly partitioned among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation.

  • 48. Rauf, I.
    et al.
    Vistbakka, I.
    Troubitsyna, Elena
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Formal Verification of Stateful Services with REST APIs Using Event-B2018In: Proceedings - 2018 IEEE International Conference on Web Services, ICWS 2018 - Part of the 2018 IEEE World Congress on Services, Institute of Electrical and Electronics Engineers Inc. , 2018, p. 131-138Conference paper (Refereed)
    Abstract [en]

    REST APIs are being increasingly used in the industry including their application in safety-critical domain and in the IoT world. They offer basic CRUD (create, retrieve, update and delete) interfaces. However, REST APIs can be used to build services with more advanced scenarios. Developing such services with REST constraints requires rigorous approaches that are capable of creating services that can be trusted for their behavior. In this work, we present an approach based on formal verification technique for a development of REST services using Event-B. We focus on deriving a correct system architecture by refinement and consistency verification of service design models. We illustrate our approach on a Hotel Reservation System. 

  • 49.
    Riese, Emma
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Teaching Assistants’ Experiences of Lab Sessions in Introductory Computer Science Courses2018In: 2018 IEEE Frontiers in Education Conference (FIE), 2018Conference paper (Refereed)
    Abstract [en]

    This Research Work in Progress paper presents a study on how teaching assistants (TAs) in introductory computer science courses experience their roles and responsibilities in programming lab sessions. Eight semi-structured interviews were performed with TAs who worked in different introductory computer science courses at a technical university in Sweden. The interviews were recorded, transcribed and analyzed using thematic analysis. Four main themes were identified: uncertainty with assessing, lack of training and instructions, communication and students in focus. The most important finding is that TAs, even those with long experience of teaching, experienced uncertainties with the assessment of the assignments. Typically, the guidelines given to the TAs only included the functionalities of the program, but the TAs express that they also assessed whether the students understood the concepts and how their code worked. Noteworthily, the TAs had been offered none or little formal training and instead relied on informal mentorships and own experiences. Furthermore, the course structure and communication channels were also described as areas that could be improved. The TAs did, however, try to assist all their students, and tutor and support them from the best of their abilities.

  • 50.
    Riese, Emma
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Dicander, Marcus
    KTH, School of Electrical Engineering and Computer Science (EECS), Computational Science and Technology (CST).
    Rosqvist, D.
    Students' experiences of two different types of introduction to pair programming in introductory programming courses2018In: IMSCI 2018 - 12th International Multi-Conference on Society, Cybernetics and Informatics, Proceedings, International Institute of Informatics and Systemics, IIIS , 2018, p. 91-97Conference paper (Refereed)
    Abstract [en]

    Implementation of pair programming has been found beneficial in both the software development industry and in educational settings. This paper aims to give insights into how the introduction of pair programming influences the students' experience and use of pair programming. A framework of different introduction levels of pair programming, from voluntary to completely mandatory, is presented. A second framework consisting of categories regarding students' descriptions of pair programming and their experienced advantages and disadvantages, based on a previous study, is also presented. Semi-structured interviews were carried out with 19 students. The interviews were analyzed using the framework. The interviewed students had been given different introductions to pair programming, either voluntary or mandatory, during two introductory programming courses at KTH Royal Institute of Technology. A mixed methods approach was used; the analyzed interviews, results from course surveys and data from a pair programming logging tool were used to answer to what extent the students have been using pair programming. The results show that the students subjected to mandatory pair programming displayed to a higher extent, knowledge of the roles in pair programming. These students also expressed a greater variety of advantages and disadvantages, compared to the students with voluntary pair programming. 

12 1 - 50 of 70
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