Number of the records: 1
On protocols for monotone feasible interpolation
- 1.
SYSNO ASEP 0574198 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title On protocols for monotone feasible interpolation Author(s) Folwarczný, Lukáš (MU-W) SAI, ORCID Article number 2 Source Title ACM Transactions on Computation Theory. - : Association for Computing Machinery - ISSN 1942-3454
Roč. 15, 1-2 (2023)Number of pages 17 s. Language eng - English Country US - United States Keywords circuit complexity ; communication complexity ; proof complexity Subject RIV BA - General Mathematics OECD category Pure mathematics Method of publishing Limited access Institutional support MU-W - RVO:67985840 UT WOS 001020428600002 EID SCOPUS 85164243386 DOI 10.1145/3583754 Annotation 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). Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2024 Electronic address https://doi.org/10.1145/3583754
Number of the records: 1