Počet záznamů: 1
On protocols for monotone feasible interpolation
- 1.
SYSNO ASEP 0574198 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název On protocols for monotone feasible interpolation Tvůrce(i) Folwarczný, Lukáš (MU-W) SAI, ORCID Číslo článku 2 Zdroj.dok. ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 15, 1-2 (2023)Poč.str. 17 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova circuit complexity ; communication complexity ; proof complexity Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 001020428600002 EID SCOPUS 85164243386 DOI 10.1145/3583754 Anotace Dag-like communication protocols, a generalization of the classical tree-like communication protocols, are useful objects in the realm of proof complexity (most importantly for monotone feasible interpolation) and circuit complexity. We consider three kinds of protocols in this article (d is the degree of a protocol): - IEQ-d-dags: feasible sets of these protocols are described by inequality which means that the feasible sets are combinatorial triangles, these protocols are also called triangle-dags in the literature, - EQ-d-dags: feasible sets are described by equality, and - c-IEQ-d-dags: feasible sets are described by a conjunction of c inequalities.Garg, Göös, Kamath, and Sokolov (Theory of Computing, 2020) mentioned all these protocols, and they noted that EQ-d-dags are a special case of c-IEQ-d-dags. The exact relationship between these types of protocols is unclear. As our main contribution, we prove the following statement: EQ-2-dags can efficiently simulate c-IEQ-d-dags when c and d are constants. This implies that EQ-2-dags are at least as strong as IEQ-d-dags and that EQ-2-dags have the same strength as c-IEQ-d-dags for c ≥ 2 (because 2-IEQ-2-dags can trivially simulate EQ-2-dags).Hrubeš and Pudlák (Information Processing Letters, 2018) proved that IEQ-d-dags over the monotone Karchmer-Wigderson relation are equivalent to monotone real circuits which implies that we have exponential lower bounds for these protocols. Lower bounds for EQ-2-dags would directly imply lower bounds for the proof system R(LIN). Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2024 Elektronická adresa https://doi.org/10.1145/3583754
Počet záznamů: 1