More Like this

1. K-theory for real k-graph C∗-algebras

   https://doi.org/10.2140/akt.2022.7.395  

   Boersema, Jeffrey L.; Gillaspy, Elizabeth (January 2022, Annals of K-Theory)
2. K-homology and K-theory for pure braid groups

   Azzali, Sara; Browne, Sarah L.; Gomez Aparicio, Maria Paula; Ruth, Lauren C.; Wang, Hang (January 2022, New York journal of mathematics)

   We produce an explicit description of the K-theory and K-homology of the pure braid group on n strands. We describe the Baum–Connes correspondence between the generators of the left- and right-hand sides for n = 4. Using functoriality of the assembly map and direct computations, we recover Oyono-Oyono’s result on the Baum–Connes conjecture for pure braid groups [24]. We also discuss the case of the full braid group on 3-strands. 

   more » « less
3. Improved Guarantees for k-means++ and k-means++ Parallel

   Makarychev, Konstantin; Reddy, Aravind; Shan, Liren (December 2020, Advances in neural information processing systems)

   In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++. 

   more » « less
4. Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

   https://doi.org/10.1287/moor.2021.1250  

   Chandrasekaran, Karthekeyan; Chekuri, Chandra (January 2022, Mathematics of Operations Research)
5. Near-optimal Algorithms for Explainable k-Medians and k-Means

   Makarychev, Konstantin; Shan, Liren (July 2021, International Conference on Machine Learning)

   null (Ed.)

   We consider the problem of explainable k-medians and k-means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). In this problem, our goal is to find a threshold decision tree that partitions data into k clusters and minimizes the k-medians or k-means objective. The obtained clustering is easy to interpret because every decision node of a threshold tree splits data based on a single feature into two groups. We propose a new algorithm for this problem which is O(log k) competitive with k-medians with ℓ1 norm and O(k) competitive with k-means. This is an improvement over the previous guarantees of O(k) and O(k^2) by Dasgupta et al (2020). We also provide a new algorithm which is O(log^{3}{2}k) competitive for k-medians with ℓ2 norm. Our first algorithm is near-optimal: Dasgupta et al (2020) showed a lower bound of Ω(log k) for k-medians; in this work, we prove a lower bound of Ω(k) for k-means. We also provide a lower bound of Ω(log k) for k-medians with ℓ2 norm. 

   more » « less