More Like this

1. Distributed MST: A Smoothed Analysis

   https://doi.org/10.1145/3369740.3369778  

   Chatterjee, Soumyottam; Pandurangan, Gopal; Pham, Nguyen Dinh (January 2020, ICDCN 2020: Proceedings of the 21st International Conference on Distributed Computing and Networking)

   We study smoothed analysis of distributed graph algorithms, focusing on the fundamental minimum spanning tree (MST) problem. With the goal of studying the time complexity of distributed MST as a function of the "perturbation" of the input graph, we posit a smoothing model that is parameterized by a smoothing parameter 0 ≤ ϵ(n) ≤ 1 which controls the amount of random edges that can be added to an input graph G per round. Informally, ϵ(n) is the probability (typically a small function of n, e.g., n--¼) that a random edge can be added to a node per round. The added random edges, once they are added, can be used (only) for communication. We show upper and lower bounds on the time complexity of distributed MST in the above smoothing model. We present a distributed algorithm that, with high probability, 1 computes an MST and runs in Õ(min{1/√ϵ(n)2O(√log n), D+ √n}) rounds2 where ϵ is the smoothing parameter, D is the network diameter and n is the network size. To complement our upper bound, we also show a lower bound of Ω(min{1/√ϵ(n), D + √n}). We note that the upper and lower bounds essentially match except for a multiplicative 2O(√log n) polylog(n) factor. Our work can be considered as a first step in understanding the smoothed complexity of distributed graph algorithms. 

   more » « less
2. Game Theoretic Analysis of Ransomware: A Preliminary Study [Game Theoretic Analysis of Ransomware: A Preliminary Study]

   https://doi.org/10.5220/0011006600003120  

   Baksi, Rudra; Upadhyaya, Shambhu (January 2022, 8th International Conference on Information Systems Security and Privacy (ICISSP))
3. Regression-Assisted Independent Vector Analysis: A Solution to Large Scale fMRI Analysis

   https://doi.org/10.1109/IEEECONF59524.2023.10476796  

   Yang, H; Gabrielson, B; Calhoun, V D; Adali, T (October 2023, Proc. 57th Asilomar Conf. on Signals, Systems and Computers)
4. A TSL Analysis of Japanese Case

   https://doi.org/10.7275/xqhr-r404  

   Hanson, Kenneth (January 2023, Proceedings of the Society for Computation in Linguistics)

   Recent work in subregular syntax has revealed deep parallels among syntactic phenomena, many of which fall under the computational class TSL (Graf, 2018, 2022). Vu et al. (2019) argue that case dependencies are yet another member of this class. But their analysis focuses mainly on English, which is famously case-poor. In this paper I present a TSL analysis of Japanese, which features a much wider range of case-marking patterns, adding support to the claim that case dependencies, and by extension syntactic dependencies, are TSL. 

   more » « less
5. Typed–Untyped Interactions: A Comparative Analysis

   https://doi.org/10.1145/3579833  

   Greenman, Ben; Dimoulas, Christos; Felleisen, Matthias (March 2023, ACM Transactions on Programming Languages and Systems)

   The literature presents many strategies for enforcing the integrity of types when typed code interacts with untyped code. This article presents a uniform evaluation framework that characterizes the differences among some major existing semantics for typed–untyped interaction. Type system designers can use this framework to analyze the guarantees of their own dynamic semantics. 

   more » « less