In the distributed edge-connectivity problem, every node in the distributed graph (the CONGEST model) needs to find what is the minimum number of edges required to be removed to disconnect the graph. This work addresses edge connectivity of constant size. Here, the first significant result was by [Pritchard and Thurimella, ACM TALG'2011], who gave a randomized algorithm that finds all the small sized cuts in O(D) time. Their algorithm is restrictive and finds cuts of size only one and two. The technique used here is binary random circulation. In this work, we resolve an open problem mentioned in Pritchard and Thurimella giving a deterministic algorithm for finding all cuts of size two in O(D) time. Our algorithm also improves results by Parter [DISC'19], who provided a fault-tolerant based approach to finding min-cuts poly(D, log n) (polynomial in the size of min-cut).

Epidemiologists and social scientists have used the Network Scale-Up Method (NSUM) for over thirty years to estimate the size of a hidden sub-population within a social network. This method involves querying a subset of network nodes about the number of their neighbors belonging to the hidden sub-population. In general, NSUM assumes that the social network topology and the hidden sub-population distribution are well-behaved; hence, the NSUM estimate is close to the actual value. However, bounds on NSUM estimation errors have not been analytically proven. This paper provides analytical bounds on the error incurred by the two most popular NSUM estimators. These bounds assume that the queried nodes accurately provide their degree and the number of neighbors belonging to the hidden sub-population. Our key findings are twofold. First, we show that when an adversary designs the network and places the hidden sub-population, then the estimate can be a factor of ω(gšn) off from the real value (in a network with n nodes). Second, we also prove error bounds when the underlying network is randomly generated, showing that a small constant factor can be achieved with high probability using samples of logarithmic size O(log n). We present improved analytical bounds for ErdÅ's-Rényi and Scale-Free networks. Our theoretical analysis is supported by an extensive set of numerical experiments designed to determine the effect of the sample size on the accuracy of the estimates in both synthetic and real networks.

Third-cycle education is an important part of higher education at KTH, but has been limited discussed during previous KTHSoTL conferences. Third-cycle education can, however, face a different set of challenges compared to first and second-cycle, and there have for instance been alarming reports concerning the well-being of doctoral students [1]. The COVID-19 pandemic, has also come with an additional set of challenges for doctoral students [2], and balancing the different roles within a doctoral education program has been reported as difficult [3]. The purpose of this workshop is to highlight, reflect on, discuss and find possible solutions to some of the key issues which were identified in the doctoral student survey, that was conducted by the PhD Chapter at KTH in December 2019 [4].

The workshop will be structured around the questions:

• How should third-cycle education at KTH look like in ten years, 2031?'

• What do we need to change to reach that vision?

In December 2019, the PhD Chapter (THS) sent out a survey to all doctoral students that had a registered study activity and email address in Ladok [4]. KTH has also recently sent out a survey to all doctoral students that were admitted to their doctoral studies between the years 2012-2016 [5]. In addition, in UKÄ’s recent review of KTH’s quality assurance system, they highlighted that the doctoral students at KTH were not given as good opportunities to influence their education as first-and second-cycle students, but at the same time recognizing that this is something KTH works with [6]. A short summary of the survey results from the PhD Chapter’s report on “Consequences of COVID-19” gave some insights into how the current pandemic influenced KTH’s doctoral students at the beginning of the pandemic [7].Results/observations/lessons learnedThird-cycle education differentiates from first- and second-cycle, and comes with a set of own challenges. Based on the four sources regarding KTH’s doctoral students [4-7], we like to focus on some key topics that have been identified to have room for improvements:

• Supervision [4-5] - what characterizes good supervision and how do we achieve that?

• Doctoral student influence and evaluations of study programs [4, 6] - how can this be strengthened and unified across KTH?

• Well-being and balance between private and working life [4] - what can be done to support the doctoral students to achieve this? For instance, how can the work culture support a good balance?

• Study and work environment [4] - what is working well and what can be improved?

• Career opportunities and guidance for doctoral students [4-6] - what can be done to strengthen this?

• COVID-19 pandemic consequences [7] - what can we learn from this experience and how can we minimize potential damage to doctoral education on short and long term?