91 Arbeiten
Die Arbeit stellt eine vollständig dynamische Datenstruktur vor, die einen spektralen Sparsifizierer für geometrische Graphen mit -Aktualisierungszeit unter Punktänderungen erhält und zudem robuste Skizzen für Laplace-Matrizen bereitstellt, die Matrix-Vektor-Multiplikationen und Projektionen effizient unterstützen.
Die Autoren stellen einen neuartigen, vollständig symmetrischen Ansatz zur Lösung von Discounted-Payoff-Spielen vor, der durch die schrittweise Minimierung eines Fehlerbetrags, der aus einem auf allen Kanten basierenden Ungleichungssystem abgeleitet wird, die etablierte Dichotomie zwischen Strategieverbesserung und Wertiteration herausfordert.
Diese Arbeit bestimmt die Schwellenwerte für die Detektion korrelierter stochastischer Blockmodelle mittels Polynome niedrigen Grades und zeigt, dass eine Unterscheidung von unabhängigen Erdős-Rényi-Graphen genau dann möglich ist, wenn die Subsampling-Wahrscheinlichkeit den Minimum-Wert aus der Wurzel von Otters Konstante und dem Kehrwert des Kesten-Stigum-Schwellenwerts überschreitet.
Diese Arbeit führt eine relaxierte Definition der Highway-Dimension ein, die auch natürliche metrische Räume wie Gitter und die euklidische Ebene umfasst, und nutzt diese, um ein Padded-Decomposition-Toolkit sowie einen PTAS für das Traveling-Salesman-Problem zu entwickeln.
Dieser Artikel stellt zwei effiziente Algorithmen zur Berechnung des multiplikativen Inversen modulo für beliebige ganze Zahlen vor: einen allgemeinen Ansatz, der von der Schulmultiplikation inspiriert ist und Hardware-Arithmetik nutzt, sowie eine Verallgemeinerung von Hensel-Lifting-Methoden für Moduli der Form .
Diese Arbeit verbessert bestehende Algorithmen für lineare Algebra-Aufgaben mit Kernel-Matrizen durch den Einsatz von Dichteschätzung, wodurch die Abhängigkeit von der Datenmenge und dem Fehler signifikant reduziert wird, und ergänzt diese Ergebnisse durch untere Schranken, die die Grenzen dieser Ansätze aufzeigen.
Diese Arbeit stellt den ersten deterministischen iterativen Algorithmus vor, der für beliebige und eine -Kernmenge mit optimaler Größe ohne logarithmische Faktoren konstruiert, um eine deterministische -Unterraumeinbettung zu gewährleisten und damit das -Regressionsproblem deterministisch zu lösen.
Diese Arbeit stellt den ersten algorithmischen Ansatz vor, der die Approximationsgüte des Greedy-Algorithmus für die submodulare Maximierung über dem Schnitt von Matroiden durch eine hybride Greedy-Lokalsuche-Methode um einen konstanten Faktor verbessert und dabei in polynomieller Zeit unabhängig von läuft.
Diese Arbeit zeigt, dass die bekannten unteren Schranken für den additiven Fehler bei der differenziell privaten fortlaufenden Schätzung von Distinct-Count und -Momenten in Turnstile-Streams umgangen werden können, indem Algorithmen mit sowohl multiplikativem als auch additivem polylogarithmischem Fehler und polylogarithmischem Speicherbedarf entwickelt werden.
Diese Arbeit stellt eine vereinfachte Splitting-Methode durch Längenbegrenzung vor, die die durchschnittliche Abfragezeit von Move-Strukturen in RLBWT-Permutationen auf das Optimum begrenzt, die Konstruktion beschleunigt, den Speicherbedarf signifikant senkt und eine effiziente Inversion des BWT sowie die Enumeration des Suffixarrays mit optimaler Laufzeit ermöglicht.
Die Arbeit stellt DRESS vor, einen deterministischen, parameterfreien und isomorphieinvarianten Rahmen zur iterativen Verfeinerung von Graphstrukturen, der durch Konvergenz eines nichtlinearen dynamischen Systems ein numerisch stabiles Kanten-Fingerprint erzeugt und dabei die Ausdrucksstärke des 2-WL-Tests bei deutlich geringerer Rechenkomplexität erreicht, während Erweiterungen wie Δ-DRESS die Unterscheidungskraft weiter steigern.