More Like this

1. Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering

   https://doi.org/10.1145/3313276.3316350  

   Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya (June 2019, Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering)

   Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log(k /ε) / ε2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p. For k-means, our result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan. 

   more » « less
2. Spectroscopy of A=9A=9A=9 hyperlithium with the (e,e′K+)e,e′K^+)e,e′K+) reaction

   T. Gogami, C. Chen (April 2021, Physical review)

   null (Ed.)
3. 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)
4. On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP

   https://doi.org/10.4230/LIPIcs.IPEC.2024.6  

   Karthik, C_S; Lee, Euiwoong; Manurangsi, Pasin (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bonnet, Édouard; Rzążewski, Paweł (Ed.)

   Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on k variables and alphabet size n, it is 𝖶[1]-hard parameterized by k to distinguish if the input is perfectly satisfiable or if every assignment to the input violates 1% of the constraints. An important implication of PIH is that it yields the tight parameterized inapproximability of the k-maxcoverage problem. In the k-maxcoverage problem, we are given as input a set system, a threshold τ > 0, and a parameter k and the goal is to determine if there exist k sets in the input whose union is at least τ fraction of the entire universe. PIH is known to imply that it is 𝖶[1]-hard parameterized by k to distinguish if there are k input sets whose union is at least τ fraction of the universe or if the union of every k input sets is not much larger than τ⋅ (1-1/e) fraction of the universe. In this work we present a gap preserving FPT reduction (in the reverse direction) from the k-maxcoverage problem to the aforementioned 2-CSP problem, thus showing that the assertion that approximating the k-maxcoverage problem to some constant factor is 𝖶[1]-hard implies PIH. In addition, we present a gap preserving FPT reduction from the k-median problem (in general metrics) to the k-maxcoverage problem, further highlighting the power of gap preserving FPT reductions over classical gap preserving polynomial time reductions. 

   more » « less
5. K-stability of cubic fourfolds

   https://doi.org/10.1515/crelle-2022-0002  

   Liu, Yuchen (February 2022, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract We prove that the K-moduli space of cubic fourfolds is identical to their GIT moduli space.More precisely, the K-(semi/poly)stability of cubic fourfolds coincide to the corresponding GIT stabilities, which was studied in detail by Laza. In particular, this implies that all smooth cubic fourfolds admit Kähler–Einstein metrics. Key ingredients are local volume estimates in dimension three due to Liu and Xu, and Ambro–Kawamata’s non-vanishing theorem for Fano fourfolds. 

   more » « less