Neuer Algorithmus löst Lernproblem von Halbflächen bei faktorisierten Verteilungen
Das Lernen von Schnittstellen zweier Halbflächen ist ein zentrales Problem der Computational Learning Theory. Trotz jahrzehntelanger Forschung ist es noch immer unklar, ob ein polynomieller Algorithmus existiert, der die Datenpunkte mit einem gegebenen Rand γ und einer Dimensionalität d verarbeiten kann. Bestehende Verfahren benötigen quasi-polynomielle Laufzeiten dO(log(1/γ)) und zeigen, dass die CSQ‑Hardness‑Barriere für reine Korrelationsabfragen unvermeidlich ist.
