Résumé - L'égalité est beaucoup plus faible que la communication à coût constant.

L'égalité est beaucoup plus faible que la communication à coût constant.

2025-07-15 10:10:21

{"Mika Göös","Nathaniel Harms","Artur Riazanov"}

{cs.CC}

Cet article investigate les pouvoirs de l'hashage simple, en particulier le problème de communication égale, en complexité de communication. Les auteurs démontrent un résultat surprenant : même les protocoles aléatoires à coût constant ne peuvent pas être "dérandérisés" de manière efficace en utilisant des oracles d'Égalité. **Principales Découvertes** : * **Communication à Coût Constant vs. Oracles d'Égalité** : Les auteurs présentent un problème de communication avec une communication aléatoire à coût constant, mais nécessitant nΩ(1) de requêtes déterministes (ou même non-deterministiques) à un oracle d'Égalité. Cela implique que BPP0 ̸⊆ PEq, où BPP0 est la classe des problèmes de coût constant avec communication aléatoire et PEq est la classe des problèmes avec un coût d'oracle d'Égalité polynôme de log n. * **Séparation par rapport à la Distance de Hamming k** : Les auteurs montrent également que la communication à coût constant ne se réduit pas à l'hiérarchie de Distance de Hamming k, améliorant ainsi la séparation entre BPP0 et la Distance de Hamming k. * **Deux Preuves avec Cinq Corollaires** : L'article fournit deux preuves inégalables du résultat principal, l'une analytique et l'autre combinatoire. Ces preuves produisent plusieurs corollaires intéressants, y compris : * L'existence d'une fonction avec une norme spectrale approchée O(1) mais une norme spectrale exacte 2Ω(n). * L'existence d'une fonction avec une taille d'arbre de décision de parité aléatoire O(1) mais une taille d'arbre de décision de parité déterministe 2Ω(n). * Une amélioration de la séparation entre BPP et NPEq, où NPEq est la classe des problèmes avec un coût d'oracle d'Égalité non-deterministe polynôme de log n. * Une amélioration des bornes inférieures sur NDEq(·), le coût d'oracle d'Égalité non-deterministe. * **Implications** : * Les résultats mettent en lumière les limites de l'hashage simple, même en présence d'oracles d'Égalité, pour l'efficacité de la dérandérisation des protocoles de communication. * Ils fournissent de nouvelles insights sur la complexité des problèmes de communication et le pouvoir de différents types d'oracles. * Les corollaires ont des implications pour divers domaines de la théorie informatique théorique, y compris la théorie de la complexité, la complexité de communication et l'analyse des fonctions booléennes. **Signification** : Cet article apporte des contributions significatives au domaine de la complexité de communication en fournissant de nouvelles insights sur le pouvoir de l'hashage simple et les limites de la dérandérisation en utilisant des oracles d'Égalité. Les résultats ont des implications pour divers domaines de la théorie informatique théorique et fournissent une base pour des recherches futures en complexité de communication et dans des domaines connexes.