45 articoli
Il documento dimostra che il problema decisionale di approssimazione del raggio di copertura sui reticoli nella norma è NP-difficile per una funzione esplicita di approssimazione quando supera circa 35.31, estendendo i risultati precedenti sulla difficoltà di problemi correlati nella norma .
Questo lavoro chiude il divario sulla complessità parametrizzata del QBF con poche variabili esistenziali dimostrando che la dipendenza doppiamente esponenziale è ottimale sotto l'ETH per formule CNF generali, mentre per il caso limitato a due blocchi quantificatori () viene proposto un algoritmo quasi ottimale con complessità significativamente ridotta.
Il paper presenta i risultati ottenuti con AlphaEvolve, un agente di mutazione del codice basato su LLM che ha migliorato i limiti inferiori per cinque numeri di Ramsey classici e ha dimostrato la capacità di recuperare o eguagliare i migliori limiti noti per molti altri casi attraverso un unico meta-algoritmo.
Questo articolo stabilisce esplicitamente un limite costruttivo secondo cui la dimensione ottimale di un circuito cambia al massimo di in seguito a perturbazioni della tabella di verità, estendendo il risultato a distanze di Hamming generali e convalidandolo sperimentalmente per nel basis AIG, dove la differenza massima osservata è esattamente .
Questo articolo propone un quadro unificante per i teoremi di dicotomia della complessità nelle reti tensoriali booleane, classificando i problemi irrisolti in nove casi basati su gruppi finiti di funzioni binarie e risolvendo i casi dei gruppi ciclici di ordine superiore.
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.
Questo articolo sostiene che il vantaggio quantistico è stato effettivamente raggiunto, nonostante la mancanza di un consenso unanime, e delinea i prossimi passi teorici e sperimentali necessari per consolidare tale affermazione.
Questo lavoro dimostra che il gioco del Tetris con una singola tipologia di pezzo (tranne il quadrato O) è NP-difficile sotto il sistema di rotazione SRS, smentendo una congettura di 23 anni fa, mentre fornisce algoritmi efficienti per casi specifici come i pezzi a forma di domino o barre con la parte superiore della griglia vuota.
Il documento dimostra che, sotto l'assunzione di sicurezza del problema LWE, nessun algoritmo quantistico può automatizzare debolmente il sistema di dimostrazione -Frege, stabilendo così il primo risultato di difficoltà tra calcolo quantistico e ricerca di dimostrazioni proposizionali.
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 un algoritmo in tempo polinomiale per testare l'isomorfismo di estensioni di gruppi abeliani da parte di gruppi a generatori, generalizzando risultati precedenti e basandosi su un nuovo metodo per calcolare il gruppo delle unità di un anello finito.
Il paper confronta tre diverse semantica di soddisfacibilità per la logica quantistica in spazi di Hilbert a dimensione finita, dimostrando che la semantica standard ammette più formule rispetto a quelle commutative globali e parziali booleane, e fornendo un esplicito separatore che soddisfa la prima ma non le altre due.
Questo lavoro stabilisce un quadro di cambio di base per le funzioni tensoriali che estende i risultati da campi specifici a campi generali, dimostrando che il rango a fette per i tensori 3-dimensionali è linearmente limitato dal rango geometrico e quasi-supermoltiplicativo su qualsiasi campo.
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 algoritmi deterministici efficienti per la fattorizzazione di polinomi sparsi a grado individuale limitato, fornendo nuovi limiti strutturali, migliorando i tempi di esecuzione rispetto alle tecniche precedenti e risolvendo parzialmente una questione aperta sulla ricostituzione di prodotti di polinomi sparsi.
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.
Questo lavoro presenta una proposta alternativa per dimostrare un vantaggio nell'informazione quantistica basata su disuguaglianze di Bell e giochi CHSH ripetuti in parallelo, caratterizzata da un verificatore efficiente e un prover quantistico robusto al rumore che supera l'efficienza dell'approccio sperimentale recente di Kretschmer et al.
Il documento dimostra che il divario tra la dimensione minima di un circuito booleano e quella di una formula è sempre 0 o 1, stabilendo che tale differenza unitaria deriva esclusivamente da un singolo gate con fan-out pari a 2 e fornendo condizioni precise su quando la condivisione delle sottoreti è necessaria.
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.
Il documento dimostra che esiste una classe di problemi decisionali in tempo polinomiale con struttura causale intrinseca che, a causa dei limiti dell'informazione e della non duplicabilità del token, non ammette alcuna accelerazione asintotica tramite calcolo parallelo, risultando intrattabili per le famiglie di circuiti NC.