{"id":"arxiv/2607.04062","url":"https://arxiv.org/abs/2607.04062","tags":["math.OC","cs.DS","cs.LG"],"score":0,"title":"Fast, Parallel, Query-Efficient Binary Classification","domain":"math.OC","source":"arxiv","authors":["Ishani Karmarkar","Liam O'Carroll","Aaron Sidford"],"reviews":0,"subject":"math.OC","summary":"We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$-dimensional features. Letting $Φ\\in \\mathbb{R}^{n \\times d}$ denote the feature matrix and $γ$ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in $\\tilde{O}(γ^{-2/3}\\, \\operatorname{nnz}(Φ) + γ^{-2(ω+1)/3})$-sequential running time (work), $\\tilde{O}(γ^{-2/3})$-parallel (computational) depth, and accesses $Φ$ only through $\\tilde{O}(γ^{-2/3})$-matrix-vector queries (matvecs). We…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-05","reactions":{}}