More Like this

1. Optimal orthogonal group synchronization and rotation group synchronization

   https://doi.org/10.1093/imaiai/iaac022  

   Gao, Chao; Zhang, Anderson Y. (August 2022, Information and Inference: A Journal of the IMA)

   Abstract We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $$Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$$ where $$W_{ij}$$ is a Gaussian random matrix and $$Z_i^*$$ is either an orthogonal matrix or a rotation matrix, and each $$Y_{ij}$$ is observed independently with probability $$p$$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $$(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk. 

   more » « less
2. Synchronization Schemas

   https://doi.org/10.1145/3452021.3458317  

   Alur, Rajeev; Hilliard, Phillip; Ives, Zachary G.; Kallas, Konstantinos; Mamouras, Konstantinos; Niksic, Filip; Stanford, Caleb; Tannen, Val; Xue, Anton (June 2021, ACM Symposium on Principles of Database Systems)

   null (Ed.)
3. Synchronization Schemas

   Alur, R.; Hilliard, P; Ives, Z.G; Kallas, K; Mamouras, K; Niksic, F; Stanford, C.; Tannen, V; Xue, A. (January 2021, ACM Symposium on Principles of Database Systems)

   null (Ed.)
4. Learning Transformation Synchronization

   Huang, Xiangru; Liang, Zhenxiao; Zhou, Xiaowei; Xie, Yao; Guibas, Leonidas J.; Huang, Qixing (January 2019, Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition)
5. Responsive Parallelism with Synchronization

   https://doi.org/10.1145/3591249  

   Muller, Stefan K.; Singer, Kyle; Keeney, Devyn Terra; Neth, Andrew; Agrawal, Kunal; Lee, I-Ting Angelina; Acar, Umut A. (June 2023, Proceedings of the ACM on Programming Languages)

   Many concurrent programs assign priorities to threads to improve responsiveness. When used in conjunction with synchronization mechanisms such as mutexes and condition variables, however, priorities can lead to priority inversions, in which high-priority threads are delayed by low-priority ones. Priority inversions in the use of mutexes are easily handled using dynamic techniques such as priority inheritance, but priority inversions in the use of condition variables are not well-studied and dynamic techniques are not suitable. In this work, we use a combination of static and dynamic techniques to prevent priority inversion in code that uses mutexes and condition variables. A type system ensures that condition variables are used safely, even while dynamic techniques change thread priorities at runtime to eliminate priority inversions in the use of mutexes. We prove the soundness of our system, using a model of priority inversions based on cost models for parallel programs. To show that the type system is practical to implement, we encode it within the type systems of Rust and C++, and show that the restrictions are not overly burdensome by writing sizeable case studies using these encodings, including porting the Memcached object server to use our C++ implementation. 

   more » « less