On protocols for monotone feasible interpolation

0574198 - MÚ 2024 RIV US eng J - Journal Article
Folwarczný, Lukáš
On protocols for monotone feasible interpolation.
ACM Transactions on Computation Theory. Roč. 15, 1-2 (2023), č. článku 2. ISSN 1942-3454
Institutional support: RVO:67985840
Keywords : circuit complexity * communication complexity * proof complexity
OECD category: Pure mathematics
Impact factor: 0.7, year: 2022
Method of publishing: Limited access
https://doi.org/10.1145/3583754

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).
Permanent Link: https://hdl.handle.net/11104/0344548