45 articles
Cet article présente SCORE, un langage conçu pour manipuler des variables et des piles, et démontre comment interpréter ses opérations comme des bijections totales certifiées par un assistant de preuve, permettant ainsi d'étudier la complexité computationnelle dans des modèles réversibles complets.
Cet article démontre que tout code localement décodable relâché (RLDC) à requêtes avec une erreur de sondeur inférieure à un certain seuil peut être converti en un code localement décodable (LDC) standard à requêtes avec des paramètres comparables, généralisant ainsi des résultats précédents aux codes non linéaires et établissant de nouvelles bornes inférieures pour les RLDC, les codes localement correctables relâchés et les preuves de proximité vérifiables probabilistiquement.
Cet ouvrage présente une synthèse des récents progrès accomplis dans le décodage en liste des codes de Reed-Solomon et des familles de codes polynomiaux apparentés, notamment en matière d'efficacité algorithmique, de taille de liste optimale et de capacité de correction jusqu'à la limite informationnelle.
Cet article présente un algorithme randomisé en temps polynomial qui résout le problème d'apprentissage des déterminants « read-once » en le reliant et en résolvant une version boîte noire du problème d'affectation des mineurs principaux via une nouvelle propriété d'extension de rang un pour les matrices denses.
Cet article présente un algorithme quantique basé sur des marches quantiques MNRS pour tester l'isomorphisme approximatif de graphes, atteignant une complexité de requête de O(n^{3/2} log n / ε) et établissant une accélération polynomiale par rapport aux bornes inférieures classiques.