Ce papier investigate la relation entre les représentations exactes et approchées des fonctions booléennes dans la base de De Morgan. Les auteurs prouvent que la densité des polynômes représentant une fonction et la densité de sa représentation approchée sont polynomiallement liées sur une échelle logarithmique. Ce résultat a des implications pour diverses mesures de complexité, telles que le degré, la densité et le poids total des coefficients.
Le théorème principal stipule que pour toute fonction booléenne totale f, le logarithme de la densité approchée est O(log^2 sparpf) + log n. Cela implique que l'approximation n'augmente pas significativement la densité pour toute fonction booléenne totale dans la base de De Morgan.
Les auteurs utilisent une méthode de restriction aléatoire innovante pour prouver ce résultat. Contrairement à la plupart des méthodes de restriction aléatoire existantes, leur méthode est adaptable et basée sur la manière dont diverses mesures de complexité s'allègent pendant le processus de restriction.
Le papier prouve également un résultat similaire pour les normes l1 exactes et approchées des fonctions booléennes dans la base de De Morgan. Ce résultat montre que l'approximation n'augmente pas significativement la masse l1 d'une fonction booléenne totale dans la base de De Morgan.
Les auteurs généralisent leurs résultats aux polynômes généralisés et aux fonctions monotones. Ils montrent que pour les fonctions monotones, la densité généralisée exacte et approchée ainsi que la norme l1 sont polynomiallement liées sur une échelle logarithmique.
Les résultats de ce papier ont des implications pour divers domaines de l'informatique, y compris la théorie de la complexité, la complexité de communication et la théorie de l'apprentissage. Ils fournissent de nouvelles perspectives sur le pouvoir de l'approximation pour les fonctions booléennes et leurs représentations.