45 articles
Cet article démontre que le problème du rayon de recouvrement sur les réseaux est NP-difficile pour des normes avec supérieur à environ 35,31, établissant ainsi la première preuve de dureté pour ce problème avec un paramètre explicite .
Cet article comble un écart théorique en démontrant que la dépendance doublement exponentielle pour les QBF avec peu de variables existentielles est optimale sous l'hypothèse ETH, tout en proposant un algorithme quasi-optimal pour le cas restreint à deux blocs de quantificateurs.
En utilisant AlphaEvolve, un agent de mutation de code basé sur un modèle de langage, cette étude améliore les bornes inférieures de cinq nombres de Ramsey classiques et démontre la capacité d'un algorithme méta unique à générer des algorithmes de recherche performants pour l'ensemble de ces résultats.
Cet article établit explicitement que la taille d'un circuit optimal varie au plus de lors d'une perturbation ponctuelle de la table de vérité, une borne confirmée comme optimale pour via une vérification exhaustive sur la base AIG.
Cet article propose un cadre unificateur pour les théorèmes de dichotomie de complexité des réseaux de tenseurs booléens, en classant les problèmes non résolus selon des catégories de groupes finis et en résolvant notamment le cas des groupes cycliques d'ordre supérieur.
Ce papier améliore le temps d'exécution des algorithmes d'approximation pour les problèmes de -médiane et -means en espaces euclidiens de faible dimension et établit une borne inférieure presque correspondante sous l'hypothèse du temps exponentiel.
Dans cet article, l'auteur soutient que l'avantage quantique a bel et bien été atteint, en s'appuyant sur les expériences menées depuis 2019, et propose des perspectives pour les recherches théoriques et expérimentales futures.
Cet article démontre que le jeu de Tetris reste NP-complet pour la plupart des pièces tétramino (sauf le carré O) et pour des séquences générées par un randomiseur, tout en prouvant que le problème devient polynomial pour les pièces domino ou les pièces $1 \times k$ dans des conditions initiales spécifiques.
Cet article établit que, sous l'hypothèse de la sécurité de l'apprentissage avec erreurs (LWE), aucun algorithme quantique ne peut automatiser faiblement le système de preuve -Frege, marquant ainsi la première interaction démontrée entre le calcul quantique et la recherche de preuves propositionnelles.
Cet article propose un schéma différentiellement privé pour estimer les statistiques de fonctions boîte noire en arbitrant entre l'efficacité statistique et l'efficacité oracle, tout en établissant des bornes inférieures démontrant la quasi-optimalité de cette approche.
Cet article présente un test d'isomorphisme en temps polynomial pour les extensions de groupes abéliens par des groupes à générateurs, en particulier pour les extensions abéliennes par cycliques ou par groupes simples, grâce à un nouvel algorithme polynomial pour le calcul du groupe des unités d'un anneau fini.
Cet article compare trois notions de satisfaisabilité pour la logique quantique en dimension fixe, démontrant que la sémantique standard admet des formules satisfaisables (comme SEP-1) qui sont rejetées par les sémantiques à projecteurs commutants globaux et à algèbres booléennes partielles locales, établissant ainsi une hiérarchie stricte entre ces classes de satisfaisabilité.
Cet article établit un cadre de changement de base permettant d'étendre les résultats sur les fonctions tensorielles à des corps généraux, démontrant ainsi que le rang tranché des tenseurs d'ordre 3 est linéairement borné par le rang géométrique et quasi-supermultiplicatif sur n'importe quel corps.
Ce papier présente une nouvelle méthode combinant substitution et recherche par backtracking pour prouver que la complexité bilinéaire de la multiplication de matrices 3×3 sur le corps fini est d'au moins 20, améliorant ainsi la borne inférieure précédente de 19.
Cet article présente des algorithmes déterministes efficaces pour factoriser des polynômes clairsemés à degré individuel borné, établissant de nouvelles bornes structurelles et améliorant les complexités temporelles des méthodes existantes, y compris pour les produits de tels polynômes et sur des corps de caractéristique arbitraire.
Cet article propose un cadre unifié et agnostique du domaine pour estimer le facteur de bus en le modélisant comme un problème d'optimisation combinatoire sur des graphes bipartis, prouvant la complexité NP-difficile des formulations exactes et introduisant une nouvelle mesure de robustesse normalisée qui capture à la fois la perte de couverture et la fragmentation du projet, tout en offrant des algorithmes d'approximation efficaces.
Cet article présente une nouvelle proposition d'avantage quantique basée sur les inégalités de Bell et des jeux CHSH répétés en parallèle, offrant un vérificateur efficace et un prouveur quantique robuste au bruit, surpassant ainsi l'approche précédente de Kretschmer et al.
Ce papier démontre que l'écart entre la taille minimale d'un circuit booléen et celle d'une formule sur la base AIG est toujours 0 ou 1, caractérisant précisément les conditions d'optimisation et les structures de partage nécessaires pour atteindre cette borne.
Cet article caractérise la résolubilité et le nombre de solutions des puzzles de correspondance de permutations sur grille, fournit un algorithme linéaire pour corriger les instances non résolubles, et démontre que la généralisation du problème à des permutations arbitraires est NP-complète.
Cet article démontre qu'un problème de décision polynomial, dont l'exécution dépend de contraintes causales strictes, ne peut bénéficier d'aucune accélération asymptotique par le parallélisme et échappe à la classe , révélant ainsi une limite fondamentale entre le parallélisme logique et l'exécutabilité causale.