Near-Optimal Set-Multilinear Formula Lower Bounds
Notice bibliographique
Résumé
The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas. In this paper, we make progress along this direction by proving near-optimal lower bounds against low-depth as well as unbounded-depth set-multilinear formulas. More precisely, we show that over any field of characteristic zero, there is a polynomial f computed by a polynomial-sized set-multilinear branching program (i.e., f is in set-multilinear VBP) defined over Θ(n²) variables and of degree Θ(n), such that any product-depth Δ set-multilinear formula computing f has size at least n^Ω(n^{1/Δ}/Δ). Moreover, we show that any unbounded-depth set-multilinear formula computing f has size at least n^{Ω(log n)}. If such strong lower bounds are proven for the iterated matrix multiplication (IMM) polynomial or rather, any polynomial that is computed by an ordered set-multilinear branching program (i.e., a further restriction of set-multilinear VBP), then this would have dramatic consequences as it would imply super-polynomial lower bounds for general algebraic formulas (Raz, J. ACM 2013; Tavenas, Limaye, and Srinivasan, STOC 2022). Prior to our work, either only weaker lower bounds were known for the IMM polynomial (Tavenas, Limaye, and Srinivasan, STOC 2022), or similar strong lower bounds were known but for a hard polynomial not known to be even in set-multilinear VP (Kush and Saraf, CCC 2022; Raz, J. ACM 2009). By known depth-reduction results, our lower bounds are essentially tight for f and in general, for any hard polynomial that is in set-multilinear VBP or set-multilinear VP. Any asymptotic improvement in the lower bound (for a hard polynomial, say, in VNP) would imply super-polynomial lower bounds for general set-multilinear circuits.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction distillée sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Apprise à partir de 10 348 étiquettes directes de Codex et de 10 348 étiquettes directes de Gemma. Le mode candidate est l'union des têtes enseignantes seuillées; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont ni des étiquettes humaines ni des étiquettes directes de modèles de pointe.
Scores Codex et Gemma par catégorie
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,000 | 0,000 |
| Méta-épidémiologie (sens strict) | 0,000 | 0,000 |
| Méta-épidémiologie (sens large) | 0,000 | 0,000 |
| Bibliométrie | 0,000 | 0,001 |
| Études des sciences et des technologies | 0,001 | 0,000 |
| Communication savante | 0,001 | 0,001 |
| Science ouverte | 0,001 | 0,000 |
| Intégrité de la recherche | 0,000 | 0,000 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,001 | 0,001 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule tête enseignante, pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».