We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n)o(1). Previously, the best update time was for any c > 2 and c = O (log n) [28].

We present a deterministic fully dynamic algorithm to answer c-edge connectivity queries on pairs of vertices in n°(1) worst case update and query time for any positive integer$c$= (log n)°(1)for a graph with$n$vertices. Previously, only polylogarithmic, O(√n), and O(n2/3) worst case update time fully dynamic algorithms were known for answering 1, 2 and 3-edge connectivity queries respectively [Henzinger-King 1995, Frederikson 1997, Galil and Italiano 1991]. Our result extends the c-edge connectivity vertex sparsifier [Chalermsook et al. 2021] to a multi-level sparsification framework. As our main technical contribution, we present a novel update algorithm for the multi-level c-edge connectivity vertex sparsifier with subpolynomial update time. See https://arxiv.org/abs/2004.07650 for the full version of this paper.

Speech is a critical biomarker for Huntington Disease (HD), with changes in speech increasing in severity as the disease progresses. Speech analyses are currently conducted using either transcriptions created manually by trained professionals or using global rating scales. Manual transcription is both expensive and time-consuming and global rating scales may lack sufficient sensitivity and fidelity [1]. Ultimately, what is needed is an unobtrusive measure that can cheaply and continuously track disease progression. We present first steps towards the development of such a system, demonstrating the ability to automatically differentiate between healthy controls and individuals with HD using speech cues. The results provide evidence that objective analyses can be used to support clinical diagnoses, moving towards the tracking of symptomatology outside of laboratory and clinical environments.