87 Arbeiten
Diese Arbeit stellt ein einfaches, generisches Schema zur Schätzung von -Momenten im Turnstile-Streaming-Modell vor, das durch das Hashen von Indizes auf Lévy-Prozesse und die Anwendung des Lévy-Khintchine-Repräsentationssatzes eine einheitliche Erklärung für bestehende Skizzen bietet und die Schätzbarkeit einer breiten Klasse von Funktionen, einschließlich mehrdimensionaler und heterogener Fälle, ermöglicht.
Die Autoren stellen eine neue Subgradienten-Definition für Hadamard-Räume vor, die auf Busemann-Funktionen basiert und stochastische sowie inkrementelle Subgradientenverfahren mit garantierten Komplexitätsgrenzen für konvexe Optimierungsprobleme wie die Berechnung von Medians im BHV-Baumraum ermöglicht.
Die Autoren zeigen, dass eine einfache exakte Methode alle klassischen TSPTW-M-Testinstanzen mit 50 oder mehr Kunden in unter zehn Sekunden löst, was beweist, dass diese Benchmarks nicht mehr repräsentativ für die Bewertung von Algorithmen sind und bei der Erstellung von Trainingsdaten für maschinelles Lernen Vorsicht geboten ist.
Der Artikel stellt einen Algorithmus zur elastischen Zeitverzerrung für Zeitreihen in beliebigen metrischen Räumen vor, der eine optimale Zuordnung unter Verwendung eines Hellinger-Kerns als Strafterm für die Streckung ermöglicht und dabei eine kubische Rechenkomplexität aufweist.
Die Arbeit stellt bsort vor, einen theoretisch effizienten, nicht-vergleichsbasierten Sortieralgorithmus für Ganzzahlen und Gleitkommazahlen, der durch eine von Binärschnellsortieren abgeleitete Methode eine Laufzeit von und einen zusätzlichen Speicherbedarf von erreicht.
Dieser Artikel stellt einen Ein-Pass-Streaming-Algorithmus für das Problem der Auswahl von Einheitsintervallen in zufälliger Reihenfolge vor, der mit linearem Speicherplatz eine erwartete Approximationsgüte von 0,7401 erreicht und damit die zuvor bekannte Schranke von 2/3 für adversarial geordnete Streams übertrifft.
Die Arbeit stellt einen polynomiellen Approximationsschema (PTAS) für das gewichtete triangle-freie 2-Matching-Problem vor, das auf einem einfachen lokalen Suchalgorithmus und einer nicht-trivialen Analyse basiert und damit die bisherige 2/3-Approximation verbessert.
Diese Arbeit stellt einen neuen -differenziell privaten Algorithmus vor, der durch innovative Kandidatengenerierung und Suchraum-Bereinigung die bisherige quadratische Komplexität bei der frequenten Teilstring-Mining eliminiert und dabei nahezu optimale Fehlergarantien bei deutlich reduzierter Speicher- und Zeitkomplexität erreicht.
Dieses Paper stellt ein Kommunikationsprotokoll für das verteilte Expertenproblem vor, das im Vergleich zu früheren Arbeiten eine verbesserte Regret-Schranke bei minimalem Kommunikationsaufwand erreicht.
Die Arbeit untersucht das Online-Problem des gewichteten nicht-kreuzenden Matchings in der euklidischen Ebene und zeigt, dass zwar deterministische Algorithmen für allgemeine Gewichte keine nicht-triviale Wettbewerbsfähigkeit garantieren können, randomisierte Algorithmen jedoch eine konstante Wettbewerbsfähigkeit erreichen, während für Varianten mit revokierbaren Entscheidungen, kollinearen Punkten oder begrenzten Gewichten sowie für die Advice-Komplexität neue obere und untere Schranken hergeleitet werden.
Diese Arbeit stellt einen Algorithmus zur automatisierten Enumeration aller kritischen Paare in linkverbundenen String-Diagramm-Umschreibesystemen vor, der auf Hypergraphen-Manipulation basiert und für symmetrische monoidale Kategorien ohne Frobenius-Struktur auf Korrektheit und Vollständigkeit bewiesen wird.
Diese Arbeit verbessert den Laufzeitkomplexitätsfaktor für -Approximationsalgorithmen des -Median- und -Means-Clustering in niedrigdimensionalen euklidischen Räumen auf $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$ und beweist unter der Gap-Exponential-Time-Hypothese, dass diese Laufzeit bis auf polylogarithmische Faktoren optimal ist.
Diese Arbeit untersucht das many-to-many Zuordnungsproblem mit Präferenzen, die Bindungen und Mindestquoten beinhalten, und zeigt, dass zwar ein kritischer und relaxiert-stabiler Zuordnungsalgorithmus immer existiert, die Berechnung einer maximalen solchen Zuordnung NP-schwer ist, wofür ein polynomieller 2/3-Approximationsalgorithmus entwickelt wurde.
Diese Arbeit zeigt, dass bei der sparsifizierten SYK-Modellierung für eine beweisbare Trennung zwischen klassischen Algorithmen, die auf Gauß-Zuständen basieren, und effizienten Quantenalgorithmen besteht, da erstere nur eine -Approximation der Grundzustandsenergie erreichen, während letztere eine konstante Faktor-Approximation liefern.
Diese Arbeit stellt ein differenziell privates Verfahren zur Schätzung von Black-Box-Statistiken vor, das einen effizienten Kompromiss zwischen der benötigten Datenmenge und der Anzahl der Funktionsauswertungen ermöglicht und durch fast optimale untere Schranken gestützt wird.
Die Arbeit stellt die Exploration Space Theory (EST) vor, ein formales Gittertheorie-Framework für ortsbezogene Empfehlungssysteme, das Abhängigkeiten zwischen Sehenswürdigkeiten modelliert und durch die Exploration Space Recommender System (ESRS) strukturell garantierte, valide nächste Schritte sowie effiziente Pfadgenerierung ermöglicht.
Diese Arbeit stellt ein neues Rahmenwerk für kooperatives Multi-Agenten-Reinforcement-Learning mit submodularen Belohnungen vor, das durch greedy-Optimierung bei bekannten Dynamiken und einen UCB-basierten Algorithmus bei unbekannten Dynamiken effiziente Algorithmen mit nachweisbaren Approximations- und Regret-Garantien bietet.
Die Autoren stellen neue Klassen ungerichteter phylogenetischer Netzwerke namens -schnittbare Netzwerke vor, die sich durch polynomielle Erkennbarkeit auszeichnen und das NP-schwere Problem der Baum-Enthaltenseins für effizient lösen, während sie zeigen, dass die verwandte Klasse der baumkind-orientierbaren Netzwerke selbst für binäre Fälle NP-schwer zu erkennen ist.
Diese Arbeit stellt eine neue Methode zur Bestimmung unterer Schranken für die bilineare Komplexität der Matrixmultiplikation über endlichen Körpern vor, die durch eine Kombination aus Substitutionsmethode und systematischer Backtracking-Suche mit dynamischer Programmierung erstmals beweist, dass die Komplexität der Multiplikation von $3 \times 3\mathbb{F}_2$ mindestens 20 beträgt.
Die Arbeit stellt zwei neue Sketching-Methoden vor, von denen die erste erstmals die Approximation beliebiger Tensornetzwerke (einschließlich zyklischer) ermöglicht und die zweite für azyklische Netzwerke eine polynomielle Komplexität bezüglich der Anzahl der Kontraktionen bietet, während bestehende Verfahren auf azyklische Strukturen beschränkt sind und exponentiell skalieren.