45 articoli
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 .
Questo lavoro stabilisce nuove separazioni tra circuiti quantistici e classici a profondità costante, dimostra che l'uso di gate modulari su insiemi infiniti permette di implementare gate soglia e prova che i qudit non offrono vantaggi aggiuntivi rispetto ai qubit in questo contesto.
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.
Il paper dimostra che il problema di determinare se una strategia calcolabile garantisce la vittoria in una data situazione del gioco di carte Yu-Gi-Oh! TCG è indecidibile e, più precisamente, completo per la classe , estendendo tale risultato a tutte le strategie tramite una riduzione agli ordini ben fondati contabili.
Questo articolo individua sei dimensioni fondamentali, tra cui due nuove (direzionalità e temporalità), che rivelano l'asimmetria operativa tra generazione e riconoscimento nella teoria dei linguaggi formali, sfatando il mito che la generazione sia intrinsecamente semplice e collegando tale asimmetria temporale al framework della sorpresa, anche nel contesto dei moderni modelli linguistici.
Questa tesi di abilitazione esplora l'efficienza algoritmica nel calcolo polinomiale sotto vincoli di spazio, proponendo nuovi metodi per operazioni fondamentali e sviluppando il primo algoritmo quasi-lineare per l'interpolazione di polinomi sparsi.
Il lavoro stabilisce una condizione necessaria e sufficiente per la simulabilità classica di circuiti quantistici seguiti da post-processing classico sparso, dimostrando che tale simulazione è possibile per una vasta gamma di circuiti (inclusi IQP e Clifford Magic) e fornendo un algoritmo probabilistico polinomiale per il caso di circuiti a profondità costante basato su circuiti quantistici commutanti.
Il documento propone una reinterpretazione della scoperta di testimoni NP attraverso una lente informazionale, dimostrando che nel modello psocid, dove l'accesso al testimone è limitato a sonde di uguaglianza senza struttura, l'accumulo di informazioni è insufficiente per il recupero affidabile, rivelando così un'origine informazionale fondamentale della complessità esponenziale della ricerca.
Questo articolo dimostra che il problema del Maximum Partial List H-Coloring è risolvibile in tempo polinomiale sui grafi privi di P_5 per ogni grafo H fissato, risolvendo una questione aperta e migliorando un precedente algoritmo a tempo esponenziale.
Questo articolo studia la complessità delle rappresentazioni Decision DNNF, introducendo un metodo generale per dimostrare limiti inferiori, separando esponenzialmente diverse classi di modelli come -OBDD e OBDD ordinari, e proponendo una nuova variante chiamata Structured -FBDD che si dimostra efficace per le formule CNF a larghezza d'albero d'incidenza limitata.
Questo lavoro presenta algoritmi classici efficienti per i problemi e a soluzione intera vincolata, dimostrando che non esiste più un vantaggio quantistico esponenziale per tali problemi, invalidando così i risultati precedenti di Chen, Liu e Zhandry.
Questo articolo presenta un nuovo algoritmo di approssimazione con rapporto $4/3$ per il Problema di Ampliamento dell'Albero (TAP), basato su una tecnica innovativa denominata "rapporto locale differito" e "arrampicata", che offre un tempo di esecuzione più rapido rispetto agli approcci esistenti senza ricorrere all'enumerazione di strutture esponenziali o alla scalatura e arrotondamento.
Questo lavoro presenta una classificazione completa della complessità computazionale distribuita per i problemi di ottimizzazione locale nei cicli diretti, identificando quattro possibili classi di complessità e fornendo un algoritmo centrale efficiente per determinare automaticamente la classe di un dato problema e sintetizzare un algoritmo distribuito asintoticamente ottimale.
Questo lavoro stabilisce un legame fondamentale tra le classi di complessità computazionale e le architetture delle reti ricorrenti, dimostrando che le RNN lineari sono parallelizzabili come i transformer perché corrispondono a circuiti aritmetici di profondità logaritmica, mentre le RNN non lineari risolvono problemi completi per P che ne impediscono un'efficiente parallelizzazione.
Questo lavoro generalizza la selezione top- equa a più gruppi protetti, analizzandone la complessità computazionale e proponendo una soluzione pratica che bilancia l'efficienza, la minimizzazione della disparità rispetto a una funzione di riferimento e la stabilità della funzione di punteggio rispetto alle perturbazioni.
Questo lavoro presenta l'implementazione e la simulazione di algoritmi quantistici basati sulla ricerca di Grover per risolvere il problema NP-completo di coordinazione dei segnali di rete e la sua variante robusta, dimostrandone il vantaggio quadratico sia in simulazione che su un computer quantistico reale.
Questo articolo presenta un algoritmo basato sui risultanti che sfrutta la sparsità strutturata per risolvere un sistema di equazioni polinomiali su un campo finito in modo significativamente più efficiente rispetto ai metodi di forza bruta o alle basi di Gröbner standard.
Questo lavoro stabilisce una corrispondenza esatta tra la potenza espressiva delle reti neurali su grafi ricorrenti e quella dei circuiti aritmetici ricorrenti operanti sui numeri reali, dimostrando che i due modelli sono computazionalmente equivalenti.
Questo lavoro risolve una questione aperta sulla complessità del problema della corrispondenza di Morse ottimale su complessi CW regolari, presentando un algoritmo con tempo di esecuzione $2^{O(k \log k)} nk$ e dimostrando che tale dipendenza è ottimale sotto l'Ipotesi del Tempo Esponenziale (ETH).
Il documento dimostra che la congettura di Aaronson-Ambainis è valida per una frazione non trascurabile di restrizioni casuali di un polinomio, garantendo l'esistenza di una coordinata con influenza significativa quando la varianza non è troppo bassa.