A symmetric recursive algorithm for mean-payoff games
Il paper propone un nuovo algoritmo deterministico e simmetrico basato sulla ricorsione per la risoluzione dei giochi a pagamento medio.
💻 Category
cs.DS
87 articoli
Succinct QUBO formulations for permutation problems by sorting networks
Questo articolo introduce una nuova formulazione QUBO per i problemi di permutazione basata sulle reti di ordinamento, che riduce il numero di variabili binarie a rispetto alla codifica standard, garantendo uniformità, sparsità e la capacità di supportare operazioni algebriche e vincoli aggiuntivi per applicazioni in crittografia e design combinatorio.
Structured Gossip: A Partition-Resilient DNS for Internet-Scale Dynamic Networks
Il paper presenta il "Structured Gossip DNS", un protocollo di risoluzione dei nomi per reti dinamiche su larga scala che utilizza tabelle a dita DHT e operazioni commutative per garantire la resilienza alle partizioni e la consistenza eventuale senza coordinamento globale, riducendo la complessità dei messaggi da a .
The Theory and Practice of Computing the Bus-Factor
Questo articolo propone un quadro teorico unificato e indipendente dal dominio per calcolare il "bus-factor", dimostrando la complessità computazionale NP-difficile delle relative formulazioni e introducendo una nuova misura basata sulla robustezza di rete che, grazie a efficienti algoritmi di approssimazione, offre una valutazione più stabile e informativa del rischio di progetto rispetto agli approcci esistenti.
The Li-Chao Tree: Algorithm Specification and Analysis
Questo articolo fornisce la prima formalizzazione peer-reviewed dell'albero di Li-Chao, presentandone le specifiche algoritmiche complete, le dimostrazioni di correttezza formale, l'analisi della complessità teorica e la caratterizzazione delle prestazioni empiriche.
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Questo articolo caratterizza i "permutation match puzzles" su griglie, dimostrando che la loro risolubilità dipende dall'assenza di cicli nel grafo dei vincoli, fornendo una formula per il numero di soluzioni e un algoritmo lineare per le riparazioni minime nel caso semplice, mentre stabilisce che il problema diventa NP-completo quando si generalizzano i vincoli a permutazioni arbitrarie.
Sampling Colorings with Fixed Color Class Sizes
Questo articolo presenta un algoritmo di campionamento in tempo polinomiale per colorazioni eque di grafi con , estendendo i risultati a casi con piccole deviazioni dall'equità e dimostrando un teorema del limite centrale locale multivariato per le dimensioni delle classi di colore.
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Questo studio dimostra che, nel caso di corrispondenze parziali in una dimensione, la distribuzione a posteriori per l'inferenza bayesiana di un matching nascosto tra punti casuali correlati è approssimabile tramite algoritmi locali e presenta un limite ben definito all'infinito, mentre per il caso di corrispondenza esatta è necessaria una ordinazione globale e un'indicizzazione basata sul flusso per definire il limite delle statistiche marginali.
A note on approximating the average degree of bounded arboricity graphs
Questa nota presenta una versione completa e ottimizzata dell'algoritmo di Eden, Ron e Seshadhri per stimare il grado medio di grafi con arboricità limitata, eliminando le perdite logaritmiche e fornendo un'approssimazione con un numero di query pari a .
Faster shortest-path algorithms using the acyclic-connected tree
Il paper presenta un nuovo metodo per migliorare la complessità temporale degli algoritmi di cammino minimo a sorgente singola sfruttando una decomposizione lineare dei grafi chiamata albero aciclico-connesso, che permette di ottenere complessità dipendenti dalla larghezza di annidamento del grafo invece che solo dalla dimensione totale.
Computational Complexity in Property Testing
Questo lavoro avvia uno studio sistematico sulla complessità computazionale del testing delle proprietà, stabilendo teoremi di gerarchia tempo-query e fornendo limiti inferiori basati su congetture fine-grained per l'approssimazione della distanza degli iperpiani, dimostrando così una separazione fondamentale tra complessità di query e complessità temporale.
Hallucination is a Consequence of Space-Optimality: A Rate-Distortion Theorem for Membership Testing
Questo lavoro teorizza che l'allucinazione nei modelli linguistici è una conseguenza inevitabile dell'ottimizzazione dello spazio di memoria, dimostrando attraverso un teorema di rate-distorsione che, in condizioni di capacità limitata, la strategia informazionalmente ottimale richiede di assegnare alta confidenza a fatti non veri piuttosto che astenersi o dimenticare.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
Questo articolo fornisce la giustificazione teorica del framework DRESS, dimostrando che la sua variante -DRESS distingue tutte le coppie CFI e, sotto una specifica congettura strutturale, supera o eguaglia la gerarchia -WL per ogni .
Transposition is Nearly Optimal for IID List Update
Questo articolo dimostra che la regola di trasposizione, un algoritmo online senza memoria per il problema dell'aggiornamento delle liste, raggiunge un costo di accesso atteso al più pari a OPT+1 nel modello i.i.d., confermando così una congettura di Rivest di cinquant'anni fa.
Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
Il paper presenta un algoritmo deterministico che ricostruisce i grafi con treelength limitata e grado massimo limitato utilizzando un numero di query di distanza , migliorando di un fattore logaritmico le migliori conoscenze precedenti e raggiungendo il limite inferiore noto per i grafi a cordalità limitata.
Density-Dependent Graph Orientation and Coloring in Scalable MPC
Questo articolo presenta algoritmi di calcolo massivamente parallelo (MPC) scalabili che, operando in un regime di memoria fortemente sublineare, orientano gli archi e colorano i vertici di un grafo in round in base alla densità del sottografo più denso, superando così il limite di complessità di delle soluzioni precedenti.
Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
Questo studio dimostra matematicamente che, in tre dimensioni, la strategia di ricerca intermittente di Cauchy (esponente di Lévy ) è l'unica a garantire una rilevazione ottimale e invariante di scala per una vasta gamma di forme e dimensioni dei bersagli, rivelando una sensibilità alla geometria del target assente nelle dimensioni inferiori.
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Il documento presenta un metodo per rappresentare in modo compatto (di dimensione polinomiale) tutte le tagli di valore in funzioni submodulari simmetriche intere, fornendo un algoritmo efficiente per la loro costruzione e applicazioni a problemi di ottimizzazione con vincoli di cardinalità.
Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
Questo articolo dimostra che, nel modello di movimento congiunto per la materia programmabile, è possibile riconfigurare qualsiasi struttura in un segmento lineare canonico in tempo sublineare , risolvendo positivamente un problema aperto e fornendo nuovi primitivi per il movimento parallelo efficiente.
Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
Il paper propone l'algoritmo "Sample-and-Search", un metodo basato sul campionamento che risolve il problema del clustering k-mediane potenziato dall'apprendimento in spazi ad alta dimensionalità, riducendo significativamente la complessità computazionale e il costo di clustering rispetto agli approcci esistenti.