Aaron Sidford

Fast, Parallel, Query-Efficient Binary Classification

This work presents a randomized algorithm that solves the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size $n$ with normalized $d$-dimensional features and presents a second, faster randomized algorithm with improved sequential runtime and parallel depth.