86 articoli
Questo lavoro presenta uno schema generico per la stima dei momenti nel modello di streaming a turnstile, basato sull'hashing degli indici su processi di Lévy e sulla rappresentazione di Lévy-Khintchine, unificando così costruzioni esistenti e estendendo la trattabilità a nuove classi di funzioni multidimensionali ed eterogenee.
Questo articolo introduce un nuovo tipo di subgradiente basato sulle funzioni di Busemann per spazi di Hadamard, permettendo di generalizzare i metodi stocastici e incrementali di subgradiente con garanzie di complessità e applicandoli a problemi come il calcolo delle medie -e nelle varietà BHV degli alberi.
Il paper dimostra che un metodo semplice ed esatto risolve istantaneamente le istanze di riferimento classiche del problema del commesso viaggiatore con finestre temporali, rivelando che queste non sono più rappresentative per valutare l'efficacia degli algoritmi e richiedendo cautela nella creazione di set di addestramento per il machine learning.
Il documento presenta l'algoritmo Elastic Time Warping, che risolve il problema di allineamento di serie temporali in spazi metrici arbitrari utilizzando una penalità basata sul kernel di Hellinger con una complessità computazionale cubica.
Il documento presenta bsort, un algoritmo di ordinamento non basato su confronti per interi e numeri in virgola mobile che unifica i casi di segno e floating-point tramite un approccio derivato dal binary quicksort, ottenendo una complessità temporale di e uno spazio ausiliario di .
Questo lavoro presenta un algoritmo di streaming a passaggio singolo che, per il problema della selezione di intervalli unitari in ordine casuale, raggiunge un fattore di approssimazione atteso di 0,7401 utilizzando spazio lineare rispetto alla soluzione ottima, superando il limite di 2/3 noto per gli stream con ordine avversario e fornendo anche limiti inferiori sulla complessità spaziale necessaria per approssimazioni migliori.
Questo articolo presenta un algoritmo di approssimazione polinomiale (PTAS) per il problema del 2-matching pesato senza triangoli, basato su una semplice ricerca locale e un'analisi non banale, risolvendo un problema per cui esisteva solo un'approssimazione 2/3.
Questo lavoro presenta un nuovo algoritmo di mining dei sottostringhe frequenti con garanzia di privacy differenziale che, mantenendo gli stessi errori ottimali della ricerca precedente, riduce drasticamente la complessità spaziale e temporale da a e grazie a una strategia di generazione dei candidati raffinata e a un'efficace potatura dello spazio di ricerca.
Questo lavoro presenta un protocollo migliorato per il problema degli esperti distribuiti che riduce il regret e ottimizza la comunicazione necessaria tra i server, superando i risultati precedenti.
Questo articolo studia il problema online del matching non incrociato pesato nel piano euclideo, dimostrando l'impossibilità di algoritmi deterministici con rapporto competitivo non banale, ma proponendo invece algoritmi randomizzati a rapporto costante, analizzando varianti come la revocabilità e i punti collineari, e migliorando i limiti sulla complessità degli consigli per l'ottimalità.
Questo lavoro presenta un algoritmo corretto ed esaustivo per l'enumerazione automatica di tutte le coppie critiche nei sistemi di riscrittura di diagrammi a stringa in categorie monoidali simmetriche prive di struttura di Frobenius, realizzabile attraverso la manipolazione concreta di ipergrafi.
Questo lavoro migliora i tempi di esecuzione degli algoritmi di approssimazione per i problemi di clustering -median e -means in spazi euclidei a bassa dimensione e dimostra che tale miglioramento è quasi ottimale, fornendo un limite inferiore corrispondente basato sull'ipotesi Gap Exponential Time.
Il paper dimostra che, nel contesto dell'abbinamento many-to-many con preferenze con legami e quote inferiori, esiste sempre un abbinamento critico e rilassatamente stabile, e propone un algoritmo di approssimazione in tempo polinomiale per massimizzarne la cardinalità, nonostante il problema esatto sia NP-difficile.
Questo lavoro dimostra che esiste una separazione provabile tra algoritmi classici basati su stati gaussiani e algoritmi quantistici efficienti per l'approssimazione dello stato fondamentale del modello SYK diradato, in quanto gli stati gaussiani falliscono nel fornire approssimazioni a fattore costante per valori di sparsità , mentre l'algoritmo quantistico di Hastings-O'Donnell mantiene la sua efficacia in tale regime.
Questo lavoro presenta un nuovo schema per la stima differenzialmente privata di funzioni black-box che ottimizza il compromesso tra efficienza statistica ed efficienza computazionale, supportato da limiti inferiori che ne dimostrano la near-ottimalità.
Il documento presenta la Teoria dello Spazio di Esplorazione (EST), un quadro formale basato sulla teoria degli spazi di conoscenza e sull'analisi dei concetti formali che modella le dipendenze prerequisito tra punti di interesse per garantire raccomandazioni strutturalmente valide, spiegabili e ottimali all'interno di sistemi di raccomandazione basati sulla posizione.
Questo articolo introduce un nuovo quadro teorico per l'apprendimento per rinforzo multi-agente cooperativo con ricompense submodulari, proponendo algoritmi con garanzie provate di efficienza nei campioni e bound sul rimpianto che superano la maledizione della dimensionalità.
Questo articolo introduce le nuove classi di reti filogenetiche non radicate chiamate "q-cuttable", dimostrandone il riconoscimento in tempo polinomiale e la capacità di rendere risolvibile in tempo polinomiale il problema NP-difficile del "Tree Containment" per q≥3, superando così le limitazioni computazionali delle reti orientabili in alberi-child.
Questo articolo presenta un nuovo metodo basato su backtracking e sostituzione per dimostrare che la complessità bilineare della moltiplicazione di matrici $3 \times 3\mathbb{F}_2$ è almeno 20, migliorando il precedente limite inferiore di 19.
Questo lavoro presenta il primo metodo per approssimare la contrazione di reti tensoriali arbitrarie, incluse quelle cicliche, e introduce una seconda tecnica per le reti acicliche che riduce la complessità computazionale da esponenziale a polinomiale rispetto al numero di contrazioni.