Previous TCS Seminar Series

TCS Seminar Series Spring 2020

(50% Seminar) Application Level Chaos Engineering

by Long Zhang, KTH, on 25 Jun 2020 at 16:00 in zoom

Software systems contain resilience code to handle those failures and unexpected events happening in production. It is essential for developers to understand and assess the resilience of their systems. Chaos engineering is a technology that aims at assessing resilience and uncovering weaknesses by actively injecting perturbations in production. During this talk, I will introduce what we have researched about application-level chaos engineering. More specifically, I will talk about resilience evaluation at the level of try-catch blocks, methods, and system call invocations.

(50% seminar) Formal Verification of Direct Memory Accesses of I/O Devices

by Jonas Haglund, KTH, on 29 May 2020 at 16:00 in zoom

I/O devices having direct memory access (DMA) are common in computer systems, e.g. storage devices, USBs and network interfaces. Since memory is shared between critical and non-critical software, it is important that the DMA driver of the operating system does not configure the DMA controller (DMAC) such that the DMAC reads confidential data or overwrites sensitive data or code. In order to configure the DMAC such that it does not perform any unwanted memory accesses, it must be known what an allowed DMAC state is.

I will present an approach for formally verifying which DMAC states are allowed from the perspective of memory isolation and the common features of DMACs. This is currently work in progress, and will be presented with previous and related work.

Hardness of learning DNFs using Halfspaces

by Suprovat Ghoshal on 23 Mar 2020 at 13:15 in room 4523

The problem of learning t-term DNF formulas (for t=O(1)) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A t-term DNF can be efficiently learnt using a t-term DNF only if t=1 i.e., when it is an AND, while even weakly learning a 2-term DNF using a constant term DNF was shown to be NP-hard by Khot and Saket (FOCS 2008). On the other hand, Feldman et al. (FOCS 2009) showed the hardness of weakly learning a noisy AND using a halfspace -- the latter being a generalization of an AND, while Khot and Saket (STOC 2008) showed that an intersection of two halfspaces is hard to weakly learn using any function of constantly many halfspaces. The question of whether a 2-term DNF is efficiently learnable using 2 or constantly many halfspaces remained open.

In this work we answer this question in the negative by showing the hardness of weakly learning a 2-term DNF as well as a noisy AND using any function of a constant number of halfspaces. In particular we prove the following: For any constants \nu,\zeta > 0 and \mathcal{l} \in \mathbbm{N}, given a distribution over point-value pairs {0,1}^n \times {0,1}, it is NP-hard to decide whether,

YES Case: There is a 2-term DNF that classifies all the points of the distribution, and an AND that classifies at least 1−\zeta fraction of the points correctly.

NO Case: Any boolean function depending on at most \ell halfspaces classifies at most 1/2+\nu fraction of the points of the distribution correctly.

Our result generalizes and strengthens the previous best results mentioned above on the hardness of learning a 2-term DNF, learning a intersection of two halfspaces, and learning a noisy AND.

This is joint work with Rishi Saket (IBM Research).

Software Engineering ReThought - future challenges and empirical software engineering

by Tony Gorschek, Blekinge Institute of Technology, on 03 Mar 2020 at 11:15 in room 1537

Software Engineering ReThought is a new research project with the aim to take on the next generation challenges facing companies developing software-intensive systems and products. We as an engineering lab are working on introducing 3:rd generation empirical software engineering – denoting close co-production of pragmatic problem-solving in close collaboration with our industrial partners as we perform engineering research. The focus is on how to affect change, today.

(50% seminar) A Characterization of all low Degree Polynomial Calculus Consequences

by Kilian Risse, KTH, on 21 Feb 2020 at 13:15 in room 4523

Polynomial calculus is a proof system that can be used to determine whether a given system of polynomials is consistent. In every step of the derivation we may either take a linear combination of two previously derived polynomials or multiply a derived polynomial by a variable. The goal is to derive 1, which shows that the given system of polynomials is inconsistent. An important measure of complexity is the minimum degree required to refute an inconsistent system.

In this seminar we show a degree lower bound for the pigeonhole principle formula claiming that m pigeons can be mapped one-to-one to n holes for m > n. The lower bound follows from a more general statement that precisely characterizes polynomials that are derivable in low degree.

This based is based on joint work with Jakob Nordström, Anastasia Sofronova, Dmitry Sokolov and Marc Vinyals.

TCS Seminar Series Fall 2019

TCS Seminar Series Spring 2019

TCS Seminar Series Autumn 2018

TCS Seminar Series Spring 2018

TCS Seminar Series Fall 2017

TCS Seminar Series Spring 2017

TCS Seminar Series Fall 2016

TCS Seminar Series Spring 2016

TCS Seminar Series Fall 2015

TCS Seminar Series Spring 2015

TCS Seminar Series Fall 2014

TCS Seminar Series Spring 2014

TCS Seminar Series Fall 2013

TCS Seminar Series Spring 2013

TCS Seminar Series Fall 2012

TCS Seminar Series Spring 2012

TCS Seminar Series Fall 2011

TCS Seminar Series Spring 2011

TCS Seminar Series Fall 2010

TCS Seminar Series Spring 2010

TCS Seminar Series Fall 2009

TCS Seminar Series Spring 2009

TCS Seminar Series Fall 2008

TCS Seminar Series Spring 2008

TCS Seminar Series Fall 2007

TCS Seminar Series Spring 2007

TCS Seminar Series Autumn 2006

  • Monday December 11, 10:15, room 4523 (NB! Not the usual time and place):
    Higher Level Fusion For Catastrophic Events
    (Galina L. Rogova PhD, Encompass Consulting, USA)

    The core purpose of higher level fusion (situation and threat assessment) is to infer and approximate the characteristics and critical events of the environment in relation to specific goals, capabilities and policies of the decision makers. The higher level fusion processes utilize fused data about objects of interest, dynamic databases, maps, and expert knowledge, and opinion for context processing. The result of higher level fusion is a coherent composite picture of the current and predicted situation, which provides human experts with essential information to help them understand and control the situation, and act effectively to mitigate its impact. Situation and threat assessment processing has to be adaptive to resource and time constraints, new and uncertain environments, and reactive to uncertain and unreliable heterogeneous inputs.

    The presentation will discuss major challenges, specific requirements, and approaches to designing higher level fusion processes as applied to the problem of crisis management.

    The higher level fusion processing described in the presentation exploits synergy between cognitive work analysis and ontological analysis of the specific domain, developed within the framework of a formal ontology. The combination of cognitive work analysis and ontology provides a formally structured and computationally tractable domain representation capturing the basic structures of relevant objective reality and users’ domain knowledge and requirements. This domain representation further serves as a basis for generating domain specific situational hypotheses and high-level reasoning about these hypotheses. The dynamic situational picture is built by analyzing spatial and temporal relations of the situational entities and entity aggregations at different levels of granularity, and their dynamics provided within the overall situational context. Special attention is paid to "inference for best explanation" aimed at discovery of the underlying causes of observed situational entities and their behavior. Belief Based Argumentation system, a reasoning framework considered, represents a generalization of Probabilistic Argumentation System. It allows for allocating rational belief in hypotheses about the environment by utilizing given knowledge to find and combine arguments in favor of and against them.

    The presented methodology also includes multi-step inter-level and intra-processing information exchange comprising a quality control and a belief update steps.

  • Monday November 20, 13:15, room 1537:
    Counting Set Covers
    (Andreas Björklund, Lund Institute Of Technology)

    In a Set Cover problem we are given a ground set U of size n and a family S of size m of subsets of U and we want to know if U can be covered by k of the sets from S. We give two related algorithms which are stronger than applying dynamic programming over all subsets of U.

    1. We demonstrate a simple technique solving the problem in space $\poly(n,\log m)$ and time $\poly(n,\log m)m2^n$ which actually counts the number of solutions.
    2. We show that with exponential space we can count the solutions in time $\poly(n,\log m)(m+2^n)$ which gives us the fastest algorithms for Chromatic Number and Domatic Number known to date.

    Based on two recent papers with Thore Husfeldt announced at ICALP 2006 and FOCS 2006. The seminar will be roughly 45 minutes long.

  • Monday October 2, 13:15, room 1537:
    (Stefan Nilsson, Theory Group, KTH CSC)

    BitTorrent är ett filöverföringsprotokoll som gör det möjligt att med mycket små serverresurser distribuera stora filer till många användare på kort tid. I det här föredraget kommer jag att beskriva hur protokollet fungerar, berätta hur Bram Cohen uppfann det och diskutera dess skalbarhet, säkerhet och begränsningar.

    Seminariet blir ca 45 minuter långt.

    TCS Seminar Series Spring 2006

    TCS Seminar Series Autumn 2005

    TCS Seminar Series, spring 2005

    TCS Seminar Series, autumn 2004

    TCS Seminar Series, spring 2004

    TCS Seminar Series, autumn 2003

    TCS Seminar Series, spring 2003

    TCS Seminar Series, autumn 2002

    TCS Seminar Series, spring 2002

    TCS Seminar Series, spring 2000

    TCS Seminar Series, autumn 1999