87 articoli
Il paper introduce l'Huffman-Bucket Sketch (HBS), una struttura dati semplice e unibile che comprime losslessly gli sketch HyperLogLog in uno spazio ottimale di bit mantenendo aggiornamenti a tempo costante e riducendo significativamente i requisiti di memoria.
Questo articolo presenta un algoritmo lineare per riconoscere i sottoinsiemi minimamente insoddisfacibili (MUS) delle formule 2-CNF, estende i risultati sulla complessità NP-completa per gli MUS con difetto 1, dimostra invece che trovare MUS contenenti una o due clausole unitarie è risolvibile in tempo polinomiale e propone un algoritmo incrementale per MUS con almeno una clausola unitaria.
Il paper introduce il blocco sparso Tensor Train (BSTT), una proiezione casuale strutturata che unifica gli operatori di sketching esistenti per il formato Tensor Train garantendo proprietà di embedding e iniezione di sottospazi con complessità lineare rispetto all'ordine del tensore, superando così le limitazioni esponenziali delle costruzioni precedenti.
Questo lavoro risolve una questione aperta dimostrando la prima separazione esplicita tra privacy differenziale in modalità cieca e adattiva nel contesto dell'osservazione continua, presentando un algoritmo accurato per un numero esponenziale di passi temporali nel primo caso e provando che ogni algoritmo adattivo fallisce dopo un numero costante di passi.
Il paper presenta IsalGraph, un metodo che codifica la struttura di qualsiasi grafo finito e semplice in una stringa compatta e isomorfismo-invariante tramite un alfabeto di nove istruzioni, dimostrando che la distanza di Levenshtein tra queste stringhe si correla fortemente con la distanza di modifica dei grafi (GED) e rendendole adatte a ricerche di similarità, generazione e modellazione linguistica.
Il paper stabilisce limiti di complessità di campionamento quasi ottimali per il test della proprietà del -clique e della -colorabilità nei grafi densi, dimostrando che il metodo dei contenitori grafici è uno strumento potente per l'analisi degli algoritmi di verifica delle proprietà.
Questo lavoro introduce un algoritmo 8-competitivo e un limite inferiore di 2 per il problema della pianificazione online dei tempi di attività su macchine eterogenee con lavori di lunghezza uniforme, colmando una lacuna teorica rilevante per i servizi di cloud computing.
Questo lavoro risolve una questione aperta generalizzando l'algoritmo di Gallai-Milgram attraverso un approccio FPT che, per un grafo non orientato, determina in tempo polinomiale se esiste una copertura di cammini inferiore a un certo parametro o produce un insieme indipendente che certifica la non esistenza di tale copertura, includendo come sottoprodotto significativo il primo algoritmo in tempo polinomiale per il problema dell'Hamiltonianità nei grafi con numero di indipendenza limitato.
Il paper introduce -Motif, un algoritmo accelerato da GPU per l'isomorfismo di sottografi che trasforma il problema in operazioni relazionali tabellari, ottenendo velocità fino a 595 volte superiori rispetto ai metodi tradizionali e abilitando applicazioni critiche come la compilazione di circuiti quantistici.
Questo lavoro presenta e valuta sperimentalmente varianti di B-tree ottimizzate per dispositivi embedded con vincoli di memoria, dimostrando che l'implementazione di ottimizzazioni specifiche per l'archiviazione flash consente un'indicizzazione efficiente anche su dispositivi di piccole dimensioni per applicazioni IoT.
Questo articolo presenta i primi algoritmi di ordinamento basati su confronti che sono strettamente in-place e raggiungono un tempo di esecuzione ottimale rispetto all'entropia delle sequenze, offrendo due paradigmi semplici per implementare la merge sort naturale su sistemi embedded con memoria limitata.
Questo lavoro migliora i limiti superiori noti per l'apprendimento agnostico di classi di concetti rispetto alla misura gaussiana, dimostrando che un'approssimazione polinomiale di grado è sufficiente per ottenere una precisione , ottenendo così limiti (quasi) ottimali per l'apprendimento di funzioni soglia polinomiali nel modello delle query statistiche.
Questo lavoro risolve parzialmente un problema aperto sulla minimizzazione del tempo di flusso massimo nel forwarding di pacchetti online, dimostrando che un algoritmo greedy raggiunge un rapporto di competitività di $2-2^{1-k}4/3$.
Il paper presenta un nuovo algoritmo per riconoscere e enumerare gli insiemi di copertura minimi (trasversali) negli ipergrafi con complessità migliorata rispetto alla dimensione degli spigoli, dimostrando inoltre che un'ulteriore ottimizzazione temporale dipendente solo polinomialmente dai vertici sarebbe equivalente a risolvere problemi aperti fondamentali nella teoria dell'enumerazione e nel riconoscimento della conformalità.
Il paper dimostra una versione indebolita di una congettura recente, provando che ogni grafo che esclude come minori indotti sia il grafo bipartito completo sia la griglia ammette una decomposizione ad albero in cui ogni sacchetto ha un numero di indipendenza a distanza $16(\log n + 1)$ limitato da una funzione polilogaritmica della dimensione del grafo.
Il documento presenta un metodo sequenziale per la generazione, l'enumerazione e il campionamento di grafi bipartiti, diretti e non diretti con sequenze di gradi prescritte, definendo condizioni necessarie e sufficienti per garantire la fattibilità globale e dimostrando, attraverso esperimenti numerici, la scalabilità dell'approccio su istanze di grandi dimensioni dove i metodi esistenti risultano proibitivi.
Il documento stabilisce una dicotomia di complessità per il problema di riconfigurazione dell'insieme dominante a distanza- (), dimostrando che è risolvibile in tempo polinomiale sui grafi split (con un algoritmo lineare sugli alberi sotto la regola ) mentre rimane -completo su grafi planari, bipartiti e cordali, estendendo così i risultati noti per il caso .
Questo lavoro presenta un nuovo metodo di campionamento casuale con sostituzione per flussi di dati ponderati, che genera in un'unica passata un campione rappresentativo senza richiedere post-elaborazione, dimostrando formalmente la sua correttezza ed efficienza rispetto agli approcci esistenti.
Questa lettera presenta un nuovo approccio basato su accumulatori in cascata per calcolare in modo efficiente somme pesate con potenze dell'indice temporale, riducendo drasticamente il costo computazionale e l'uso di memoria rispetto ai metodi tradizionali.
Questo articolo studia la complessità parametrizzata del problema del cammino minimo con vincoli disgiuntivi positivi, fornendo kernelizzazioni polinomiali basate sulla dimensione della soluzione e risultati di trattabilità parametrizzata basati sulle proprietà strutturali del grafo dei vincoli.