2008/07/29 by Subhash Khot, Khot, Subhash, Assaf Naor +1
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Optimization and Search Problems #Stochastic Gradient Optimization Techniques #cs.CC #cs.DS #math.FA
paper · pdf · doi:10.48550/arxiv.0807.4626
openalex publication_date 2008/07/29 · arxiv created 2008/12/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the kernel clustering problem we are given a large n× n positive semi-definite matrix A=(aij) with ∑i,j=1naij=0 and a small k× k positive semi-definite matrix B=(bij). The goal is to find a partition S1,...,Sk of \1,... n\ which maximizes the quantity ∑i,j=1k (∑(i,j)∈ Si× Sjaij)bij. We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the Unique Games Conjecture (UGC). In particular, when B is the 3× 3 identity matrix the UGC hardness threshold of this problem is exactly (16π)/(27). We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when B is the k× k identity matrix is (8π)/(9)(1-(1)/(k)) for every k≥ 3.