91 articoli
Il lavoro presenta una struttura dati completamente dinamica che mantiene uno sparsificatore spettrale di un grafo geometrico con aggiornamenti dei punti in tempo , garantendo robustezza contro avversari adattivi e permettendo il mantenimento efficiente di moltiplicazioni e proiezioni matrice-vettore.
Il paper presenta un approccio innovativo e simmetrico per risolvere i giochi a ricompensa scontata, basato su un sistema di vincoli che minimizza l'errore tra le disuguaglianze definite dagli archi, sfidando la dicotomia tradizionale tra miglioramento delle strategie e iterazione dei valori.
Questo lavoro determina la soglia computazionale per il rilevamento di correlazioni in coppie di modelli a blocchi stocastici correlati, dimostrando che i test basati su polinomi di basso grado riescono a distinguere il modello da grafi indipendenti se e solo se la probabilità di campionamento supera il minimo tra la costante di Otter e la soglia di Kesten-Stigum.
Il paper propone una definizione rilassata della dimensione autostradale che include spazi metrici naturali come le griglie e il piano euclideo, permettendo la costruzione di un PTAS per il TSP e lo sviluppo di strumenti metrici fondamentali come decomposizioni imbottite e coperture sparse.
Questo articolo presenta due algoritmi generalizzati per calcolare l'inverso modulare per interi qualsiasi , estendendo le tecniche esistenti basate su espansioni -adiche e sollevamento di Hensel per sfruttare l'efficienza dell'aritmetica nativa delle architetture informatiche.
Questo lavoro migliora gli algoritmi esistenti per le operazioni di algebra lineare sulla matrice di kernel, riducendo la dipendenza dal numero di punti e dall'errore tramite l'uso della stima della densità di kernel, e fornisce limiti inferiori che ne delineano i vincoli teorici.
Questo lavoro presenta il primo algoritmo iterativo deterministico per costruire un coreset di dimensione ottimale che garantisce un embedding deterministico del sottospazio per qualsiasi , risolvendo un problema aperto di lunga data eliminando i fattori logaritmici e permettendo la risoluzione deterministica del problema di regressione .
Questo lavoro presenta il primo miglioramento moltiplicativo rispetto all'algoritmo greedy per la massimizzazione di funzioni submodulari non negative e monotone soggette all'intersezione di matroidi, ottenendo un rapporto di approssimazione inferiore a $0.819kk$.
Questo lavoro dimostra che è possibile aggirare le barriere di errore additivo note per il rilascio continuo differenzialmente privato del numero di elementi distinti e del momento in flussi turnstile, ottenendo algoritmi con errore sia additivo che moltiplicativo polilogaritmici e utilizzando spazio polilogaritmico.
Questo articolo presenta un metodo di "length capping" per le strutture di movimento che, rispetto agli approcci tradizionali, garantisce tempi di query ottimali e una costruzione più rapida, riducendo al contempo lo spazio di memorizzazione e migliorando le prestazioni pratiche per le permutazioni RLBWT, come dimostrato dall'implementazione nella libreria RunPerm.
Il paper introduce DRESS, un framework deterministico e privo di parametri che genera un'impronta digitale invariante per isomorfismo attraverso la convergenza di un sistema dinamico non lineare, offrendo un'espressività pari o superiore al test 2-WL a un costo computazionale significativamente inferiore e generalizzabile a varianti come Motif-DRESS e -DRESS per migliorare ulteriormente la capacità di discriminazione dei grafi.