45 articoli
Questo lavoro presenta SCORE, un linguaggio progettato per dimostrare come le operazioni sugli stack possano essere interpretate come biezioni totali, permettendo così di certificare formalmente che tutti i termini del modello computazionale sono funzioni biunivoche totali.
Questo lavoro dimostra che qualsiasi codice decodificabile localmente rilassato (RLDC) con errore di soundness inferiore a una certa soglia, anche se non lineare e con completezza imperfetta, può essere trasformato in un codice decodificabile localmente (LDC) con parametri comparabili, generalizzando risultati precedenti e permettendo di derivare nuovi limiti inferiori per RLDC, RLCC e PCPP.
Questo libro esamina i recenti progressi nel list decoding dei codici polinomiali, in particolare i codici di Reed-Solomon, che permettono la correzione di un numero elevato di errori con liste di dimensioni ottimali e algoritmi efficienti, trovando applicazioni sia nella teoria dell'informazione che nell'informatica teorica.
Questo lavoro presenta un algoritmo randomizzato in tempo polinomiale per apprendere i determinanti a lettura singola (ROD) risolvendo il problema di assegnazione dei minori principali in modalità black-box, collegando i due problemi attraverso la proprietà di estensione di rango uno delle matrici dense.
Questo articolo presenta un algoritmo quantistico basato su camminate quantistiche MNRS per il test di isomorfismo approssimato dei grafi che dimostra un vantaggio polinomiale rispetto agli approcci classici, con una complessità di query di O(n^3/2 log n/ε) contro un limite inferiore classico di Ω(n^2).