Reduction from Bichromatic Hamming Close Pair to Approximate Hard-Margin SVM: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 12:1912:19, 15 February 2023‎ Admin talk contribs‎ 701 bytes +701‎ Created page with "FROM: Bichromatic Hamming Close Pair TO: Approximate Hard-Margin SVM == Description == == Implications == assume: SETH<br/>then: let $k(a,a')$ be the Gaussian kernel with $C={100}\log n$ and let $\epsilon = \exp(-\omega(\log^{2} n))$, then approximating the optimal value of target within multiplicative factor ${1}+\epsilon$ requires almost quadratic time. == Year == 2017 == Reference == Backurs, A., Indyk, P., & Schmidt, L. (2017). On the fine-graine..."
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_Bichromatic_Hamming_Close_Pair_to_Approximate_Hard-Margin_SVM"